Hostname: page-component-f554764f5-246sw Total loading time: 0 Render date: 2025-04-20T23:49:53.689Z Has data issue: false hasContentIssue false
  • English
  • Français

RH-ECBS: enhanced conflict-based search for MRPP with region heuristics

Part of: The 40th Anniversary of Robotica

Published online by Cambridge University Press:  27 August 2024

Zhangchao Pan Open the ORCID record for Zhangchao Pan [Opens in a new window] ,
Runhua Wang ,
Qingchen Bi ,
Xuebo Zhang  and
Jingjin Yu Open the ORCID record for Jingjin Yu [Opens in a new window]
Zhangchao Pan
Affiliation:
College of Artificial Intelligence, Nankai University, Tianjin, China
Runhua Wang*
Affiliation:
College of Artificial Intelligence, Nankai University, Tianjin, China
Qingchen Bi
Affiliation:
College of Artificial Intelligence, Nankai University, Tianjin, China
Xuebo Zhang
Affiliation:
College of Artificial Intelligence, Nankai University, Tianjin, China
Jingjin Yu
Affiliation:
Rutgers University New Brunswick, Computer Science New Brunswick, New Brunswick, USA
*
Corresponding author: Runhua Wang; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper proposes a novel two-layer framework based on conflict-based search and regional divisions to improve the efficiency of multi-robot path planning. The high-level layer targets the reduction of conflicts and deadlocks, while the low-level layer is responsible for actual path planning. Distinct from previous dual-level search frameworks, the novelties of this work are (1) subdivision of planning regions for each robot to decrease the number of conflicts encountered during planning; (2) consideration of the number of robots in the region during planning in the node expansion stage of A*, and (3) formal proof demonstrating the nonzero probability of the proposed method in obtaining a solution, along with providing the upper bound of the solution in a special case. Experimental comparisons with Enhanced Conflict-Based Search demonstrate that the proposed method not only reduces the number of conflicts but also achieves a computation time reduction of over 30%.

Keywords

mobile robotsmulti-robot systemmulti-robot path planningconflict-based search
Type
Research Article
Information
Robotica , Volume 42 , Special Issue 12: The 40th Anniversary of Robotic , December 2024 , pp. 4150 - 4160
Copyright
© The Author(s), 2024. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Li, J., Chen, Z., Harabor, D., Stuckey, P. J. and Koenig, S., “MAPF-LNS2: Fast repairing for multi-agent path finding via large neighborhood search,” Proceed AAAI Conf Artif Intell 36(9), 10256–10265 (2022).Google Scholar
Bi, Q., Zhang, X., Wen, J., Pan, Z., Zhang, S., Wang, R. and Yuan, J., “CURE: A hierarchical framework for multi-robot autonomous exploration inspired by centroids of unknown regions,” IEEE Trans Autom Sci Eng 99, 1–14 (2023).Google Scholar
Yu, J. and LaValle, S., “Structure and intractability of optimal multi-robot path planning on graphs,” Proceed AAAI Conf Artif Intell 27(1), 1443–1449 (2013).Google Scholar
Huang, T., Li, J., Koenig, S. and Dilkina, B., “Anytime multi-agent path finding via machine learning-guided large neighborhood search,” Proceed AAAI Conf Artif Intell 36(9), 9368–9376 (2022).Google Scholar
Ryan, M. R. K., “Exploiting subgraph structure in multi-robot path planning,” J Artif Intell Res 31, 497–542 (2008).CrossRefGoogle Scholar
Standley, T., “Finding optimal solutions to cooperative pathfinding problems,” Proceed AAAI Conf Artif Intell 24(1), 173–178 (2010).Google Scholar
Standley, T. and Korf, R., “Complete Algorithms for Cooperative Pathfinding Problems,” In: IJCAI, (2011).Google Scholar
Wagner, G. and Choset, H., “M*: A Complete Multirobot Path Planning Algorithm with Performance Bounds,” In: 2011 IEEE/RSJ international conference on intelligent robots and systems. IEEE, (2011).Google Scholar
Ferner, C., Wagner, G. and Choset, H., “ODrM* Optimal Multirobot Path Planning in Low Dimensional Search Spaces,” In: 2013 IEEE international conference on robotics and automation. IEEE, (2013).CrossRefGoogle Scholar
Sharon, G., Stern, R., Felner, A. and Sturtevant, N. R., “Conflict-based search for optimal multi-agent pathfinding,” Artif Intell 219, 40–66 (2015).CrossRefGoogle Scholar
Sharon, G., Stern, R., Goldenberg, M. and Felner, A., “The increasing cost tree search for optimal multi-agent pathfinding,” Artif Intell 195, 470–495 (2013).CrossRefGoogle Scholar
Boyarski, E., Felner, A., Stern, R., Sharon, G., Betzalel, O., Tolpin, D. and Shimony, E., “Icbs: The improved conflict-based search algorithm for multi-agent pathfinding,” Proceed Int Symp Combin Sear 6(1), 223–225 (2015).Google Scholar
Felner, A., Li, J., Boyarski, E., Ma, H., Choren, L., Satish Kumar, T. K. and Koenig, S., “Adding heuristics to conflict-based search for multi-agent path finding,” Proceed Int Conf Autom Plan Sched 28, (2018).Google Scholar
Barer, M., Sharon, G., Stern, R. and Felner, A., “Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem,” Proceed Int Symp Combin Sear 5(1), 19–27 (2014).Google Scholar
Li, J., Ruml, W. and Koenig, S., “EECBS: A bounded-suboptimal search for multi-agent path finding,” Proceed AAAI Conf Artif Intell 35(14), 12353–12362 (2021).Google Scholar
Szegedy, M. and Yu, J., “Rubik tables and object rearrangement,” Int J Rob Res 42(6), 459–472 (2023).CrossRefGoogle Scholar
Guo, T. and Yu, J., “Sub-1.5 time-optimal multi-robot path planning on grids in polynomial time, “(2022) arXiv preprint arXiv: 2201.08976.Google Scholar
Fiorini, P. and Shiller, Z., “Motion planning in dynamic environments using velocity obstacles,” Int J Rob Res 17(7), 760–772 (1998).CrossRefGoogle Scholar
Van den, B., Jur, M. L. and Manocha, D., “Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation,” In: 2008 IEEE international conference on robotics and automation, (2008).CrossRefGoogle Scholar
van den Berg, J., Guy, S. J., Lin, M. and Manocha, D., “Reciprocal n-Body Collision Avoidance,” In: Robotics Research: The 14th International Symposium ISRR, (2011).CrossRefGoogle Scholar
Alonso-Mora, J., Breitenmose, A., Rufli, M., Beardsley, P. and Siegwart, R., “Optimal Reciprocal Collision Avoidance for Multiple Non-Holonomic Robots,” In: Distributed autonomous robotic systems: The 10th international symposium, (2013).CrossRefGoogle Scholar
Snape, J., van den Berg, J., Guy, S. J. and Manocha, D., “The hybrid reciprocal velocity obstacle,” IEEE Trans Robot 27(4), 696–706 (2011).CrossRefGoogle Scholar
Yang, Y., Juntao, L. and Lingling, P., “Multi-robot path planning based on a deep reinforcement learning DQN algorithm,” CAAI Trans Intell Technol 5(3), 177–183 (2020).CrossRefGoogle Scholar
Li, Q., Gama, F., Ribeiro, A. and Porok, A., “Graph Neural Networks for Decentralized Multi-Robot Path Planning,” In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, (2020).CrossRefGoogle Scholar
Han, R., Chen, S., Wang, S., Zhang, Z., Gao, R., Hao, Q. and Pan, J., “Reinforcement learned distributed multi-robot navigation with reciprocal velocity obstacle shaped rewards,” IEEE Rob Autom Lett 7(3), 5896–5903 (2022).CrossRefGoogle Scholar
Long, P., Fan, T., Liao, X., Liu, W., Zhang, H. and Pan, J., “Towards Optimally Decentralized Multi-Robot Collision Avoidance Via Deep Reinforcement Learning,” In: 2018 IEEE international conference on robotics and automation (ICRA). IEEE, (2018).CrossRefGoogle Scholar
Chan, S.-H., Li, J., Gange, G., Harabor, D., Stuckey, P. J. and Koenig, S., “ECBS with flex distribution for bounded-suboptimal multi-agent path finding,” Proceed Int Symp Combin Sear 12(1), 159–161 (2021).Google Scholar
Li, J., Ran, M. and Xie, L., “Efficient trajectory planning for multiple non-holonomic mobile robots via prioritized trajectory optimization,” IEEE Rob Autom Lett 6(2), 405–412 (2020).CrossRefGoogle Scholar