2012/05/23 by Jingjin Yu, Daniela Rus, Yu, Jingjin +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.1205.5263
openalex publication_date 2012/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \mathbf G is the minimum length of the generator product required to reach an arbitrary element of \mathbf 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.