论文标题
具有最短路径标准的瓶颈任务分配认证
Certification of Bottleneck Task Assignment with Shortest Path Criteria
论文作者
论文摘要
最小化具有可互换目标的一组移动机器人的最长旅行距离需要了解所有机器人和目标目的地之间的最短路径。但是，确定具有障碍物环境中最短路径的确切长度是NP-固定的。在本文中，我们研究了最短路径搜索的多项式时间近似何时足以确定机器人对目标的最佳分配。特别是，我们提出了一种算法，其中路径计划的准确性在迭代上提高。当对最短路径的估计的不确定性变得足够小以确保目标分配的最佳性时，该方法提供了证书。为此，我们采用分配灵敏度的结果，假设最短路径的上限上的上限和下限。然后，我们提供多项式时间方法来通过应用基于抽样的路径计划来找到此类界限。上限由可行的路径给出，下限是通过扩展样品集并利用样品分散的知识来获得的。我们证明了该方法与多机器人路径规划案例研究的应用。
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.
