基于冲突搜索算法的多机器人路径规划

doi:10.16182/j.issn1004731x.joss.22-FZ0926

系统仿真学报 ›› 2022, Vol. 34 ›› Issue (12): 2659-2669.doi: 10.16182/j.issn1004731x.joss.22-FZ0926

• 仿真模型/系统置信度评估技术 • 上一篇下一篇

基于冲突搜索算法的多机器人路径规划

乔乔(), 王艳(), 纪志成

江南大学教育部物联网技术应用工程中心，江苏无锡 214122

收稿日期:2022-08-07 修回日期:2022-09-23 出版日期:2022-12-31 发布日期:2022-12-21
通讯作者: 王艳 E-mail:905523350@qq.com;wangyan@jiangnan.edu.cn
作者简介:乔乔(1996-)，男，硕士生，研究方向为机器人路径规划。E-mail：905523350@qq.com
基金资助:
国家自然科学基金(61973138);国家重点研发计划(2018YFB1701903)

Multi-robot Path Planning Based on CBS Algorithm

Qiao Qiao(), Yan Wang(), Zhicheng Ji

Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China

Received:2022-08-07 Revised:2022-09-23 Online:2022-12-31 Published:2022-12-21
Contact: Yan Wang E-mail:905523350@qq.com;wangyan@jiangnan.edu.cn

摘要/Abstract

摘要：

针对冲突搜索法（conflict-based search，CBS）在多机器人路径规划（multi-agent path finding，MAPF）过程中规划路径过长、单向搜索运行时间长等缺陷，从搜索方向和搜索方式提出一种改进的双向A^*焦点搜索来优化冲突搜索算法。将次优因子 $ω$ 引入冲突搜索算法的底层搜索函数中，以提高路径搜索的效率；将冲突搜索算法中的单向搜索优化为双向A^*搜索。实验结果表明：改进的冲突搜索算法的路径成本缩短了14.82%，总运行时间缩短了10.63%。

关键词: 多机器人路径规划, 双向搜索, 焦点搜索, 路径规划, 冲突搜索算法

Abstract:

Aiming at the long multi-robot planning path and long one-way search running time of conflict-based search(CBS) in the multi-agent path finding(MAPF), an improved CBS algorithm is proposed, which in a two-way A^* focus search is used to optimize the search direction and search method. The suboptimal factor $ω$ is introduced into the underlying search function of the CBS algorithm to improve the efficiency of path search. The one-way search in the conflict search algorithm is optimized to a two-way A^*search. The experimental results show that the path cost of the improved CBS algorithm is shortened by 14.82%, and the total running time is shortened by 10.63%.

Key words: multi-agent path finding(MAPF), two-way search, focus search, path planning, conflict-based search(CBS)

中图分类号:

TP242

乔乔, 王艳, 纪志成. 基于冲突搜索算法的多机器人路径规划[J]. 系统仿真学报, 2022, 34(12): 2659-2669.

Qiao Qiao, Yan Wang, Zhicheng Ji. Multi-robot Path Planning Based on CBS Algorithm[J]. Journal of System Simulation, 2022, 34(12): 2659-2669.

图/表 13

图1

图 2

图3

图4

图5

图6

图7

图8

表1

图9

图10

图11

图12

参考文献 16

1	刘晶, 姚维, 章玮. 移动机器人全覆盖路径规划算法研究[J]. 工业控制计算机, 2019, 32(12): 52-54.
	Liu Jing, Yao Wei, Zhang Wei. Research on Complete Coverage Path Planning Algorithm of Mobile Robots[J]. Industrial Control Computer, 2019, 32(12): 52-54.
2	王洪斌, 尹鹏衡, 郑维, 等. 基于改进的A*算法与动态窗口法的移动机器人路径规划[J]. 机器人, 2020, 42(3): 346-353.
	Wang Hongbin, Yin Pengheng, Zheng Wei, et al. Mobile Robot Path Planning Based on Improved A* Algorithm and Dynamic Window Method[J]. Robot, 2020, 42(3): 346-353.
3	强宁, 高洁, 康凤举. 基于PSO和三次样条插值的多机器人全局路径规划[J]. 系统仿真学报, 2017, 29(7): 1397-1404.
	Qiang Ning, Gao Jie, Kang Fengju. Multi-Robot Global Path Planning Based on PSO and Cubic Spline Interpolation[J]. Journal of System Simulation, 2017, 29(7): 1397-1404.
4	张云旺. 物流中心多任务场景下多AGV的路径规划算法设计[D]. 哈尔滨: 哈尔滨工业大学, 2021.
	Zhang Yunwang. Path Planning Algorithm Design of Multi-AGV in Multi-Task Scenario of Logistics Center[D]. Harbin: Harbin Institute of Technology, 2021.
5	杨伦. 消解基于冲突搜索的多智能体路径规划算法中的对顶冲突[D]. 长春: 吉林大学, 2020.
	Yang Lun. Resolving the Top Conflict in the Multi-Agent Path Planning Algorithm Based on Conflict Search[D]. Changchun: Jilin University, 2020.
6	万千. 基于CBS算法的物流分拣多AGV路径规划的研究[D]. 哈尔滨: 哈尔滨工业大学, 2018.
	Wan Qian. Research on Multi-AGV Path Planning for Logistics Sorting Based on CBS Algorithm[D]. Harbin: Harbin Institute of Technology, 2018.
7	Li Jiaoyang, Andrew Tinka, Scott Kiesel, et al. EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding[C]//35th AAAI Conference on Artificial Intelligence. California, SC: Association for the Advancement of Artificial Intelligence, 2021: 12353-12362.
8	朱宝艳. 移动机器人全覆盖路径规划算法研究[D]. 淄博: 山东理工大学, 2017.
	Zhu Baoyan. Research on Complete Coverage Planning Algorithm for Mobile Robots[D]. Zibo: Shandong University of Technology, 2017.
9	赵萍, 雷新宇, 陈波芝, 等. 基于TI-A*的多机器人动态规划协调方法研究[J]. 系统仿真学报, 2019, 31(5): 925-935.
	Zhao Ping, Lei Xinyu, Chen Bozhi, et al. Research on Multi-Robot Dynamic Programming Coordination Method Based on TI-A*[J]. Journal of System Simulation, 2019, 31(5): 925-935.
10	李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.
	Li Qi, Wang Wei. Path Planning of Multi-omnidirectional Wheel Collaborative Sorting Platform [J]. Journal of System Simulation, 2021, 33(3): 698-709.
11	陈志梅, 李敏, 邵雪卷, 等. 基于改进RRT算法的桥式起重机避障路径规划[J]. 系统仿真学报, 2021, 33(8): 1832-1838.
	Chen Zhimei, Li Min, Shao Xuejuan, et al. Obstacle Avoidance Path Planning of Bridge Crane Based on Improved RRT Algorithm[J]. Journal of System Simulation, 2021, 33(8): 1832-1838.
12	黄晓冬, 苑海涛, 毕敬, 等. 基于DQN的海战场舰船路径规划及仿真[J]. 系统仿真学报, 2021, 33(10): 2440-2448.
	Huang Xiaodong, Yuan Haitao, Bi Jing, et al. Ship Path Planning and Simulation in Naval Battlefield Based on DQN[J]. Journal of System Simulation, 2021, 33(10): 2440-2448.
13	林彬, 韩光辉, 宋晨晨, 等. 基于辐射扫描算法的机器人路径规划与仿真[J]. 系统仿真学报, 2021, 33(1): 84-90.
	Lin Bin, Han Guanghui, Song Chenchen, et al. Robot Path Planning and Simulation Based on Radiation Scanning Algorithm[J]. Journal of System Simulation, 2021, 33(1): 84-90.
14	刘恒麟. 多AGV路径规划算法的研究与实现[D]. 南京: 东南大学, 2020.
	Liu Henglin. Research and Implementation of Multi-AGV Path Planning Algorithm[D]. Nanjing: Southeast University, 2020.
15	Li Jiaoyang, Andrew Tinka, Scott Kiesel, et al. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses[C]//35th AAAI Conference on Artificial Intelligence. California, SC: Association for the Advancement of Artificial Intelligence, 2021: 11272-11281.
16	Li J, Ran M, Xie L. Efficient Trajectory Planning for Multiple Non-holonomic Mobile Robots Via Prioritized Trajectory Optimization[C]//IEEE Robotics and Automation Letters, 2021, 6(2): 405-412. DOI: 10.1109/LRA.2020.3044834 .

机器人数量/个	ECBS运行时间/s	改进ECBS 运行时间/s	运行时间降低百分比/%
4	0.000 43	0.000 42	2.32
8	0.000 59	0.000 58	1.69
12	0.000 85	0.000 72	15.3
16	0.001 29	0.001 14	11.6
20	0.002 43	0.002 50	-2.88
24	0.005 93	0.004 14	30.2
28	0.017 94	0.017 39	3.07
32	0.071 10	0.018 10	74.5

[1]	李腾, 丁佩佩, 刘金芳. 货到人拣选系统多阶段可穿行多AGV路径规划[J]. 系统仿真学报, 2022, 34(7): 1512-1523.
[2]	陆淼嘉, 黄承媛, 滕靖. 基于多智能体的网购生鲜无人车配送调度仿真[J]. 系统仿真学报, 2022, 34(6): 1185-1195.
[3]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[4]	蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.
[5]	梁江涛, 王慧琴. 基于改进蚁群算法的建筑火灾疏散路径规划研究[J]. 系统仿真学报, 2022, 34(5): 1044-1053.
[6]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[7]	李兆强, 张时雨. 基于快速RRT算法的三维路径规划算法研究[J]. 系统仿真学报, 2022, 34(3): 503-511.
[8]	王启明, 宗高强, 胥津铭. 多段式自动泊车最优路径规划与仿真分析[J]. 系统仿真学报, 2022, 34(2): 385-395.
[9]	张莉, 张惠珍, 刘冬, 陆雨欣. 考虑紧迫度的应急物资调度及粒子群算法求解[J]. 系统仿真学报, 2022, 34(09): 1988-1998.
[10]	陈志梅, 李敏, 邵雪卷, 赵志诚. 基于改进RRT算法的桥式起重机避障路径规划[J]. 系统仿真学报, 2021, 33(8): 1832-1838.
[11]	李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.
[12]	黄晓冬, 苑海涛, 毕敬, 刘涛. 基于DQN的海战场舰船路径规划及仿真[J]. 系统仿真学报, 2021, 33(10): 2440-2448.
[13]	林彬, 韩光辉, 宋晨晨, 张雅静. 基于辐射扫描算法的机器人路径规划与仿真[J]. 系统仿真学报, 2021, 33(1): 84-90.
[14]	朱大奇, 朱婷婷, 颜明重. 基于改进神经网络的多AUV全覆盖路径规划[J]. 系统仿真学报, 2020, 32(8): 1505-1514.
[15]	张倩, 熊英, 何明珂, 张浩. 不确定需求生鲜电商配送路径规划多目标模型[J]. 系统仿真学报, 2019, 31(8): 1582-1590.

基于冲突搜索算法的多机器人路径规划

Multi-robot Path Planning Based on CBS Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 16

相关文章 15

编辑推荐

Metrics

本文评价