A Scalable Post-Processing Pipeline for Large-Scale Free-Space Multi-Agent Path Planning with PIBT

Arjo Chakravarty; Michael X. Grey; M. A. Viraj J. Muthugala; Rajesh Mohan Elara

doi:10.3390/math14071195

journal article Open Access Apr 03, 2026

A Scalable Post-Processing Pipeline for Large-Scale Free-Space Multi-Agent Path Planning with PIBT

Arjo Chakravarty

Michael X. Grey M. A. Viraj J. Muthugala

Rajesh Mohan Elara

Mathematics Vol. 14 No. 7 pp. 1195 · MDPI AG

View at Publisher Save 10.3390/math14071195

Abstract

Free-space multi-agent path planning remains challenging at large scales. Most existing methods either offer optimality guarantees but do not scale beyond a few dozen agents or rely on grid-world assumptions that do not generalize well to continuous space. In this paper, we propose a hybrid, rule-based planning framework that combines Priority Inheritance with Backtracking (PIBT) with a novel safety-aware path smoothing method. Our approach extends PiBT to eight-connected grids and selectively applies string-pulling-based smoothing while preserving collision safety through local interaction awareness and a fallback collision resolution step based on Safe Interval Path Planning (SIPP). This design allows us to reduce overall path lengths while maintaining real-time performance. We demonstrate that our method can scale to over 500 agents in large free-space environments, outperforming existing any-angle and optimal methods in terms of runtime, while producing near-optimal trajectories in sparse domains. Our results suggest this framework is a promising building block for scalable, real-time multi-agent navigation in robotics systems operating beyond grid constraints.

Topics

No keywords indexed for this article. Browse by subject →

References

26

[1]

Okumura "Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding" Artif. Intell. (2022) 10.1016/j.artint.2022.103752

[2]

Yakovlev, K., Andreychuk, A., and Stern, R. (2024). Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding. Proceedings of the 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE. 10.1109/iros58592.2024.10801691

[3]

Macenski, S., Martin, F., White, R., and Ginés Clavero, J. (2020, January 25–29). The Marathon 2: A Navigation System. Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, USA. 10.1109/iros45743.2020.9341207

[4]

Conflict-based search for optimal multi-agent pathfinding

Guni Sharon, Roni Stern, Ariel Felner et al.

Artificial Intelligence 2015 10.1016/j.artint.2014.11.006

[5]

Li "Eecbs: A bounded-suboptimal search for multi-agent path finding" Proceedings of the AAAI Conference on Artificial Intelligence (2021) 10.1609/aaai.v35i14.17466

[6]

Shaoul, Y., Mishani, I., Vats, S., Li, J., and Likhachev, M. (2024). Multi-robot motion planning with diffusion models. arXiv.

[7]

Gordon, O., Filmus, Y., and Salzman, O. (2021). Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds. Proceedings of the Fourteenth International Symposium on Combinatorial Search, SOCS 2021, Online, 16–18 July 2021, AAAI Press. 10.1609/socs.v12i1.18552

[8]

Okumura, K. (2023). LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI Press. 10.1609/aaai.v37i10.26377

[9]

Surynek, P. (2022). Problem Compilation for Multi-Agent Path Finding: A Survey. Proceedings of the IJCAI, Curran Associates, Inc. 10.24963/ijcai.2022/783

[10]

Surynek "Sub-optimal sat-based approach to multi-agent path-finding problem" Proceedings of the International Symposium on Combinatorial Search (2018) 10.1609/socs.v9i1.18456

[11]

Sartoretti "Primal: Pathfinding via reinforcement and imitation multi-agent learning" IEEE Robot. Autom. Lett. (2019) 10.1109/lra.2019.2903261

[12]

Wang, Y., Xiang, B., Huang, S., and Sartoretti, G. (2023). Scrimp: Scalable communication for reinforcement-and imitation-learning-based multi-agent pathfinding. Proceedings of the 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE. 10.1109/iros55552.2023.10342305

[13]

MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale

Anton Andreychuk, Konstantin Yakovlev, Aleksandr Panov et al.

Proceedings of the AAAI Conference on Artificial I... 2025 10.1609/aaai.v39i22.34477

[14]

Chan, S.H., Chen, Z., Guo, T., Zhang, H., Zhang, Y., Harabor, D., Koenig, S., Wu, C., and Yu, J. (2024, January 1–6). The League of Robot Runners Competition: Goals, Designs, and Implementation. Proceedings of the ICAPS 2024 System’s Demonstration Track, Banff, AB, Canada.

[15]

Stern "Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks" Symp. Comb. Search (SoCS) (2019)

[16]

(2025, April 23). GitHub—open-rmf/mapf: Multi-Agent (Path Finding) Planning Framework—github.com. Available online: https://github.com/open-rmf/mapf.

[17]

Li "MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search" Proceedings of the AAAI Conference on Artificial Intelligence (2022) 10.1609/aaai.v36i9.21266

[18]

Nash "Theta*: Any-angle path planning on grids" Proceedings of the AAAI (2007)

[19]

Nash "Lazy Theta*: Any-angle path planning and path length analysis in 3D" Proceedings of the AAAI Conference on Artificial Intelligence (2010) 10.1609/aaai.v24i1.7566

[20]

Cui "Direction oriented pathfinding in video games" Int. J. Artif. Intell. Appl. (2011)

[21]

Van den Berg, J., Lin, M., and Manocha, D. (2008). Reciprocal velocity obstacles for real-time multi-agent navigation. Proceedings of the 2008 IEEE International Conference on Robotics and Automation, IEEE. 10.1109/robot.2008.4543489

[22]

Alonso-Mora, J., Breitenmoser, A., Rufli, M., Beardsley, P., and Siegwart, R. (2013). Optimal reciprocal collision avoidance for multiple non-holonomic robots. Proceedings of the Distributed Autonomous Robotic Systems: The 10th International Symposium, Springer. 10.1007/978-3-642-32723-0_15

[23]

Nash, A. (2012). Any-Angle Path Planning. [Ph.D. Thesis, University of Southern California].

[24]

Surynek, P. (2010). An Optimization Variant of Multi-Robot Path Planning Is Intractable. Proceedings of the AAAI, AAAI Press. 10.5772/12906

[25]

Phillips, M., and Likhachev, M. (2011). Sipp: Safe interval path planning for dynamic environments. Proceedings of the 2011 IEEE International Conference on Robotics and Automation, IEEE. 10.1109/icra.2011.5980306

[26]

Gao, Z., Yang, G., and Prorok, A. (2023). Online control barrier functions for decentralized multi-agent navigation. Proceedings of the 2023 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), IEEE. 10.1109/mrs60187.2023.10416796

Metrics

0

Citations

26

References

Details

Published: Apr 03, 2026
Vol/Issue: 14(7)
Pages: 1195
License: View

Authors

A

Arjo Chakravarty

Intrinsic LLC, 438A Alexandra Road, #04-11/12 Block A, Alexandra Technopark, Singapore 119967, Singapore; Engineering Product Development Pillar, Singapore University of Technology and Design, 8 Somapah Road, Singapore 487372, Singapore

M

Michael X. Grey

Intrinsic LLC, 438A Alexandra Road, #04-11/12 Block A, Alexandra Technopark, Singapore 119967, Singapore

M

M. A. Viraj J. Muthugala

Engineering Product Development Pillar, Singapore University of Technology and Design, 8 Somapah Road, Singapore 487372, Singapore

R

Rajesh Mohan Elara

Engineering Product Development Pillar, Singapore University of Technology and Design, 8 Somapah Road, Singapore 487372, Singapore

Funding

A*STAR Award: M24N2a0039

National Robotics Programme Award: M25N4N2028

Cite This Article

Arjo Chakravarty, Michael X. Grey, M. A. Viraj J. Muthugala, et al. (2026). A Scalable Post-Processing Pipeline for Large-Scale Free-Space Multi-Agent Path Planning with PIBT. Mathematics, 14(7), 1195. https://doi.org/10.3390/math14071195

A Scalable Post-Processing Pipeline for Large-Scale Free-Space Multi-Agent Path Planning with PIBT

You May Also Like