グラフ上の複数ロボットの最適経路計画
Planning Optimal Paths for Multiple Robots on Graphs
グラフ上の複数ロボット経路計画をマルチフロー整数線形計画で定式化し、最終到着時刻最小と総距離最小の最適解を保証する完全アルゴリズムを提案した。
著者: Jingjin Yu, Steven M. LaValle
分類: cs.RO, cs.AI, cs.SY, eess.SY
原文アブストラクト
In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that computes minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.
