Exploiting Geometric Constraints in Multi-Agent Pathfinding

Atzmon, Dor; Bernardini, Sara; Fagnani, Fabio; Fairbairn, David

Abstract

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.

Citation

Atzmon, D., Bernardini, S., Fagnani, F., & Fairbairn, D. (2023, July). Exploiting Geometric Constraints in Multi-Agent Pathfinding. Presented at Thirty-Third International Conference on Automated Planning and Scheduling, Prague, Czech Republic

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Thirty-Third International Conference on Automated Planning and Scheduling
• Start Date: Jul 8, 2023
• End Date: Jul 13, 2023
• Acceptance Date: Feb 3, 2023
• Online Publication Date: Jul 1, 2023
• Publication Date: 2023
• Deposit Date: Sep 29, 2023
• Publicly Available Date: Sep 29, 2023
• Publisher: AAAI Press
• Volume: 33
• Pages: 17-25
• Series ISSN: 2334-0835
• Book Title: Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling
• ISBN: 9781577358817
• DOI: https://doi.org/10.1609/icaps.v33i1.27174
• Public URL: https://durham-repository.worktribe.com/output/1753275