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

Fuente: arXiv
Salvato in:
Dettagli Bibliografici
Autori principali: Ardizzoni, Stefano, Saccani, Irene, Consolini, Luca, Locatelli, Marco
Natura: Preprint
Pubblicazione: 2022
Soggetti:
Accesso online:
Tags: Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
_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