@inproceedings{b60e87ca33f7437fbccad48cc09cf076,
title = "Pebble motion on graphs with rotations: Efficient feasibility tests and planning algorithms",
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.",
author = "Jingjin Yu and Daniela Rus",
note = "Funding Information: This work was supported in part by NSF grant 0904501 and ONR projects N00014-12-1-1000, N00014-09-1-1051, and N00014-09-1-1052. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014 ; Conference date: 03-08-2014 Through 05-08-2014",
year = "2015",
doi = "10.1007/978-3-319-16595-0_42",
language = "English (US)",
isbn = "9783319165943",
series = "Springer Tracts in Advanced Robotics",
publisher = "Springer Verlag",
pages = "729--746",
editor = "{van der Stappen}, {A. Frank} and {Levent Akin}, H. and Amato, {Nancy M.} and Volkan Isler",
booktitle = "Algorithmic Foundations of Robotics - Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014",
address = "Germany",
}