.png){kind=icon}
.png){kind=icon}
Return
Constrained Motion Planning and Multi-Agent Path Finding on directed graphs☆
.png){kind=icon}
OA
AI
DOI：10.1016/j.automatica.2024.111593.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We discuss C -MP and C -MAPF, generalizations of the classical Motion Planning (MP) and Multi-Agent Path Finding (MAPF) problems on a directed graph G . Namely, we enforce an upper bound on the number of agents that occupy each member of a family of vertex subsets. For instance, this constraint allows maintaining a safety distance between agents. We prove that finding a feasible solution of C -MP and C -MAPF is NP-hard. Also, we propose a method to convert these problems to standard MP and MAPF by strengthening the constraints. The method consists in finding a subset of vertices W and a reduced graph G W , such that a feasible solution of MP and MAPF on G W provides, in polynomial time, a feasible solution of C -MP and C -MAPF on G . However, since the conversion into standard MP and MAPF is obtained by strengthening constraints, feasible solutions of C -MP and C -MAPF on G may exist even if MP and MAPF on G W do not admit any feasible solution. We also study the problem of finding W of maximum cardinality. First, we show that such problem is strongly NP-hard. Then, we propose a heuristic approach for its solution. (c) 2024 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
FEASIBILITY
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.