基于层次分解的在线三维RRT*协同航路规划

doi:10.12305/j.issn.1001-506X.2023.05.17

Abstract

Abstract:

Aiming at the time cooperative route planning problem of multiple unmanned aerial vehicles (UAVs), an online three-dimensional planning method based on hierarchical decomposition is proposed. Firstly, the high dimensional strong coupling cooperative planning problem is decomposed into a low dimensional simple optimization problem according to 3 layers. Secondly, an optimization method of cooperative index parameters based on the inverse hyperbolic tangent function is presented in order to solve the diversion consumption problem caused by excessive time intervals between UAVs. Then, an online route planning algorithm of three-dimensional rapidly-exploring random tree^* based on receding horizon (TRH-RRT^*) is proposed. The biased random samples are employed to increase the utilization of sampling points, the artificial potential field is exploited to guide the growth of RRT^* nodes and the node removal method based on receding horizon is applied to reducing the unnecessary scanning process. Finally, the simulation results for attack mission of UAVs convergence show that the proposed method possesses advantages in planning time and planning results.

Key words: multiple unmanned aerial vehicle (UAV), cooperative route planning, rapidly exploring random tree^* (RRT^*), receding horizon, artificial potential field

CLC Number:

TP273

Xiaocao YANG, Yanli DU, Yunong BU, Yanbin LIU, Cheng GAO. Online three-dimensional RRT^* cooperative route planning based on hierarchical decomposition[J]. Systems Engineering and Electronics, 2023, 45(5): 1409-1419.

Figures/Tables 21

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Table 1

Fig.13

Table 2

Fig.14

Fig.15

Fig.16

Fig.17

Fig.18

Table 3

References 31

1	ZHEN Z Y , ZHU P , XUE Y X , et al. Distributed intelligent self-organized mission planning of multi-UAV for dynamic targets cooperative search-attack[J]. Chinese Journal of Aeronautics, 2019, 32 (12): 2706- 2716. doi: 10.1016/j.cja.2019.05.012
2	CHEN L , WU H S . Demand analysis based on SWOT's intelligent unmanned aerial vehicle swarm[J]. Journal of Physics: Conference Series, 2021, 2037 (1): 012121- 012129. doi: 10.1088/1742-6596/2037/1/012121
3	ZHANG H C. Research on UAV route planning technology based on evolutionary algorithm[C]//Proc. of the International Conference on Big Data Analytics for Cyber-Physical System in Smart City, 2022: 1179-1184.
4	SHIRI H , PARK J , BENNIS M . Remote UAV online path planning via neural network-based opportunistic control[J]. IEEE Wireless Communications Letters, 2020, 9 (6): 861- 865. doi: 10.1109/LWC.2020.2973624
5	INDRIYANTO T, RIZKI A R, HARIYADIN M L, et al. Centra-lized swarming UAV using ROS for collaborative missions[C]//Proc. of the 3RD International Seminar on Metallurgy and Materials: Exploring New Innovation in Metallurgy and Materials, 2020.
6	LIU H S , CHEN Q Y , NAN P , et al. Three-dimensional mountain complex terrain and heterogeneous multi-UAV cooperative combat mission planning[J]. IEEE Access, 2020, 10 (8): 197407- 197419.
7	朱黔, 黄蓓, 许诺, 等. 面向复杂障碍环境的多机协同侦察任务规划[J]. 电光与控制, 2021, 28 (2): 43- 47.
	ZHU Q , HUANG B , XU N , et al. Mission planning of coope-rative reconnaissance for multiple UAVs in complex environment with obstacles[J]. Electronics Optics & Control, 2021, 28 (2): 43- 47.
8	杨川力, 宁芊, 陈炳才, 等. 基于GAPSO-TS的多基地无人机航路-时间协同规划[J]. 火力与指挥控制, 2021, 46 (9): 20- 26.
	YANG C L , NING Q , CHEN B C , et al. Multi-base UAVs path-time collaborative planning based on GAPSO-TS algorithm[J]. Fire Control & Command Control, 2021, 46 (9): 20- 26.
9	SHI Z J, NG W K. A collision-free path planning algorithm for unmanned aerial vehicle delivery[C]//Proc. of the International Conference on Unmanned Aircraft Systems, 2018: 358-362.
10	XU C , XU M , YIN C J . Optimized multi-UAV cooperative path planning under the complex confrontation environment[J]. Computer Communications, 2020, 162 (15): 196- 203.
11	MOHAMMED H , ROMDHANE L , JARADAT M A . RRT^* N: an efficient approach to path planning in 3D for static and dynamic environments[J]. Advanced Robotics, 2021, 35 (3/4): 168- 180.
12	MCCOURT M, TON C T, MEHTA S S, et al. Adaptive step-length RRT algorithm for improved coverage[C]//Proc. of the AIAA Guidance, Navigation, and Control Conference, 2016: 06380-06388.
13	LEE H , LEE D , SHIM D H . Receding horizon-based RRT^* algorithm for a UAV real-time path planner[M]. Grapevine, Texas: Aircraft Industries Association of America, 2017.
14	刘奥博, 袁杰. 目标偏置双向RRT^*算法的机器人路径规划[J]. 计算机工程与应用, 2021, 58 (6): 234- 240.
	LIU A B , YUAN J . Robot path planning based on goal biased bidirectional RRT^* algorithm[J]. Computer Engineering and Applications, 2021, 58 (6): 234- 240.
15	LIU H Y, ZHANG X B, WEN J, et al. Goal-biased bidirectional RRT based on curve-smoothing[C]//Proc. of the 5th Curve-Smoothing IFAC Symposium on Telematics Applications, 2019: 255-260.
16	陈波芝, 陆亮, 雷新宇, 等. 基于改进快速扩展随机树算法的双机械臂协同避障规划方法[J]. 中国机械工程, 2018, 29 (10): 1220- 1226.
	CHEN B Z , LU L , LEI X Y , et al. Simultaneous obstacle-avoidance motion planning approach for dual arm robots based on improved RRT algorithm[J]. China Mechanical Engineering, 2018, 29 (10): 1220- 1226.
17	KIANI F , SEYYEDABBASI A , ALIYEV R , et al. Adapted-RRT: novel hybrid method to solve three-dimensional path planning problem using sampling and metaheuristic-based algorithms[J]. Neural Computing and Applications, 2021, 33 (22): 15569- 15599. doi: 10.1007/s00521-021-06179-0
18	阮晓钢, 郭威, 黄静, 等. 机器人信息增益RRT环境探索算法[J]. 控制与决策, 2021, 36 (11): 2683- 2689.
	RUAN X G , GUO W , HUANG J , et al. Robot RRT based on information gain for environment exploration[J]. Control and Decision, 2021, 36 (11): 2683- 2689.
19	GU M Y, HUANG Y Z. Dynamic obstacle avoidance of mobile robot based on adaptive velocity obstacle[C]//Proc. of the 36th Youth Academic Annual Conference of Chinese Association of Automation, 2021: 776-781.
20	CHEN H Y , JI Y B , NIU L J . Reinforcement learning path planning algorithm based on obstacle area expansion strategy[J]. Intelligent Service Robotics, 2020, 13 (2): 289- 297.
21	ZHANG J , LI N Z , ZHANG D Y , et al. Multi-UAV cooperative route planning based on decision variables and improved genetic algorithm[J]. Journal of Physics: Conference Series, 2021, 1941 (1): 012012- 012020.
22	WU X L , XU L , ZHEN R , et al. Bi-directional adaptive A ^* algorithm toward optimal path planning for large-scale UAV under multi-constraints[J]. IEEE Access, 2020, 5, 85431- 85440.
23	TANG A D , HAN T , ZHOU H , et al. An improved equili-brium optimizer with application in unmanned aerial vehicle path planning[J]. Sensors, 2021, 21 (5): 1814.
24	HUO L S , ZHU J H , LI Z M , et al. A hybrid differential symbiotic organisms search algorithm for UAV path planning[J]. Sensors, 2021, 21 (9): 3037.
25	任天祥, 贺建良, 邹杰. 基于改进Theta^*算法的直升机三维航路规划[J]. 电光与控制, 2022, 29 (2): 45- 48.
	REN T X , HE J L , ZOU J . 3D Route planning for helicopters based on improved Theta^* algorithm[J]. Electronics Optics & Control, 2022, 29 (2): 45- 48.
26	ZHANG J , LI J W , YANG H W , et al. Complex environment path planning for unmanned aerial vehicles[J]. Sensors, 2021, 21 (15): 5250.
27	MENG L, SONG Q, ZHAO Q J, et al. Route planning for unmanned aerial vehicle based on rolling RRT in unknown environment[C]//Proc. of the IEEE International Conference on Computational Intelligence and Computing Research, 2016.
28	SANG H Q , YOU Y S , SUN X J , et al. The hybrid path planning algorithm based on improved A ^* and artificial potential field for unmanned surface vehicle formations[J]. Ocean Engineering, 2021, 223 (3): 108709.
29	LIU C , FENG Q C , TANG Z L , et al. Motion planning of the citrus-picking manipulator based on the TO-RRT algorithm[J]. Agriculture, 2022, 12 (5): 581- 604.
30	DEBNATH S K , OMAR R , LATIP N B A . A review on energy efficient path planning algorithms for unmanned air vehicles[M]. Computational Science and Technology.Singapore: Springer, 2019.
31	FANG J, YIN K, WANG H B, et al. Motion path planning of sorting robot based on extended RRT-connect algorithm[C]//Proc. of the 4th International Conference on Mechatronics, Robotics and Automation, 2021.

比较指标	规划时间/s	代价大小	平均节点数
APF-RRT^*	3.092	266.24	18.428
TRH-RRT^*	1.390	201.66	16.235

比较指标	APF-RRT^*	TRH-RRT^*
平均转弯角/(°)	24.161	14.300
最大转弯角/(°)	168.594	41.630
最大爬升角/(°)	0.218 8	0.017 5
规划时间/s	4.088 4	1.455 8

比较指标	规划时间/s	平滑度	协同时间/h
固定权值	1.092 6	707.686 6	0.630 25
可变权值	1.380 8	608.721 0	0.587 46

[1]	Mulai TAN, Dali DING, Lei XIE, Wei DING, Chenghui LYU. UCAV escape maneuvering decision based on fuzzy expert system and IDE algorithm [J]. Systems Engineering and Electronics, 2022, 44(6): 1984-1993.
[2]	Xiaowei FU, Jing PAN. Distributed formation control of UAV swarm with dynamic obstacle avoidance [J]. Systems Engineering and Electronics, 2022, 44(2): 529-537.
[3]	Tong HAN, Andi TANG, Huan ZHOU, Dengwu XU, Lei XIE. Multiple UAV cooperative path planning based on LASSA method [J]. Systems Engineering and Electronics, 2022, 44(1): 233-241.
[4]	Yi ZHANG, Guowei FANG, Xiuxia YANG. Target tracking method for UAVs formation based on graph Laplacian [J]. Systems Engineering and Electronics, 2021, 43(3): 796-805.
[5]	Yao HAN, Shaohua LI. UAV path planning based on improved artificial potential field [J]. Systems Engineering and Electronics, 2021, 43(11): 3305-3311.
[6]	Daidai CHEN, Wanyou LI. Local path planning algorithm for USV with towed cable [J]. Systems Engineering and Electronics, 2020, 42(9): 1988-1994.
[7]	ZHU Qiang, SHAO Zhijiang. Realtime receding horizon pursuit and evasion games of missile guidance based on neural network [J]. Systems Engineering and Electronics, 2019, 41(7): 1597-1605.
[8]	CHEN Tiande, HUANG Yanyan, ZHANG Yongliang. Non-trap dynamic path planning based on collision risk [J]. Systems Engineering and Electronics, 2019, 41(11): 2496-2506.
[9]	LIU Zhong, GAO Xiaoguang, FU Xiaowei. Multi-UAVs distributed cooperative target search algorithm with controllable revisit mechanism based on digital pheromone [J]. Systems Engineering and Electronics, 2017, 39(9): 1998-2011.
[10]	GAO Bing-bing, GAO She-sheng, HU Gao-ge, YAN Hai-feng. Adaptive UKF based on maximum likelihood principle and receding horizon estimation [J]. Systems Engineering and Electronics, 2016, 38(7): 1629-1637.
[11]	ZHAO Yu, ZHANG Bin, XU An, LI Hong-ke. Two-fighter cooperative tactics maneuvering game and approximate optimal solution [J]. Systems Engineering and Electronics, 2015, 37(3): 589-593.
[12]	HUANG Chang-qiang，LIU He-ming，HUANG Han-qiao, CHENG Hua, CHEN Shao-hua. Online UCAV attacking trajectory planning in uncertain environment [J]. Systems Engineering and Electronics, 2014, 36(8): 1558-1565.
[13]	WU Xu-zhong, TANG Sheng-jing, GUO Jie， XIONG Jun-hui. Trajectory tracking guidance law for reentry based on receding horizon control [J]. Systems Engineering and Electronics, 2014, 36(8): 1602-1608.
[14]	ZHANG Tao，YU Lei，ZHOU Zhong-liang，WANG Lin. Decision-making for air combat maneuvering based on hybrid algorithm [J]. Journal of Systems Engineering and Electronics, 2013, 35(7): 1445-1450.
[15]	LUO De-lin,WU Shun-xiang. Ant colony optimization with potential field heuristic for robot path planning [J]. Journal of Systems Engineering and Electronics, 2010, 32(6): 1277-1280.

Online three-dimensional RRT^* cooperative route planning based on hierarchical decomposition

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 21

References 31

Related Articles 15

Recommended Articles

Metrics

Comments

Online three-dimensional RRT* cooperative route planning based on hierarchical decomposition

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 21

References 31

Related Articles 15

Recommended Articles

Metrics

Comments

Online three-dimensional RRT^* cooperative route planning based on hierarchical decomposition