Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms
This addresses path planning for multiple robots on graphs, offering efficient algorithms for a specific but incremental improvement in computational geometry and robotics.
The paper tackles the problem of planning collision-free paths for distinguishable pebbles on a graph, showing that feasibility is determined by the diameter of a permutation group induced by the graph, and provides a linear-time feasibility test and an O(n^3) path planning algorithm.
We study the problem of planning paths for $p$ distinguishable pebbles (robots) residing on the vertices of an $n$-vertex connected graph with $p \le 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(n^2)$, we establish a linear time algorithm for deciding the feasibility of such problems and an $O(n^3)$ algorithm for planning complete paths.