medial-axis-based pebble-graph embedding を用いたマルチロボット経路計画
Multi-Robot Path Planning Using Medial-Axis-Based Pebble-Graph Embedding
連続平面作業空間におけるラベル付き円盤型マルチロボット経路計画を、 medial axis 変換で内接円を抽出し、ロボットを層状に配置した pebble graph に変換して効率的に解く集中型アルゴリズムを提案。狭通路でも高密度配置で平均83%の成功率を達成。
著者: Liang He, Zherong Pan, Kiril Solovey, Biao Jia, Dinesh Manocha
分類: cs.RO
原文アブストラクト
We present a centralized algorithm for labeled, disk-shaped Multi-Robot Path Planning (MPP) in a continuous planar workspace with polygonal boundaries. Our method automatically transform the continuous problem into a discrete, graph-based variant termed the pebble motion problem, which can be solved efficiently. To construct the underlying pebble graph, we identify inscribed circles in the workspace via a medial axis transform and organize robots into layers within each inscribed circle. We show that our layered pebble-graph enables collision-free motions, allowing all graph-restricted MPP instances to be feasible. MPP instances with continuous start and goal positions can then be solved via local navigations that route robots from and to graph vertices. We tested our method on several environments with high robot-packing densities (up to $61.6\%$ of the workspace). For environments with narrow passages, such density violates the well-separated assumptions made by state-of-the-art MPP planners, while our method achieves an average success rate of $83\%$.
