Journal of Shanghai Jiaotong University >
Unmanned Aerial Vehicle Path Planning Algorithm Based on Improved Informed RRT* in Complex Environment
Received date: 2022-11-04
Revised date: 2022-12-12
Accepted date: 2022-12-21
Online published: 2023-03-10
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.
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 Jiaotong University, 2024 , 58(4) : 511 -524 . DOI: 10.16183/j.cnki.jsjtu.2022.442
| [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. |
| 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. |
| [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. |
| 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. |
| 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. |
| [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. |
| [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. |
| [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. |
| 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. | |
| [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. |
| [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. |
/
| 〈 |
|
〉 |
