基于改进冲突搜索的多智能体路径规划算法

doi:10.7527/S1000-6893.2022.27648

论文

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

基于改进冲突搜索的多智能体路径规划算法

于连波¹, 曹品钊¹, 石亮², 连捷¹, 王东¹()

^1.大连理工大学电子信息与电气工程学部控制科学与工程学院，大连 116024
^2.中国航空研究院，北京 100012

收稿日期:2022-06-20 修回日期:2022-07-10 接受日期:2022-09-06 出版日期:2023-06-25 发布日期:2022-09-22
通讯作者: 王东 E-mail:dwang@dlut.edu.cn
基金资助:
国家重点研发计划(2019YFE0197700);国家自然科学基金(61973050);辽宁省兴辽英才计划（XLYC

An improved conflict⁃based search algorithm for multi⁃agent path planning

Lianbo YU¹, Pinzhao CAO¹, Liang SHI², Jie LIAN¹, Dong WANG¹()

^1.School of Control Science and Engineering，Faculty of Electronic Information and Electrical Engineering，Dalian University of Technology，Dalian 116024，China
^2.Chinese Aeronautical Establishment，Beijing 100012，China

Received:2022-06-20 Revised:2022-07-10 Accepted:2022-09-06 Online:2023-06-25 Published:2022-09-22
Contact: Dong WANG E-mail:dwang@dlut.edu.cn
Supported by:
National Key Research and Development Program of China(2019YFE0197700);National Natural Science Foundation of China(61973050);Liaoning Revitalization Talents Program(XLYC2007010);Fundamental Research Funds for the Central Universities(DUT20GJ209)

摘要/Abstract

摘要：

多智能体路径规划问题在航空航天领域的多机任务中应用广泛但求解困难。基于改进冲突搜索的算法被设计用来快速求解多智能体路径规划问题。全局路径规划方面，首先设计综合考虑路径代价总和以及最大完工时间的多目标代价函数，其次提出基于唯一最短路径的冲突分类及消解方案，降低多智能体路径规划的计算量。在线冲突消解方面，利用速度障碍法在线检测和消解智能体与动态障碍物间的突发冲突。仿真结果表明，本文算法在全局路径规划方面保留基于冲突搜索算法的最优性并且降低了算法计算量，同时本文算法能够有效实现在线冲突检测与消解。

关键词: 多智能体路径规划, 基于冲突搜索, 冲突类型, 冲突检测, 冲突消解

Abstract:

The multi-agent path planning problem is widely used in multi-machine tasks in the aerospace field， but it is difficult to solve the problem. The improved conflict-based search algorithm is designed to quickly solve the multi-agent path planning problem. In terms of global path planning， a multi-objective cost function is designed to give a comprehensive consideration of the sum of path costs and the make span， and a conflict classification and resolution scheme based on the unique shortest path is then proposed to reduce the computational cost of multi-agent path planning. In terms of online conflict resolution， the velocity obstacle method is used to detect and resolve the sudden conflict between agents and dynamic obstacles. Simulation results show that the algorithm proposed retains the optimality of the conflict-based search algorithm in global path planning and reduces the amount of calculation. Thus， this algorithm can effectively realize online conflict detection and resolution.

Key words: multi-agent path planning, conflict-based search, conflict classification, conflict detection, conflict resolution

中图分类号:

V249

于连波, 曹品钊, 石亮, 连捷, 王东. 基于改进冲突搜索的多智能体路径规划算法[J]. 航空学报, 2023, 44(S1): 727648-727648.

Lianbo YU, Pinzhao CAO, Liang SHI, Jie LIAN, Dong WANG. An improved conflict⁃based search algorithm for multi⁃agent path planning[J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S1): 727648-727648.

图/表 21

图 1

图 2

图 3

表 1

图 4

图 5

图 6

图 7

图 8

图 9

表 2

智能体的起始点和目标点

智能体	$a 1$	$a 2$	$a 3$	$a 4$	$a 5$
起始点	F4	D7	E6	A6	F2
目标点	H5	B2	D2	B8	A3

表 2

图 10

图 11

图 12

表 3

图 13

图 14

图 15

图 16

图 17

图 18

参考文献 23

1	万逸飞，彭力. 基于协同多目标算法的多机器人路径规划［J］. 信息与控制， 2020， 49（2）： 139-146.
	WAN Y F， PENG L. Multi-robot path planning based on cooperative multi-objective algorithm［J］. Information and Control， 2020， 49（2）： 139-146 （in Chinese）.
2	晁永生，孙文磊. 动态修改路径的多机器人路径规划［J］. 机械科学与技术， 2018， 37（10）： 1483-1488.
	CHAO Y S， SUN W L. Dynamic path modification for multi-robot path planning［J］. Mechanical Science and Technology for Aerospace Engineering， 2018， 37（10）： 1483-1488 （in Chinese）.
3	曹其新，黄先群，朱笑笑，等. 基于保留区域的分布式多机器人路径规划［J］. 华中科技大学学报（自然科学版）， 2018， 46（12）： 71-76.
	CAO Q X， HUANG X Q， ZHU X X， et al. Distributed multi-robot path planning based on reserved area［J］ Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2018， 46（12）：71-76 （in Chinese）.
4	OROZCO-ROSAS U， MONTIEL O， SEPÚLVEDA R. Mobile robot path planning using membrane evolutionary artificial potential field［J］. Applied Soft Computing， 2019， 77： 236-251.
5	BHATTACHARYA P， GAVRILOVA M L. Roadmap-based path planning-using the Voronoi diagram for a clearance-based shortest path［J］. IEEE Robotics & Automation Magazine， 2008， 15（2）： 58-66.
6	胡章芳，冯淳一，罗元. 改进粒子群优化算法的移动机器人路径规划［J］. 计算机应用研究， 2021， 38（10）： 3089-3092.
	HU Z F， FENG C Y， LUO Y. Improved particle swarm optimization algorithm for mobile robot path planning［J］. Application Research of Computers， 2021， 38（10）： 3089-3092 （in Chinese）.
7	蒋强，易春林，张伟，等. 基于蚁群算法的移动机器人多目标路径规划［J］. 计算机仿真， 2021， 38（2）： 318-325.
	JIANG Q， YI C L， ZHANG W， et al. The multi-objective path planning for mobile robot based on ant colony algorithm［J］. Computer Simulation， 2021， 38（2）： 318-325 （in Chinese）.
8	LIU C， LIU H， YANG J. A path planning method based on adaptive genetic algorithm for mobile robot［J］. Journal of Information & Computational Science， 2011， 8（5）： 808-814.
9	SHARON G， STERN R， FELNER A， et al. Conflict-based search for optimal multi-agent pathfinding［J］. Artificial Intelligence， 2015， 219： 40-66.
10	MA H， LI J Y， KUMAR T K S， et al. Lifelong multiagent path finding for online pickup and delivery tasks［C］∥ Proceedings of the 16th Conference on Autonomous Agents and Multi-Agent Systems， 2017： 837-845.
11	MA H， YANG J， COHEN L， et al. Feasibility study： moving non-homogeneous teams in congested video game environments［C］∥ Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment， 2017， 13（1）： 270-272.
12	HÖNIG W， PREISS J A， KUMAR T K S， et al. Trajectory planning for quadrotor swarms［J］. IEEE Transactions on Robotics， 2018， 34（4）： 856-869.
13	BARER M， SHARON G， STERN R Z， et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem［C］∥ Proceedings of the 7th Annual Symposium on Combinatorial Search， 2014： 19-27.
14	COHEN L， KOENIG S. Bounded suboptimal multi-agent path finding using highways［C］∥ Proceedings of the 25th International Joint Conference on Artificial Intelligence， 2016： 978-3979.
15	BOYARSKI E， FELNER A， STERN R， et al. ICBS： Improved conflict-based search algorithm for multi-agent pathfinding［C］∥ Proceedings of the 24th International Conference on Artificial Intelligence， 2015： 740-746.
16	FELNER A， LI J， BOYARSKI E， et al. Adding heuristics to conflict-based search for multi-agent path finding［C］∥ Proceedings of the International Conference on Automated Planning and Scheduling， 2018， 28： 83-87.
17	LI J， FELNER A， BOYARSKI E， et al. Improved heuristics for multi-agent path finding with conflict-based search［C］∥ Proceedings of the 28th International Joint Conference on Artificial Intelligence， 2019： 442-449.
18	LI J， HARABOR D， STUCKEY P J， et al. Symmetry-breaking constraints for grid-based multi-agent path finding［C］∥ Proceedings of the AAAI Conference on Artificial Intelligence， 2019， 33（1）： 6087-6095.
19	COHEN L， WAGNER G， CHAN D， et al. Rapid randomized restarts for multi-agent path finding solvers［C］∥ Proceedings of Eleventh Annual Symposium on Combinatorial Search， 2018： 148-152.
20	FIORINI P， SHILLER Z. Motion planning in dynamic environments using velocity obstacles［J］. The International Journal of Robotics Research， 1998， 17（7）： 760-772.
21	DURAND N， BARNIER N. Does ATM need centralized coordination？ autonomous conflict resolution analysis in a constrained speed environment［J］. Air Traffic Control Quarterly， 2015， 23（4）： 325-346.
22	杨秀霞，周硙硙，张毅.基于速度障碍圆弧法的UAV自主避障规划研究［J］.系统工程与电子技术， 2017， 39（1）： 168-176.
	YANG X X， ZHOU W W， ZHANG Y. Automatic obstacle avoidance planning for UVA based on velocity obstacle arc method［J］. Systems Engineering and Electronics， 2017， 39（1）： 168-176 （in Chinese）.
23	DURAND N. Constant speed optimal reciprocal collision avoidance［J］. Transportation Research Part C： Emerging Technologies， 2018， 96： 366-379.

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

目标函数类型	节点数量	调用路径规划算法次数	目标节点路径代价总和	目标节点最大完工时间
单目标C	7	10	22
多目标F	5	8	22	6

基于改进冲突搜索的多智能体路径规划算法

An improved conflict⁃based search algorithm for multi⁃agent path planning

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 21

参考文献 23

相关文章 1

编辑推荐

Metrics

本文评价

算法	改进冲突搜索算法	蚁群算法	粒子群算法
路径代价总和	30	33	32
最大完工时间	8	9	9