最短経路基準によるボトルネックタスク割り当ての認証
Certification of Bottleneck Task Assignment with Shortest Path Criteria
障害物環境での多ロボットの目標割り当てにおいて、最短経路の不確かさが十分小さくなったときに最適性を保証する認証アルゴリズムを提案し、サンプリングベース経路計画で上下界を求める多項式時間手法を示した。
著者: Tony A. Wood, Maryam Kamgarpour
分類: cs.RO, cs.SY, eess.SY, math.OC
原文アブストラクト
Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment with obstacles is NP-hard however. In this paper, we investigate when polynomial-time approximations of the shortest path search are sufficient to determine the optimal assignment of robots to goals. In particular, we propose an algorithm in which the accuracy of the path planning is iteratively increased. The approach provides a certificate when the uncertainties on estimates of the shortest paths become small enough to guarantee the optimality of the goal assignment. To this end, we apply results from assignment sensitivity assuming upper and lower bounds on the length of the shortest paths. We then provide polynomial-time methods to find such bounds by applying sampling-based path planning. The upper bounds are given by feasible paths, the lower bounds are obtained by expanding the sample set and leveraging the knowledge of the sample dispersion. We demonstrate the application of the proposed method with a multi-robot path-planning case study.
