Multi-Agent Path Finding on Strongly Connected Digraphs: feasibility and solution algorithms

Fuente: arXiv
Guardado en:
Detalles Bibliográficos
Autores principales: Ardizzoni, Stefano, Saccani, Irene, Consolini, Luca, Locatelli, Marco
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