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

doi:10.7527/S1000-6893.2022.27648

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

CLC Number:

V249

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.

Figures/Tables 21

Fig.1

Fig.2

Fig.3

Table 1

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Table 2

Starts and goals of agents

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

Table 2

Fig.10

Fig.11

Fig.12

Table 3

Fig.13

Fig.14

Fig.15

Fig.16

Fig.17

Fig.18

References 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.

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

[1]	ZHANG Honghong, GAN Xusheng, SUN Jingjuan, ZHAO Guhao, HAN Baohua. Analysis of low altitude UAV conflict resolution safety based on STPA-TOPAZ [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(7): 325354-325354.
[2]	JIAO Weidong, WANG Ruidong, YAO Junqiang, PANG Yanli. Conformal geometric algebraic description of runway incursion and conflict detection [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 325297-325297.
[3]	HUANG Yang, TANG Jun, LAO Songyang. UAV flight conflict resolution algorithm based on complex network [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(12): 322222-322222.
[4]	GUAN Xiangmin, LYU Renli. Aircraft conflict resolution method based on satisfying game theory [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2017, 38(S1): 721475-721475.
[5]	CHEN Weifeng, SHAO Zhijiang. Direct Disjunction Transcription Based Conflict Resolution Approach [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2014, 35(4): 1122-1133.

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

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 21

References 23

Related Articles 5

Recommended Articles

Metrics

Comments

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