Constrained Multi-Agent Path Finding on Directed Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929306637172736 |
|---|---|
| author | Ardizzoni, Stefano Consolini, Luca Locatelli, Marco Saccani, Irene |
| author_facet | Ardizzoni, Stefano Consolini, Luca Locatelli, Marco Saccani, Irene |
| contents | 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, and we propose a reduction method to convert them to standard MP and MAPF. This reduction method consists in finding a subset of nodes W and a reduced graph G/W, such that a solution of MAPF on G/W provides a solution of C-MAPF on G. Moreover, we study the problem of finding W of maximum cardinality, which is strongly NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_12506 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Constrained Multi-Agent Path Finding on Directed Graphs Ardizzoni, Stefano Consolini, Luca Locatelli, Marco Saccani, Irene Multiagent Systems 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, and we propose a reduction method to convert them to standard MP and MAPF. This reduction method consists in finding a subset of nodes W and a reduced graph G/W, such that a solution of MAPF on G/W provides a solution of C-MAPF on G. Moreover, we study the problem of finding W of maximum cardinality, which is strongly NP-hard. |
| title | Constrained Multi-Agent Path Finding on Directed Graphs |
| topic | Multiagent Systems |
| url | https://arxiv.org/abs/2209.12506 |