近最適なマルチロボット経路計画のための効果的なアルゴリズムフレームワーク
An Effective Algorithmic Framework for Near Optimal Multi-Robot Path Planning
連続2次元環境を最適に離散化し、得られた離散計画問題を高速に近最適解くことで、多数ロボットの経路計画を短時間で実現する集中型フレームワークを提案した。
著者: Jingjin Yu, Daniela Rus
分類: cs.RO
原文アブストラクト
We present a centralized algorithmic framework for solving multi-robot path planning problems in general, two-dimensional, continuous environments while minimizing globally the task completion time. The framework obtains high levels of effectiveness through the composition of an optimal discretization of the continuous environment and the subsequent fast, near-optimal resolution of the resulting discrete planning problem. This principled approach achieves orders of magnitudes better performance with respect to both speed and the supported robot density. For a wide variety of environments, our method is shown to compute globally near-optimal solutions for fifty robots in seconds with robots packed close to each other. In the extreme, the method can consistently solve problems with hundreds of robots that occupy over 30% of the free space.
