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

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-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]	Chuanyun WANG, Yang SU, Linlin WANG, Tian WANG, Jingjing WANG, Qian GAO. Multi-object continuous robust tracking algorithm for anti-UAV swarm [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(7): 329017-329017.
[2]	. Integrated design of an high altitude super long endurance UAV system driven by distributed ground microwave power [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 0-0.
[3]	Xudong LUO, Yiquan WU, Jinlin CHEN. Research progress on deep learning methods for object detection and semantic segmentation in UAV aerial images [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 28822-028822.
[4]	Hongyu YIN, Yu WU, Tianjiao LIANG. Cooperative path planning for patrol coverage of fixed wing UAV [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 328944-328944.
[5]	Xin-Yu XU Jian Chen. UAV object tracking for air-ground targets based on status detection and Kalman filter [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 0-0.
[6]	Haiqiao LIU, Meng LIU, Zichao GONG, Jing DONG. A review of image matching methods based on deep learning [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(3): 28796-028796.
[7]	. Directional Expelling Attack for Unmanned Aerial Vehicle Swarm with leader-following structure [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 0-0.
[8]	. Cooperative Guidance Technique Considering Flight Safety Constraints of Cluster Wake Vortex Aerodynamic Coupling Effects [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 0-0.
[9]	. Automatic Landing Method for Quad-rotor Helicopter Based on MDP [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 0-0.
[10]	Yuqi CAO, Haoran FU, Fei GAO, Ximin LYU. Trajectory tracking control algorithm for canard⁃equipped tail⁃sitting vertical takeoff and landing UAV based on MPCC [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729950-729950.
[11]	Yucheng YAO, Xu LI, Qimin XU, Dong KONG. Instance segmentation for vehicle in UAV aerial images based on feature enhancement and calibration [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(24): 328397-328397.
[12]	. Vision-based air-to-air multi-UAVs tracking [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 0-0.
[13]	. Coordinated Manned/Unmanned Aerial Warfare: Concepts, Technologies, and Challenges [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 0-0.
[14]	Wenjun DING, Yajun CHAI, Dongdong HOU, Chiyu WANG, Guozong ZHANG, Zhaoyong MAO. Path planning for AUV&UAV cross⁃domain collaborative search and tracking [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(21): 528471-528471.
[15]	Ao WU, Huanyu LI, Yangjun GAO, Longfei YUE, Yajie CUI, Rennong YANG. Time-space coordination method for air refueling management for combat air patrol position maintenance [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(20): 628438-628438.