Scalable Iterative Multi-Agent Path Finding under Turn Constraints
Organizations: School of Mechanical Engineering, Tongji University, Caoan Road 4800, 201804, Shanghai, China
Abstract
Large-scale multi-mobile-robot systems require fast and reliable path planning under realistic motion constraints. Multi-Agent Path Finding with turn actions (MAPF) explicitly models orientation changes and turn-induced delays, but these constraints increase the computational burden of search-based methods. Priority-inheritance-based planning offers a highly scalable alternative, yet directly extending it to MAPF is nontrivial because turn actions break the immediate node-vacation assumption underlying conventional priority inheritance. To address this challenge, this paper proposes PIBT, an efficient iterative solver for MAPF. PIBT advances scalable multi-agent coordination by preserving the lightweight single-timestep planning mechanism of Priority Inheritance with Backtracking (PIBT), while introducing dedicated mechanisms to handle turn-induced dependencies, local deadlocks, livelock, and inefficient repeated pushing. Experiments on standard MAPF benchmarks show that PIBT achieves high success rates and strong scalability, solving instances with up to 1000 agents within seconds. For realistic engineering environments, Action Dependency Graph (ADG)-based execution simulation and a flexible manufacturing system case study show that turn-aware planning better reflects robot execution and reduces actual makespan compared with classical MAPF planning. Experiments with TurtleBot4 robots further validate the practical feasibility of the proposed method.
Figures & tables
| Map | ||||||
|---|---|---|---|---|---|---|
| 0 | 3.25% | 4.42% | 8.08% | 10.50% | 29.42% | |
| 4.63% | 0 | 0.84% | 2.43% | 2.99% | 4.19% | |
| 6.59% | 0.64% | 0 | 2.61% | 0.86% | 1.41% | |
| 0 | 0.02% | 0.40% | 0.25% | 1.94% | 36.26% | |
| 0 | 0.11% | 0.11% | 0 | 0.11% | 2.27% |
| Map | Sum of Costs | Makespan | ||
|---|---|---|---|---|
| Mean SD | CV | Mean SD | CV | |
| 2.42% | 6.74% | |||
| 5.13% | 13.08% | |||
| 2.39% | 4.55% | |||
| 0.17% | 0.32% | |||
| 0.38% | 0.26% | |||
| Map | Method | Number of agents | ||||||
|---|---|---|---|---|---|---|---|---|
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | ||
| Empty | PIBT | 4 | 7 | 10 | 14 | 17 | 21 | 25 |
| CBS T | 1 | 5 | 15 | 63 | 533 | 4433 | 13244 | |
| Random | PIBT | 4 | 7 | 10 | 14 | 17 | 22 | 26 |
| CBS T | 4 | 44 | 3900 | 20464 | 32508 | - | - | |
| Room | PIBT | 12 | 23 | 33 | 44 | 59 | 75 | 83 |
Multi-Agent Path Finding
Multi-agent path finding (MAPF) plans collision-free routes for multiple agents sharing an environment.
See all 104 papers