Pebble motion on graphs with rotations: Efficient feasibility tests and planning algorithms

Jingjin Yu, Daniela Rus

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

We study the problem of planning paths for p distinguishable pebbles (robots) residing on the vertices of an n-vertex connected graph with p ≤ n. A pebble may move from a vertex to an adjacent one in a time step provided that it does not collide with other pebbles. When p = n, the only collision free moves are synchronous rotations of pebbles on disjoint cycles of the graph. We show that the feasibility of such problems is intrinsically determined by the diameter of a (unique) permutation group induced by the underlying graph. Roughly speaking, the diameter of a group G is the minimum length of the generator product required to reach an arbitrary element of G from the identity element. Through bounding the diameter of this associated permutation group, which assumes a maximum value of O(n2), we establish a linear time algorithm for deciding the feasibility of such problems and an O(n3) algorithm for planning complete paths.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
EditorsA. Frank van der Stappen, H. Levent Akin, Nancy M. Amato, Volkan Isler
PublisherSpringer Verlag
Pages729-746
Number of pages18
ISBN (Print)9783319165943
DOIs
StatePublished - 2015
Externally publishedYes
Event11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014 - Istanbul, Turkey
Duration: Aug 3 2014Aug 5 2014

Publication series

NameSpringer Tracts in Advanced Robotics
Volume107
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Other

Other11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014
Country/TerritoryTurkey
CityIstanbul
Period8/3/148/5/14

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Pebble motion on graphs with rotations: Efficient feasibility tests and planning algorithms'. Together they form a unique fingerprint.

Cite this