cs.RONov 18, 2026

Scalable Iterative Multi-Agent Path Finding under Turn Constraints

Authors: Zheyu Tao, Chunlong Yu, Yicheng Hu

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 (MAPFT_T) 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_T is nontrivial because turn actions break the immediate node-vacation assumption underlying conventional priority inheritance. To address this challenge, this paper proposes PIBTT∗^*_T, an efficient iterative solver for MAPFT_T. PIBTT∗^*_T 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∗^*_T 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

Explore similar work

CardsList
  1. Planning over MAPF Agent Dependencies via Multi-Dependency PIBT

    Mar 24, 2026Zixiang Jiang, Yulun Zhang, Rishi Veerapaneni +1Kinodynamic Motion PlanningMotion Planning

  2. Alternating Target-Path Planning for Scalable Multi-Agent Coordination

    May 8, 2026Yu Kumagai, Keisuke OkumuraMulti-Agent CoordinationMulti-Robot Task Allocation

  3. Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding

    Mar 11, 2026Fernando Salanova, Eduardo Montijano, Cristian MahuleaMulti-Agent PlanningMulti-Agent Path Finding