Scalable Multi-Agent Path Finding for Delivery Robot Systems with Temporal and Edge Capacity Constraints on Weighted Graphs
The Multi-Agent Path Finding (MAPF) problem on a graph is a fundamental research topic in robotics. This paper formulates a mathematical problem that not only captures path finding in traditional MAPF but also incorporates constraints related to weighted graphs, deadlines, and edge capacity considerations. The feasibility of this formulation is demonstrated and compared with Mixed Integer Linear Programming, Satisfiability Modulo Theories, and OR-Tools, focusing on scalability within a realistic delivery robot system.
Authors
- Ippei Nishitani
- Bardh Hoxha (ORCID: https://orcid.org/0000-0001-6255-7566)
- Tomoya Yamaguchi (ORCID: https://orcid.org/0000-0002-6536-7001)
- Georgios Fainekos (ORCID: https://orcid.org/0000-0002-0456-2129)
- Yusuke Ota (ORCID: https://orcid.org/0000-0001-5815-1328)
Institutions
- Toyota Motor North America (United States) (US)
- Toyota Motor Corporation (Japan) (JP)
Publication Details
- Published
- 2025-08-17
- DOI
- https://doi.org/10.1109/case58245.2025.11164139
- Primary Topic
- Robotic Path Planning Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00