回転を伴うグラフ上のペブル移動：効率的な実現可能性判定と計画アルゴリズム
Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms
連結グラフ上の識別可能なペブル（ロボット）の衝突回避経路計画問題を扱い、関連する置換群の直径がO(n^2)以下であることを示して、実現可能性を線形時間で判定し完全経路をO(n^3)で計画するアルゴリズムを提案した。
著者: Jingjin Yu, Daniela Rus
分類: cs.DS, cs.RO
原文アブストラクト
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.
