Low-energy Multi-robot Path Planning Algorithm under HCA* Framework

doi:10.16182/j.issn1004731x.joss.24-0515

Abstract

Abstract:

To address the energy optimization problem in multi-robot path planning, this paper proposed a multi-robot path planning algorithm based on the energy-guided hierarchical cooperative A* (E-HCA*) algorithm. To address the issue of robot oscillations caused by mutual avoidance at bottlenecks and narrow passages in multi-robot systems, a node expansion method with path length as a secondary feature was introduced, and a greedy suppression strategy under the cooperative A* framework was proposed. A differential-drive robot energy consumption model was established, and an energy-guided heuristic function was constructed by integrating energy metrics into the underlying A* algorithm to guide low-energy path planning. The results show that the proposed algorithm effectively solves the oscillating path problem, achieving a shorter sum of length and lower sum of energy compared to existing algorithms, thereby improving path quality.

Key words: multi-robot, path planning, energy optimization, guided A* planning

CLC Number:

TP242

Wang Ning, Mao Jianlin, Li Dayan, Fang Chengyuan, Qian Chengze. Low-energy Multi-robot Path Planning Algorithm under HCA* Framework[J]. Journal of System Simulation, 2025, 37(10): 2630-2642.

Figures/Tables 17

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 1

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Table 2

Fig. 11

Fig. 12

Fig. 13

Fig. 14

Fig. 15

References 32

[1]	高明, 唐洪, 张鹏. 机器人集群路径规划技术研究现状[J]. 国防科技大学学报, 2021, 43(1): 127-138.
	Gao Ming, Tang Hong, Zhang Peng. Survey of Path Planning Technologies for Robots Swarm[J]. Journal of National University of Defense Technology, 2021, 43(1): 127-138.
[2]	Zhang Kaixiang, Mao Jianlin, Chen Mingfang, et al. Multi-agent Priority Gaming for Path Planning in Chain-like Blocking Situation[J]. Advanced Engineering Informatics, 2024, 61: 102523.
[3]	Zhang Yulun, Fontaine M C, Bhatt V, et al. Multi-robot Coordination and Layout Design for Automated Warehousing[C]//Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23). California: IJCAI, 2024: 5503-5511.
[4]	Li Jiaoyang, Sun Kexuan, Ma Hang, et al. Moving Agents in Formation in Congested Environments[C]//Proceedings of the Thirteenth International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2021: 131-132.
[5]	Wu Mengdie, Yan Wenyao, Hasan Haslin, et al. A Review of Multi-agent Path Finding Algorithms[C]//2023 11th International Conference on Information Systems and Computing Technology (ISCTech). Piscataway: IEEE, 2023: 69-73.
[6]	Liu Minghua, Ma Hang, Li Jiaoyang, et al. Task and Path Planning for Multi-agent Pickup and Delivery[C]//Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. Richland: International Foundation for Autonomous Agents and Multiagent Systems, 2019: 1152-1160.
[7]	Ma Hang, Yang Jingxing, Cohen L, et al. Feasibility Study: Moving Non-homogeneous Teams in Congested Video Game Environments[C]//Proceedings of the Thirteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Palo Alto: AAAI Press, 2021: 270-272.
[8]	Sharon Guni, Stern Roni, Goldenberg Meir, et al. The Increasing Cost Tree Search for Optimal Multi-agent Pathfinding[J]. Artificial Intelligence, 2013, 195: 470-495.
[9]	Sharon Guni, Stern Roni, Felner Ariel, et al. Conflict-based Search for Optimal Multi-agent Pathfinding[J]. Artificial Intelligence, 2015, 219: 40-66.
[10]	Boyarski Eli, Felner Ariel, Stern Roni, et al. ICBS: The Improved Conflict-based Search Algorithm for Multi-agent Pathfinding[C]//Proceedings of the Eighth International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2015: 223-225.
[11]	Walker T T, Sturtevant Nathan R, Felner Ariel, et al. Conflict-based Increasing Cost Search[C]//Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2021: 385-395.
[12]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
	Xuan Zhiwei, Mao Jianlin, Zhang Kaixiang. Low-expansion A* Algorithm Based on CBS Framework for Complex Map[J]. Acta Electronica Sinica, 2022, 50(8): 1943-1950.
[13]	杨邹, 毛剑琳, 李大焱, 等. 基于冲突概率反馈的CBS分层多机器人路径规划[J/OL]. 计算机集成制造系统. (2023-07-31) [2024-07-01]. .
	Yang Zou, Mao Jianlin, Li Dayan, et al. CBS Hierarchical Multi-robot Path Planning Based on Conflict Probability Feedback[J/OL]. Computer Integrated Manufacturing Systems. (2023-07-31) [2024-07-01]. .
[14]	Silver David. Cooperative Pathfinding[C]//First Artificial Intelligence and Interactive Digital Entertainment Conference. Palo Alto: AAAI Press, 2021: 117-122.
[15]	Phillips M, Likhachev M. SIPP: Safe Interval Path Planning for Dynamic Environments[C]//2011 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2011: 5628-5635.
[16]	Yakovlev Konstantin, Andreychuk Anton, Stern Roni. Revisiting Bounded-suboptimal Safe Interval Path Planning[C]//Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling. Palo Alto: AAAI Press, 2020: 300-304.
[17]	Li Jiaoyang, Ruml W, Koenig S. EECBS: Bounded-suboptimal Search for Multi-agent Path Finding[C]//Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence and the Thirty-Third Conference on Innovative Applications of Artificial Intelligence and the Eleventh Symposium on Educational Advances in Artificial Intelligence. Palo Alto: AAAI Press, 2021: 12353-12362.
[18]	张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的B-IHCA*多机器人路径规划算法[J]. 自动化学报, 2023, 49(7): 1483-1497.
	Zhang Kaixiang, Mao Jianlin, Xiang Fenghong, et al. B-IHCA*, a Bargaining Game Based Multi-agent Path Finding Algorithm[J]. Acta Automatica Sinica, 2023, 49(7): 1483-1497.
[19]	Li Jiaoyang, Hoang T A, Lin E, et al. Intersection Coordination with Priority-based Search for Autonomous Vehicles[C]//Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence. Palo Alto: AAAI Press, 2023: 11578-11585.
[20]	Sartoretti G, Kerr J, Shi Yunfei, et al. PRIMAL: Pathfinding via Reinforcement and Imitation Multi-agent Learning[J]. IEEE Robotics and Automation Letters, 2019, 4(3): 2378-2385.
[21]	Damani M, Luo Zhiyao, Wenzel E, et al. PRIMAL₂: Pathfinding via Reinforcement and Imitation Multi-agent Learning-lifelong[J]. IEEE Robotics and Automation Letters, 2021, 6(2): 2666-2673.
[22]	闫星宇, 李大焱, 王妮娅, 等. 带障碍物惩罚因子的多机器人路径规划[J]. 系统仿真学报, 2024, 36(3): 673-685.
	Yan Xingyu, Li Dayan, Wang Niya, et al. Multi-agent Path Planning with Obstacle Penalty Factor[J]. Journal of System Simulation, 2024, 36(3): 673-685.
[23]	Stern Roni. Multi-agent Path Finding-an Overview[M]//Gennady S Osipov, Aleksandr I Panov, Konstantin S Yakovlev. Artificial Intelligence. Cham: Springer International Publishing, 2019: 96-115.
[24]	Stern Roni, Sturtevant Nathan, Felner Ariel, et al. Multi-agent Pathfinding: Definitions, Variants, and Benchmarks[C]//Proceedings of the International Symposium on Combinatorial Search. Palo Alto: AAAI Press, 2019: 151-158.
[25]	Liu Shuang, Sun Dong. Minimizing Energy Consumption of Wheeled Mobile Robots via Optimal Motion Planning[J]. IEEE/ASME Transactions on Mechatronics, 2014, 19(2): 401-411.
[26]	Lian Yindong, Zhang Langwen, Xie Wei, et al. An Improved Heuristic Path Planning Algorithm for Minimizing Energy Consumption in Distributed Multi-AGV Systems[C]//2020 International Symposium on Autonomous Systems (ISAS). Piscataway: IEEE, 2020: 70-75.
[27]	Hu Kewei, Chen Zheng, Kang Hanwen, et al. 3D Vision Technologies for a Self-developed Structural External Crack Damage Recognition Robot[J]. Automation in Construction, 2024, 159: 105262.
[28]	唐昀超, 祁少军, 朱立学, 等. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26.
	Tang Yunchao, Qi Shaojun, Zhu Lixue, et al. Obstacle Avoidance Motion in Mobile Robotics[J]. Journal of System Simulation, 2024, 36(1): 1-26.
[29]	Andreychuk Anton, Yakovlev Konstantin, Surynek Pavel, et al. Multi-agent Pathfinding with Continuous Time[J]. Artificial Intelligence, 2022, 305: 103662.
[30]	Atzmon Dor, Stern Roni, Felner Ariel, et al. Robust Multi-agent Path Finding and Executing[J]. Journal of Artificial Intelligence Research, 2020, 67: 549-579.
[31]	张洪琳, 吴耀华, 胡金昌, 等. 一种基于改进冲突搜索的多机器人路径规划算法[J]. 控制与决策, 2023, 38(5): 1327-1335.
	Zhang Honglin, Wu Yaohua, Hu Jinchang, et al. A Multi-robot Path Finding Algorithm Based on Improved Conflict Search[J]. Control and Decision, 2023, 38(5): 1327-1335.
[32]	Yu Jingjin, LaValle S. Structure and Intractability of Optimal Multi-robot Path Planning on Graphs[C]//Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence and the Twenty-Fifth Conference on Innovative Applications of Artificial Intelligence and the Fourth Symposium on Educational Advances in Artificial Intelligence. Palo Alto: AAAI Press, 2013: 1443-1449.

地图	机器人数量/个	算例数量	平均路径总代价值/步
地图	机器人数量/个	算例数量	B-IHCA*	B-IHCA*+GSS	E-HCA*
29×29 maze	4	20	108.40	108.40	108.40
	8	20	217.30	216.75	216.60
	12	18	330.44	330.50	333.27
	16	18	472.44	471.89	472.62
	20	18	601.89	602.17	605.17
	24	17	736.50	736.39	737.82
	28	16	883.67	875.88	880.10
32×32 room	4	20	72.95	72.95	72.65
	8	20	182.35	182.35	182.05
	12	18	294.10	294.20	292.95
	16	18	389.61	389.72	392.06
	20	18	503.78	503.89	507.41
	24	17	632.53	624.17	627.15
	28	16	753.72	752.22	756.26
32×32 random	4	20	68.10	68.10	68.10
	8	20	164.25	164.25	164.90
	12	18	268.85	268.85	269.00
	16	18	377.45	377.45	378.35
	20	18	485.15	485.15	488.15
	24	17	585.90	585.90	589.90
	28	17	686.75	686.75	691.85