HCA*框架下的低能耗多机器人路径规划算法

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

摘要/Abstract

摘要：

针对多机器人路径规划中的能耗优化问题，提出一种基于能量引导协作A*算法（energy-guided hierarchical cooperative A*，E-HCA*）的多机器人路径规划算法。针对多机器人系统在关隘口和狭长通道相互避让导致机器人振荡移动的问题，引入以路径长度为第二特征的节点拓展方法，提出一种协作A*框架下的贪婪抑制策略；建立差速机器人能耗模型，融合能耗指标在底层A*算法中构建能量引导估价函数，引导A*算法规划低能耗路径。实验结果表明：所提算法能够有效解决振荡路径问题，较现有算法路径总长度更短，路径总能耗更低，路径质量得到改善。

关键词: 多机器人, 路径规划, 能耗优化, 引导A*规划

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

中图分类号:

TP242

王宁,毛剑琳,李大焱等 . HCA*框架下的低能耗多机器人路径规划算法[J]. 系统仿真学报, 2025, 37(10): 2630-2642.

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

图/表 17

图1

图2

图3

图4

图5

图6

表1

图7

图8

图9

图10

表2

图11

图12

图13

图14

图15

参考文献 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