Algorithm

Computational complexity theory

Multi-agent system

Theoretical computer science

Time complexity

Set (abstract data type)

Scalability

Computer science

Mathematical optimization

Completeness (order theory)

Distributed computing

Database

Graph

Mathematics

Mathematical analysis

Artificial intelligence

Pathfinding

Programming language

Shortest path problem

Proceedings of the International Symposium on Combinatorial Search

Multi-agent pathfinding is a challenging combinatorial problem that involves multiple agents moving on a graph from a set of initial nodes to a set of desired goals without inter-agent collisions. Searching the composite space of all agents has exponential complexity and does not scale well. Decoupled methods are more efficient but are generally incomplete. There are, however, polynomial time algorithms, which utilize single or few-agents primitives with completeness guarantees. One limitation of these alternatives is that the resulting solution is sequential, where only one agent moves at a time. Such solutions are of low quality when compared to methods where multiple agents can move simultaneously. This work proposes an algorithm for multi-agent pathfinding that utilizes similar single-agent primitives but allows all agents to move in parallel. The paper describes the algorithm and its properties. Experimental comparisons suggest that the resulting paths are considerably better than sequential ones, even after a post-processing, parallelization step, as well as solutions returned by decoupled and coupled alternatives. The experiments also suggest good scalability and competitive computational performance.

Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives