.png){kind=icon}
.png){kind=icon}
Return
Multi-agent pathfinding on strongly connected digraphs: Feasibility and solution algorithms
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2025.104372.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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, we describe a procedure that checks the problem feasibility in linear time with respect to the number of vertices n, and we find a necessary and sufficient condition for feasibility of any MAPF instance. Moreover, we present an algorithm (diSC) that provides a feasible solution of length O(kn2c), where k is the number of agents and c the maximum length of the corridors of the graph.
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W