复杂环境下基于改进Informed RRT*的无人机路径规划算法
收稿日期: 2022-11-04
修回日期: 2022-12-12
录用日期: 2022-12-21
网络出版日期: 2023-03-10
基金资助
国家自然科学基金资助项目(61973139);江苏省自然科学基金面上项目(BK20191286);中央高校基本科研业务费专项资金资助项目(30920021139)
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
针对无人机在复杂环境中进行路径规划时,快速搜索随机树(RRT)算法易出现规划时间长、路径冗余、狭窄空间中易陷入局部约束导致规划失败的问题,提出一种改进的Informed RRT*算法.首先,引入人工势场法使采样点按照势场下降的方式向目标点移动,以提高RRT树扩展的目的性和方向性.然后,考虑随机树在扩展过程中全局环境的复杂度,引入自适应步长调整策略以增加随机树在无障碍环境下的扩展速度,并在随机树扩展的过程中加入相关约束条件以确保生成路径的可行性.在找到第一条可达路径后,采用变化的椭圆或椭球采样域限制采样点选取和自适应步长的扩展范围,加快算法收敛到渐进最优的速度.最后,在复杂二维和三维环境下进行传统算法和改进算法的对比实验,仿真分析表明:改进算法可以在很少的迭代次数下找到更优的初始路径,更快地锁定椭圆或椭球采样域,从而给路径优化留出更多时间,算法规划效果更好.
关键词： 路径规划; Informed RRT*; 人工势场法; 自适应步长; 椭圆采样域
刘文倩, 单梁, 张伟龙, 刘成林, 马强 . 复杂环境下基于改进Informed RRT*的无人机路径规划算法[J]. 上海交通大学学报, 2024 , 58(4) : 511 -524 . DOI: 10.16183/j.cnki.jsjtu.2022.442
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.
| [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. |
/
| 〈 |
|
〉 |
