Home » Publication » 28311

Dettaglio pubblicazione

2023, Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling, Pages 17-25 (volume: 33)

Exploiting Geometric Constraints in Multi-Agent Pathfinding (04b Atto di convegno in volume)

Atzmon D., Bernardini S., Fagnani F., Fairbairn D.

In tackling the multi-agent pathfinding problem (MAPF), we study a specific class of paths that are constructed by taking the agents' shortest paths from the start to the goal locations and adding safe delays at the beginning of the paths, which guarantee that they are non-conflicting. Safe delays are calculated by exploiting a set of fundamental geometric constraints among the distances between all agents' start and goal locations. Those constraints are simple, but the MAPF problem reformulated in terms of them remains computationally hard. Nonetheless, based on safe delays, we devise a new, fast and lightweight algorithm, called Delayed Shortest Path (DSP), to find solutions to the MAPF problem. Via an extensive experimental evaluation on standard benchmarks, we show that, in many cases, our technique runs several orders of magnitudes faster than related methods while addressing problems with thousands of agents and returning low-cost solutions.
keywords
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma