Unmanned Aerial Vehicle Path Planning Algorithm Based on Improved Informed RRT* in Complex Environment

doi:10.16183/j.cnki.jsjtu.2022.442

Abstract

Abstract:

To address the problems of long planning time, redundant planning path, and even planning failure caused by local constraints in narrow spaces in the rapid exploring random trees (RRT) algorithm when unmanned aerial vehicle is planning a path in a complex environment, an improved Informed RRT^* algorithm is proposed. First, the artificial potential field (APF) method is used to make the sampling points move to the target point in the way of potential field descending, which improves the purpose and directionality of RRT tree expansion. Considering the complexity of the global environment during tree expansion, an adaptive step size is introduced to accelerate the expansion speed of the RRT tree in an unobstructed environment. Then, relevant constraints are added in the process of random tree expansion to ensure the feasibility of the generated paths. After the first reachable path is found, variable elliptic or ellipsoidal sampling domain is used to limit the selection of sampling points and the expansion range of adaptive step size, so as to accelerate the convergence of the algorithm to the asymptotic optimization. Finally, the original algorithm and the improved algorithm are compared in two-dimensional and three-dimensional complex environment. The simulation results show that the improved algorithm can find a better reachable path with a small number of iterations, lock the elliptic or ellipsoidal sampling domain faster and leave more time for path optimization. The improved algorithm performs better in path planning.

Key words: path planning, Informed RRT^* (IRRT^*), artificial potential field (APF) method, adaptive step size, elliptic sampling domain

CLC Number:

TP242.2

LIU Wenqian, SHAN Liang, ZHANG Weilong, LIU Chenglin, MA Qiang. Unmanned Aerial Vehicle Path Planning Algorithm Based on Improved Informed RRT^* in Complex Environment[J]. Journal of Shanghai Jiao Tong University, 2024, 58(4): 511-524.

Figures/Tables 27

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

Fig.16

Fig.17

Fig.18

Fig.19

Fig.20

Fig.21

Fig.22

Fig.23

Fig.24

Fig.25

Tab.1

Fig.26

References 25

[1]	杨旭, 王锐, 张涛. 面向无人机集群路径规划的智能优化算法综述[J]. 控制理论与应用, 2020, 37(11): 2291-2302.
	YANG Xu, WANG Rui, ZHANG Tao. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization[J]. Control Theory & Applications, 2020, 37(11): 2291-2302.
[2]	徐伟华, 聊士超, 张根瑞, 等. 改进Theta^算法的物流无人机城域三维路径规划[J]. 计算机工程与应用*, 2023, 59(17): 334-340. doi: 10.3778/j.issn.1002-8331.2205-0428
	XU Weihua, LIAO Shichao, ZHANG Genrui, et al. 3D path planning of logistics UAV based on improved Theta^* algorithm in metropolitan area[J]. Computer Engineering & Applications, 2023, 59(17): 334-340.
[3]	王琼, 刘美万, 任伟建, 等. 无人机航迹规划常用算法综述[J]. 吉林大学学报(信息科学版), 2019, 37(1): 58-67.
	WANG Qiong, LIU Meiwan, REN Weijian, et al. Overview of common algorithms for UAV path planning[J]. Journal of Jilin University(Information Science Edition), 2019, 37(1): 58-67.
[4]	张伟龙, 单梁, 常路, 等. 基于改进DWA的多无人水面艇分布式避碰算法[J]. 控制与决策, 2023, 38(4):951-962.
	ZHANG Weilong, SHAN Liang, CHANG Lu, et al. Distributed collision avoidance algorithm for multiple unmanned surface vessels based on improved DWA[J]. Control & Decision, 2023, 38(4):951-962.
[5]	刘光才, 马寅松, 齐福强, 等. 基于改进A^-人工势场法的城市物流无人机路径规划[J]. 飞行力学*, 2022, 40(6): 16-23.
	LIU Guangcai, MA Yinsong, QI Fuqiang, et al. Flight path planning for urban logistics UAV based on improved A^-artificial potential field method algorithm[J]. Flight Dynamics*, 2022, 40(6): 16-23.
[6]	LI W M, WANG L, ZOU A W, et al. Path planning for UAV based on improved PRM[J]. Energies, 2022, 15(19): 7267. doi: 10.3390/en15197267 URL
[7]	孔维立, 王峰, 周平华, 等. 改进蚁群算法的无人机三维路径规划[J]. 电光与控制, 2023, 30(3): 63.
	KONG Weili, WANG Feng, ZHOU Pinghua, et al. Three dimensional path planning of UAV based on improved ant colony algorithm[J]. Electronics Optics & Control, 2023, 30(3): 63.
[8]	罗隆福, 李冬, 钟杭. 基于改进RRT的无人机电力杆塔巡检路径规划[J]. 湖南大学学报(自然科学版), 2018, 45(10): 80-86.
	LUO Longfu, LI Dong, ZHONG Hang. Path planning of unmanned aircraft inspection for electric towers based on advanced RRT algorithm[J]. Journal of Hunan University(Natural Sciences), 2018, 45(10): 80-86.
[9]	黄宇昊, 韩超, 赵明辉, 等. 考虑安全飞行通道约束的无人机飞行轨迹多目标优化策略[J]. 上海交通大学学报, 2022, 56(8): 1024-1033. doi: 10.16183/j.cnki.jsjtu.2021.154
	HUANG Yuhao, HAN Chao, ZHAO Minghui, et al. Multi-objective optimization strategy of trajectory planning for unmanned aerial vehicles considering constraints of safe flight corridors[J]. Journal of Shanghai Jiao Tong University, 2022, 56(8): 1024-1033.
[10]	魏武, 韩进, 李艳杰, 等. 基于双树Quick-RRT算法的移动机器人路径规划[J]. 华南理工大学学报(自然科学版), 2021, 49(7): 51-58. doi: 10.12141/j.issn.1000-565X.200769
	WEI Wu, HAN Jin, LI Yanjie, et al. Path planning of mobile robots based on dual-tree quick-RRT Algorithm[J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(7): 51-58.
[11]	刘文倩, 单梁, 王志强, 等. 机械臂的位姿分离求逆和改进RRT-connect算法研究[J/OL]. 控制工程. https://doi.org/10.14107/j.cnki.kzgc.20210234.
	LIU Wenqian, SHAN Liang, WANG Zhiqiang, et al. Research on inverse kinematics analysis based on position and attitude separation and improved path planning algorithm of manipulator[J/OL]. Control Engineering of China. https://doi.org/10.14107/j.cnki.kzgc.20210234.
[12]	KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894. doi: 10.1177/0278364911406761 URL
[13]	WEBB D J, BERG J V D. Kinodynamic RRT^*: Optimal motion planning for systems with linear differential constraints[DB/OL]. (2012-05-23) [2022-10-11]. https://arxiv.org/abs/1205.5088 .
[14]	GAMMELL J D, SRINIVASA S S, BARFOOT T D. Informed RRT^: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]// 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems*. Chicago, USA: IEEE, 2014: 2997-3004.
[15]	NOREEN I, KHAN A, RYU H, et al. Optimal path planning in cluttered environment using RRT^-AB[J]. Intelligent Service Robotics*, 2018, 11(1): 41-52. doi: 10.1007/s11370-017-0236-7 URL
[16]	YANG F, FANG X, GAO F, et al. Obstacle avoidance path planning for UAV based on improved RRT algorithm[J]. Discrete Dynamics in Nature & Society, 2022, 2022: 1-9.
[17]	WU X J, XU L, ZHEN R, et al. Biased sampling potentially guided intelligent bidirectional RRT algorithm for UAV path planning in 3D environment[J]. Mathematical Problems in Engineering, 2019, 2019: 1-12.
[18]	施英杰. 基于改进蚁群算法及改进informed-RRT^*算法的机器人路径规划研究[D]. 长春: 吉林大学, 2022.
	SHI Yingjie. Research on robot path planning based on improved ant colony algorithm and improved informed-RRT^* algorithm[D]. Changchun: Jilin University, 2022.
[19]	WU D H, WEI L S, WANG G L, et al. APF-IRRT^: An improved informed rapidly-exploring random trees-star algorithm by introducing artificial potential field method for mobile robot path planning[J]. Applied Sciences*, 2022, 12(21): 10905. doi: 10.3390/app122110905 URL
[20]	杨俊成, 李淑霞, 蔡增玉. 路径规划算法的研究与发展[J]. 控制工程, 2017, 24(7): 1473-1480.
	YANG Juncheng, LI Shuxia, CAI Zengyu. Research and development of path planning algorithm[J]. Control Engineering of China, 2017, 24(7): 1473-1480.
[21]	ZHONG X Y, TIAN J, HU H S, et al. Hybrid path planning based on safe A^* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment[J]. Journal of Intelligent & Robotic Systems, 2020, 99(1): 65-77.
[22]	张启钱, 许卫卫, 张洪海, 等. 复杂低空物流无人机路径规划[J]. 北京航空航天大学学报, 2020, 46(7): 1275-1286.
	ZHANG Qiqian, XU Weiwei, ZHANG Honghai, et al. Path planning for logistics UAV in complex low-altitude airspace[J]. Journal of Beijing University of Aeronautics & Astronautics, 2020, 46(7): 1275-1286.
[23]	李东方, 李科伟, 邓宏彬, 等. 基于人工势场与IB-LBM的机器蛇水中2D避障控制算法[J]. 机器人, 2018, 40(3): 346-359. doi: 10.13973/j.cnki.robot.170421
	LI Dongfang, LI Kewei, DENG Hongbin, et al. The 2D aquatic obstacle avoidance control algorithm of the snake-like robot based on artificial potential field and IB-LBM[J]. Robot, 2018, 40(3): 346-359. doi: 10.13973/j.cnki.robot.170421
[24]	ZHOU H B, ZHOU S, YU J, et al. Trajectory optimization of pickup manipulator in obstacle environment based on improved artificial potential field method[J]. Applied Sciences, 2020, 10(3): 935. doi: 10.3390/app10030935 URL
[25]	臧强, 张国林, 靳雨桐, 等. 一种基于动态步长的AAPF-RRT^移动机器人路径规划新算法[J]. 中国科技论文*, 2021, 16(11): 1227-1233.
	ZANG Qiang, ZHANG Guolin, JIN Yutong, et al. A novel path planning method of mobile robot based on AAPF-RRT^* with dynamic step[J]. China Sciencepaper, 2021, 16(11): 1227-1233.

环境	算法	t_cost/s
环境	算法	实验1	实验2		实验3		实验4		实验5		实验6
map1	IRRT^*	21.60287	15.5735		75.43213		11.9442		58.0835		9.934
map1	APF-IRRT^*	11.1223	10.4460		8.0520		5.6783		4.0484		7.4060
map1	AAPF-IRRT^*	1.3111	3.9898		1.5462		2.8812		1.2479		1.0312
map2	IRRT^*	8.1384	9.9257		14.1959		34.3551		46.8274		15.7147
map2	APF-IRRT^*	3.9932	4.4203		7.0841		4.1881		3.8764		5.9439
map2	AAPF-IRRT^*	0.8612	0.8457		1.4761		2.0935		1.3418		1.5886
3D	IRRT^*	20.2574	32.2878		20.6133		20.4921		91.9290		91.6779
3D	AAPF-IRRT^*	14.6385	17.2127		16.4404		14.7832		11.1154		12.0652
环境	算法	t_cost/s
环境	算法	实验7		实验8		实验9		实验10		平均
map1	IRRT^*	83.1127		12.6667		51.1817		69.0751		40.8606
map1	APF-IRRT^*	7.5079		5.7140		5.2071		8.3225		7.35045
map1	AAPF-IRRT^*	2.9592		2.2278		0.8121		1.4574		1.9464
map2	IRRT^*	10.4236		8.9757		64.0088		10.4278		22.2993
map2	APF-IRRT^*	4.7732		4.4239		7.1845		3.9987		4.9886
map2	AAPF-IRRT^*	1.5822		1.2133		1.7045		0.9273		1.3634
3D	IRRT^*	20.6224		24.5895		29.4656		168.4688		52.0403
3D	AAPF-IRRT^*	16.6168		10.1393		13.0260		11.1180		13.7156