Optimal and Bounded-Suboptimal Multi-Agent Motion Planning
Optimal and Bounded-Suboptimal Multi-Agent Motion Planning
复制标题
最优和有界次优多智能体运动规划
DOI：
10.1609/socs.v10i1.18501
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Sven Koenig
中科院分区：
文献类型：
--
作者：
L. Cohen;T. Uras;T. K. S. Kumar;Sven Koenig
多代理运动计划（MAMP）是从一开始到目标状态寻找无冲突的动力学可行计划的任务。尽管MAMP具有重要的实际重要性，但现有的求解器要么不完整，效率低下，要么依赖于简化假设。例如，多代理路径查找（MAPF）求解器常规假定剂量的离散时间段和直线运动在图形的相邻顶点之间。在本文中，我们开发了MAMP求解器，以消除这些简化的假设，但概括了最先进的MAPF求解器的核心思想。具体而言，由于不同的动作可能需要任意不同的持续时间，因此MAMP求解器需要有效地推理不断的时间和任意等待持续时间。为此，我们适应（增强）基于冲突的搜索来连续时间，并开发出新型的安全间隔路径计划的界限扩展，称为软冲突间隔路径计划。从理论方面来说，我们证明了我们的MAMP求解器的完整性，最佳性和有限的 - 求和性。在实验方面，我们表明我们的MAMP求解器随着次优度的增加而良好。
Multi-Agent Motion Planning (MAMP) is the task of finding conflict-free kinodynamically feasible plans for agents from start to goal states. While MAMP is of significant practical importance, existing solvers are either incomplete, inefficient or rely on simplifying assumptions. For example, Multi-Agent Path Finding (MAPF) solvers conventionally assume discrete timesteps and rectilinear movement of agents between neighboring vertices of a graph. In this paper, we develop MAMP solvers that obviate these simplifying assumptions and yet generalize the core ideas of state-of-the-art MAPF solvers. Specifically, since different motions may take arbitrarily different durations, MAMP solvers need to efficiently reason with continuous time and arbitrary wait durations. To do so, we adapt (Enhanced) Conflict-Based Search to continuous time and develop a novel bounded-suboptimal extension of Safe Interval Path Planning, called Soft Conflict Interval Path Planning. On the theoretical side, we justify the completeness, optimality and bounded-suboptimality of our MAMP solvers. On the experimental side, we show that our MAMP solvers scale well with increasing suboptimality bounds.