基于多指标动态优先级的无人机协同路径规划

doi:10.7527/S1000-6893.2023.28816

Abstract

Abstract:

To save operation costs and increase efficiency for collaborative inspection, distribution, and other tasks of multiple Unmanned Aerial Vehicles (UAVs) in complex urban environments, a cooperative path planning method is proposed based on multi-index dynamic priority. A dynamic priority model is constructed through a comprehensive consideration of the indices such as collision risk, total distance, and waiting time. Under the priority-based unilateral collision avoidance mechanism, a combined avoidance strategy is customized to handle local conflicts, so as to balance the planning efficiency and route quality. For individual path planning, a congestion weighted map is introduced into the Lazy Theta* algorithm to guide UAV to avoid congested areas and reduce the conflict possibility. Comparative simulation experiments show that the proposed individual planning algorithm can reduce congestion areas and congestion duration, and the proposed multi-index dynamic priority cooperative planning algorithm can improve planning efficiency and route optimality compared to the flight-time driven dynamic priority.

Key words: multi-UAV system, cooperative path planning, multi-index dynamic priority, Lazy Theta* algorithm, congestion weighted map, combined avoidance strategy

CLC Number:

V279

Zhu WANG, Mengtong ZHANG, Zhenpeng ZHANG, Guangtong XU. Multi-UAV cooperative path planning based on multi-index dynamic priority[J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(4): 328816.

Figures/Tables 20

Fig.1

Fig.2

Table 1

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 2

Fig.8

Fig.9

Fig.10

Table 3

Table 4

Fig.11

Fig.12

Fig. 13

Table 5

Fig.14

Table 6

References 23

1	LI S， ZHANG H H， LI Z L， et al. An air route network planning model of logistics UAV terminal distribution in urban low altitude airspace［J］. Sustainability， 2021， 13（23）： 13079.
2	LI K， NI W， TOVAR E， et al. On-board deep Q-network for UAV-assisted online power transfer and data collection［J］. IEEE Transactions on Vehicular Technology， 2019， 68（12）： 12215-12226.
3	杨旭，王锐，张涛. 面向无人机集群路径规划的智能优化算法综述［J］. 控制理论与应用， 2020， 37（11）： 2291-2302.
	YANG X， WANG R， ZHANG T. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization［J］. Control Theory & Applications， 2020， 37（11）： 2291-2302 （in Chinese）.
4	XU C， XU M， YIN C J. Optimized multi-UAV cooperative path planning under the complex confrontation environment［J］. Computer Communications， 2020， 162： 196-203.
5	XU L， CAO X B， DU W B， et al. Cooperative path planning optimization for multiple UAVs with communication constraints［J］. Knowledge-Based Systems， 2023， 260： 110164.
6	MOHANAN M G， SALGOANKAR A. A survey of robotic motion planning in dynamic environments［J］. Robotics and Autonomous Systems， 2018， 100： 171-185.
7	CHUNG S J， PARANJAPE A A， DAMES P， et al. A survey on aerial swarm robotics［J］. IEEE Transactions on Robotics， 2018， 34（4）： 837-855.
8	XU G T， CAO Y， SUN J L， et al. Real-time path generation for UAV swarms using receding planning framework and priority decoupling mechanism［C］∥ 2021 33rd Chinese Control and Decision Conference （CCDC）. Piscataway： IEEE Press， 2021： 4338-4343.
9	徐广通，王祝，曹严，等. 动态优先级解耦的无人机集群轨迹分布式序列凸规划［J］. 航空学报， 2022， 43（2）： 325059.
	XU G T， WANG Z， CAO Y， et al. Dynamic-priority-decoupled UAV swarm trajectory planning using distributed sequential convex programming［J］. Acta Aeronautica et Astronautica Sinica， 2022， 43（2）： 325059 （in Chinese）.
10	VELAGAPUDI P， SYCARA K， SCERRI P. Decentralized prioritized planning in large multirobot teams［C］∥ 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2010： 4603-4609.
11	ERDMANN M， LOZANO-PÉREZ T. On multiple moving objects［J］. Algorithmica， 1987， 2（1-4）： 477-521.
12	DU L Z， KE S F， WANG Z， et al. Research on multi-load AGV path planning of weaving workshop based on time priority［J］. Mathematical Biosciences and Engineering， 2019， 16（4）： 2277-2292.
13	ZHANG Y， WANG F L， FU F K， et al. Multi-AGV path planning for indoor factory by using prioritized planning and improved ant algorithm［J］. Journal of Engineering and Technological Sciences， 2018， 50（4）： 534-547.
14	TAI R C， WANG J C， CHEN W D. A priori tized planning algorithm of trajectory coordination based on time windows for multiple AGVs with delay disturbance［J］. Assembly Automation， 2019， 39（05）： 753-768.
15	GUNEY M ALI， RAPTIS I A. Dynamic prioritized motion coordination of multi-AGV systems［J］. Robotics and Autonomous Systems， 2021， 139： 103534.
16	LI H， LONG T， XU G T， et al. Coupling-degree-based heuristic prioritized planning method for UAV swarm path generation［C］∥ 2019 Chinese Automation Congress （CAC）. Piscataway： IEEE Press， 2020： 3636-3641.
17	DANIEL K， NASH A， KOENIG S， et al. Theta*： Any-angle path planning on grids［J］. Journal of Artificial Intelligence Research， 2010， 39： 533-579.
18	NASH A， KOENIG S， TOVEY C. Lazy theta*： Any-angle path planning and path length analysis in 3D［J］. Proceedings of the AAAI Conference on Artificial Intelligence， 2010， 24（1）： 147-154.
19	FARIA M， MARÍN R， POPOVIĆ M， et al. Efficient lazy theta* path planning over a sparse grid to explore large 3D volumes with a multirotor UAV［J］. Sensors， 2019， 19（1）： 174.
20	FARIA M， MAZA I， VIGURIA A. Applying frontier cells based exploration and lazy theta* path planning over single grid-based world representation for autonomous inspection of large 3D structures with an UAS［J］. Journal of Intelligent & Robotic Systems， 2019， 93（1）： 113-133.
21	徐鹏飞，丁延旭，曹清波. 基于环境优化的无人艇全局路径规划研究［J］. 中国造船， 2022， 63（5）： 206-220.
	XU P F， DING Y X， CAO Q B. Research on global path planning of unmanned surface vehicle based on environmental optimization［J］. Shipbuilding of China， 2022， 63（5）： 206-220 （in Chinese）.
22	张耀天，张旭成，贾明顺，等. 基于层次分析法的自适应决策评价方法［J］. 北京航空航天大学学报， 2016， 42（5）： 1065-1070.
	ZHANG Y T， ZHANG X C， JIA M S， et al. Adaptive evaluation method based on analytic hierarchy process［J］. Journal of Beijing University of Aeronautics and Astronautics， 2016， 42（5）： 1065-1070 （in Chinese）.
23	KIM C， KIM Y， YI H. Fuzzy analytic hierarchy process-based mobile robot path planning［J］. Electronics， 2020， 9（2）： 290.

确定优先级	总路程	等待时间	剩余路程比
总路程	a₁₁	a₁₂	a₁₃
等待时间	a₂₁	a₂₂	a₂₃
剩余路程比	a₃₁	a₃₂	a₃₃

确定优先级	总路程	等待时间	剩余路程比
总路程	1	3	5
等待时间	1/3	1	3
剩余路程比	1/5	1/3	1

无人机规模/架	求解结果	多指标动态优先级/s	飞行时间驱动的动态优先级/s
5	任务完成时间	115.11	112.10
5	规划耗时	0.88	5.88
10	任务完成时间	119.82	128.05
10	规划耗时	5.18	20.20
15	任务完成时间	120.14	123.94
15	规划耗时	5.54	10.62

无人机规模/架	迭代步数	发生冲突的无人机编号组合及其优先级结果
无人机规模/架	迭代步数	飞行时间驱动动态优先级	多指标动态优先级
5	4	｛3， 1｝，｛1， 4｝，｛3， 5｝，｛3， 4｝，｛5， 4｝	｛1， 4｝，｛5， 1｝，｛3， 2｝，｛5， 4｝
10	10	｛9， 1｝，｛5， 8｝，｛5， 9｝，｛5， 7｝	｛1， 9｝，｛8， 6｝，｛8， 9｝，｛8， 1｝
15	22	｛8， 1｝，｛14， 2｝，｛8， 13｝，｛10， 9｝	｛14， 2｝，｛11， 9｝，｛11， 15｝

无人机规模/架	求解结果	WM-Lazy Theta*/s	Lazy Theta*/s
5	任务完成时间	115.11	110.24
5	规划耗时	0.88	2.18
10	任务完成时间	119.82	114.45
10	规划耗时	5.18	15.85
15	任务完成时间	120.14	126.12
15	规划耗时	5.54	15.81

Multi-UAV cooperative path planning based on multi-index dynamic priority

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 20

References 23

Related Articles 15

Recommended Articles

Metrics

Comments

无人机规模/架	求解结果	组合规避策略/s	重规划策略/s	等待策略/s
5	任务完成时间	115.11	111.96	117.20
5	规划耗时	0.88	1.26	0.12
10	任务完成时间	119.82	117.87	137.11
10	规划耗时	5.18	7.86	0.75
15	任务完成时间	120.14	118.3	151.96
15	规划耗时	5.54	9.3	2.76

[1]	Chen WANG, Caisheng WEI, Zeyang YIN, Kai JIN, Xingchen LI. Collaborative planning of multi-UAV trajectories and communication strategies considering channel resource constraints [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(18): 331837-331837.
[2]	Yi ZHENG, Xianghong CHENG, Xingbang TANG, Yi CAO. Oriented detection algorithm for insulator and their defects from aerial images based on improved ReDet [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(18): 331825-331825.
[3]	. Robust infrared target tracking algorithm for anti-UAV in complex backgrounds [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[4]	. Research on UAV Complete Data Collection Trajectory Planning Algorithm Based on Time Window Constraints [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[5]	Fang LIU, Chenyang LU, Yan LU, Xin WANG. Adaptive template update-based Transformer algorithm for UAV target tracking [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(16): 331687-331687.
[6]	Yonggang YANG, Wentao JIANG, Zhiyun GAO. Real-time target detection algorithm for low altitude UAVs [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(16): 331619-331619.
[7]	Yu WANG, Zhipeng XIE, Yongjian TIAN, Guanglei MENG. Distributed UAV formation control with virtual structure guided reinforcement learning [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(15): 331354-331354.
[8]	. Risk-aware autonomous avoidance for eVTOL [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[9]	Fanteng MENG, Yong QIN, Jing CUI, Yunpeng WU, Zicheng ZHANG, Shaowei WEI. Unknown risk detection in external environment of railroad using UAV images [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531262-531262.
[10]	Lin CHEN, Qing ZHU, Han HU, Yulin DING, Pengxin GU. FLASH: Flexible and lightweight awareness of slope hazard [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531293-531293.
[11]	Yongguang JIN, Fangwei YE, Qihui WU. Location privacy protection mechanisms for UAVs with Remote ID [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531341-531341.
[12]	Ruokun QU, Zhiyuan WANG, Yelu LIU, Chenglong LI, Bo JIANG. UAV visual positioning technology for urban air mobility [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531168-531168.
[13]	Haijun ZHANG, Qingyue XIA, Xu MA, Chao REN, Yang LU. A review of unmanned aerial vehicles deployment optimization in 6G low-altitude communication scenarios [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531296-531296.
[14]	Junzhi LI, Teng LONG, Jingliang SUN, Hongyu MIAO, Zhenlin ZHOU. Differential flatness-based spatial-temporal hierarchical trajectory planning for fixed-wing UAVs in urban environments [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531369-531369.
[15]	. RGB-T UAV Object Tracking Based on Feature-cooperative Reconstruction [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.