Optimal and Bounded-Suboptimal Multi-Agent Motion Planning

doi:10.1609/socs.v10i1.18501

Optimal and Bounded-Suboptimal Multi-Agent Motion Planning

2021-09-01

0

OA

AI

DOI：10.1609/socs.v10i1.18501

原文链接

原文求助

摘要

En 中文

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.

Optimal and Bounded-Suboptimal Multi-Agent Motion Planning

摘要

期刊

机构

引用论文