Large-scale multi-mobile-robot systems require fast and reliable path planning under realistic motion constraints. Multi-Agent Path Finding with turn actions (MAPFT) 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 MAPFT is nontrivial because turn actions break the immediate node-vacation assumption underlying conventional priority inheritance. To address this challenge, this paper proposes PIBTT∗, an efficient iterative solver for MAPFT. PIBTT∗ 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 PIBTT∗ 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
Figure 1: Paths generated by a classical MAPF solver and a high-level MAPF T solver.
Figure 2: An MAPF T instance solved by the proposed method.
Figure 3: (a) An instance of cycle. (b) Cycle is handled by proposed approach.
Figure 4: Cycle handling approach
Figure 5: Deadlock in PIBT and swap process
Figure 6: Agent at its goal is continuously pushed away.
Map
k=1
k=2
k=3
k=4
k=5
k=∞
Empty
0
3.25%
4.42%
8.08%
10.50%
29.42%
Random
4.63%
0
0.84%
2.43%
2.99%
4.19%
Room
6.59%
0.64%
0
2.61%
0.86%
1.41%
Warehouse
0
0.02%
0.40%
0.25%
1.94%
36.26%
Den520d
0
0.11%
0.11%
0
0.11%
2.27%
Table 1: Makespan gaps under different PET threshold values k for 100-agent instances.
Map
Sum of Costs
Makespan
Mean ± SD
CV
Mean ± SD
CV
Empty
3386.9±82.0
2.42%
57.2±3.9
6.74%
Random
5891.4±302.5
5.13%
116.9±15.3
13.08%
Room
10175.5±242.9
2.39%
166.9±7.6
4.55%
Warehouse
11539.7±20.1
0.17%
211.3±0.7
0.32%
Den520d
17685.7±67.5
0.38%
402.2±1.0
0.26%
Table 2: Variability of solution quality with different random seeds ( ∣A∣=100 , 10 runs)
Figure 7: Ablation study of the PET and SPD modules on benchmark maps under different numbers of agents.
Figure 8: Success rates of CBS T , PIBT T , and PIBT T* , together with the SoC and makespan ratios of PIBT T and PIBT T* relative to the CBS T reference solutions.
Map
Method
Number of agents
10
20
30
40
50
60
70
Empty
PIBT T*
4
7
10
14
17
21
25
CBS T
1
5
15
63
533
4433
13244
Random
PIBT T*
4
7
10
14
17
22
26
CBS T
4
44
3900
20464
32508
-
-
Room
PIBT T*
12
23
33
44
59
75
83
Table 3: Average runtime of PIBT T* and CBS T on five benchmark maps (ms).
Figure 9: Success rate of PIBT T and PIBT T* on the warehouse map with up to 1,000 agents.
Figure 10: Runtime of PIBT T* on the warehouse map with up to 1,000 agents.
Figure 11: Comparison between theoretical planning makespan and ADG-based actual execution makespan for PIBT and PIBT T* .
Figure 12: Example of a FMS layout, where P1 to P10 are parking stations and W1 to W9 are working stations.
Figure 13: Comparison between theoretical planning makespan and actual execution makespan in SMART.
Figure 14: Execution paths of agents a1 , a5 , and a8 in the SMART simulator for instance #1 with 10 agents. The left panel corresponds to PIBT, and the right panel corresponds to PIBT T* .
Figure 15: Real-robot experiment on three TurtleBot 4 robots. (a) Start and goal configuration on the 6×6 map with obstacles. (b) Deadlock between R2 and R3 under PIBT+ADG at t=5 s. (c) R1 reaches its goal under PIBT+ADG at t=41 s, while R2 and R3 remain deadlocked. (d) Successful execution under PIBT T* : R1 reaches its goal at t=32 s, and R2 and R3 reach their goals at approximately t=36 s.
Modern Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second, requiring highly efficient algorithms. Priority Inheritance with Backtracking (PIBT) is a popular algorithm capable of effectively planning in such situations. However, PIBT, and its variants like Enhanced PIBT (EPIBT), is constrained by its rule-based planning procedure and lacks generality because it restricts its search to paths that collide with at most one other agent. In this paper, we describe a new perspective on solving MAPF by planning over agent dependencies. Taking inspiration from PIBT's priority inheritance logic, we define the concept of agent dependencies and propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies. MD-PIBT is a general framework where specific parameterizations can reproduce PIBT and EPIBT. At the same time, alternative configurations generalize PIBT and EPIBT to multi-step planning capable of reasoning paths that collide with more than one other agent. Our experiments demonstrate that MD-PIBT effectively plans for as many as 10,000 homogeneous agents under various kinodynamic constraints, including pebble motion, rotation motion, and differential drive robots with speed and acceleration limits. We perform thorough evaluations on different variants of MAPF and find that MD-PIBT is particularly effective in MAPF with large agents. Our code is available at https://github.com/lunjohnzhang/MD-PIBT.
Zixiang Jiang, Yulun Zhang, Rishi Veerapaneni +1
University Of Melbourne · Robotics Institute, Carnegie Mellon University
The concurrent target assignment and pathfinding (TAPF) problem extends multi-agent pathfinding (MAPF) by asking planners to allocate distinct targets and collision-free paths to agents. Prior work on TAPF has relied exclusively on Conflict-Based Search (CBS), which tightly couples target assignment and pathfinding, resulting in compute-intensive, non-scalable solutions. In contrast, we propose an iterative refinement framework that decouples target assignment from pathfinding. Our framework builds on modern, fast, suboptimal MAPF solvers, such as LaCAM. Specifically, within a given time budget, it repeatedly solves MAPF for the current target assignment, identifies bottleneck agents via MAPF feedback, and refines the assignment. Empirical results show that feedback-driven reassignment loop is effective, enabling our framework to scale well beyond the reach of the state-of-the-art CBS-based solver while maintaining decent solution quality. This represents a solid step toward practical, large scale TAPF suitable for real-world setups.
Yu Kumagai, Keisuke Okumura
1Hitotsubashi University, Japan · 2National Institute of Advanced Industrial Science and Technology (AIST), Japan
Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph, often with the objective of minimizing the sum-of-costs (SOC). Many optimal and bounded-suboptimal solvers rely on time-expanded models and centralized conflict resolution, which limits scalability in large or dense instances. We propose a hybrid prioritized framework that separates geometric planning from execution-time conflict resolution. In the first stage, Geometric Conflict Preemption (GCP) plans agents sequentially with A* on the original graph while inflating costs for transitions entering vertices used by higher-priority paths, encouraging spatial detours without explicit time reasoning. In the second stage, a Decentralized Local Controller (DLC) executes the geometric paths using per-vertex FIFO authorization queues and inserts wait actions to avoid vertex and edge-swap conflicts. Experiments on standard benchmark maps with up to 1000 agents show that the method scales with an near-linear runtime trend and attains a 100% success rate on instances satisfying the geometric feasibility assumption. Page of the project: https://sites.google.com/unizar.es/multi-agent-path-finding/home
Fernando Salanova, Eduardo Montijano, Cristian Mahulea
Dept. of Systems Engineering and Computer Science, University of Zaragoza, Zaragoza, Spain