Multi-Agent Path Finding on Strongly Connected Digraphs: feasibility and solution algorithms
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917634266628096 |
|---|---|
| author | Ardizzoni, Stefano Saccani, Irene Consolini, Luca Locatelli, Marco |
| author_facet | Ardizzoni, Stefano Saccani, Irene Consolini, Luca Locatelli, Marco |
| contents | On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists in finding paths for multiple agents, avoiding collisions. Finding the minimum-length solution is known to be NP-hard, and computation times grows exponentially with the number of agents. However, in industrial applications, it is important to find feasible, suboptimal solutions, in a time that grows polynomially with the number of agents. Such algorithms exist for undirected and biconnected directed graphs. Our main contribution is to generalize these algorithms to the more general case of strongly connected directed graphs. In particular, given a MAPF problem with at least two holes, we present an algorithm that checks the problem feasibility in linear time with respect to the number of nodes, and provides a feasible solution in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_04286 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Multi-Agent Path Finding on Strongly Connected Digraphs: feasibility and solution algorithms Ardizzoni, Stefano Saccani, Irene Consolini, Luca Locatelli, Marco Multiagent Systems Robotics On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists in finding paths for multiple agents, avoiding collisions. Finding the minimum-length solution is known to be NP-hard, and computation times grows exponentially with the number of agents. However, in industrial applications, it is important to find feasible, suboptimal solutions, in a time that grows polynomially with the number of agents. Such algorithms exist for undirected and biconnected directed graphs. Our main contribution is to generalize these algorithms to the more general case of strongly connected directed graphs. In particular, given a MAPF problem with at least two holes, we present an algorithm that checks the problem feasibility in linear time with respect to the number of nodes, and provides a feasible solution in polynomial time. |
| title | Multi-Agent Path Finding on Strongly Connected Digraphs: feasibility and solution algorithms |
| topic | Multiagent Systems Robotics |
| url | https://arxiv.org/abs/2209.04286 |