上海交通大学学报 ›› 2024, Vol. 58 ›› Issue (4): 511-524.doi: 10.16183/j.cnki.jsjtu.2022.442
收稿日期:
2022-11-04
修回日期:
2022-12-12
接受日期:
2022-12-21
出版日期:
2024-04-28
发布日期:
2024-04-30
通讯作者:
单 梁,副教授;E-mail:shanliang@njust.edu.cn.
E-mail:shanliang@njust.edu.cn
作者简介:
刘文倩(2000-),硕士生,从事无人机路径规划与控制算法研究.
基金资助:
LIU Wenqian1, SHAN Liang1(), ZHANG Weilong1, LIU Chenglin2, MA Qiang1
Received:
2022-11-04
Revised:
2022-12-12
Accepted:
2022-12-21
Online:
2024-04-28
Published:
2024-04-30
摘要:
针对无人机在复杂环境中进行路径规划时,快速搜索随机树(RRT)算法易出现规划时间长、路径冗余、狭窄空间中易陷入局部约束导致规划失败的问题,提出一种改进的Informed RRT*算法.首先,引入人工势场法使采样点按照势场下降的方式向目标点移动,以提高RRT树扩展的目的性和方向性.然后,考虑随机树在扩展过程中全局环境的复杂度,引入自适应步长调整策略以增加随机树在无障碍环境下的扩展速度,并在随机树扩展的过程中加入相关约束条件以确保生成路径的可行性.在找到第一条可达路径后,采用变化的椭圆或椭球采样域限制采样点选取和自适应步长的扩展范围,加快算法收敛到渐进最优的速度.最后,在复杂二维和三维环境下进行传统算法和改进算法的对比实验,仿真分析表明:改进算法可以在很少的迭代次数下找到更优的初始路径,更快地锁定椭圆或椭球采样域,从而给路径优化留出更多时间,算法规划效果更好.
中图分类号:
刘文倩, 单梁, 张伟龙, 刘成林, 马强. 复杂环境下基于改进Informed RRT*的无人机路径规划算法[J]. 上海交通大学学报, 2024, 58(4): 511-524.
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.
表1
不同地图环境下原始算法与改进算法找到初始路径所耗费时间
环境 | 算法 | tcost/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 | ||||
环境 | 算法 | tcost/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 |
[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. |
[1] | 董德金, 范云锋, 蔡云泽. 一种具有必经点约束的非结构化环境路径规划方法[J]. 空天防御, 2024, 7(1): 71-80. |
[2] | 黄鹤, 高永博, 茹锋, 杨澜, 王会峰. 基于自适应黏菌算法优化的无人机三维路径规划[J]. 上海交通大学学报, 2023, 57(10): 1282-1291. |
[3] | . 基于栅格图特征点提取下的蚁群算法路径规划[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 86-99. |
[4] | 裘柯钧, 鲍中凯, 陈璐. 民用客机总装车间自动引导车任务分配及路径规划[J]. 上海交通大学学报, 2023, 57(1): 93-102. |
[5] | 陈禹伊, 陈璐. 车辆路径规划问题的逆向优化方法[J]. 上海交通大学学报, 2022, 56(1): 81-88. |
[6] | 李昭莹, 欧一鸣, 石若凌. 基于深度Q网络的改进RRT路径规划算法[J]. 空天防御, 2021, 4(3): 17-23. |
[7] | 李征, 陈建伟, 彭博. 基于伪谱法的无人机集群飞行路径规划[J]. 空天防御, 2021, 4(1): 52-59. |
[8] | 刘洋,陈璐. 养护车辆路径规划的鲁棒性优化方法[J]. 上海交通大学学报(自然版), 2018, 52(4): 388-394. |
[9] | 乐健,张华,叶艳辉,范宇. 基于旋转电弧传感机器人立焊焊缝的跟踪[J]. 上海交通大学学报(自然版), 2015, 49(03): 348-352. |
[10] | 杨乘东,钟继勇,陈玉喜,陈善本. 基于视觉识别的多层多道路径规划修正[J]. 上海交通大学学报(自然版), 2015, 49(03): 297-300. |
[11] | 许波,闵华清,肖芳雄. 蚁群算法求解离散最小约束去除问题[J]. 上海交通大学学报(自然版), 2015, 49(03): 383-386. |
[12] | 张铁,欧阳帆. 双机器人协调跟随运动的运动学分析与路径规划[J]. 上海交通大学学报(自然版), 2013, 47(08): 1251-1256. |
[13] | 胡彬a, 王冰a, 王春香b, 杨明a. 一种基于时间窗的自动导引车动态路径规划方法 [J]. 上海交通大学学报(自然版), 2012, 46(06): 967-971. |
[14] | 白杰,杨根科,潘常春,孙凯. 基于改进分散搜索算法的无人机路径规划 [J]. 上海交通大学学报(自然版), 2011, 45(02): 173-0178. |
[15] | 王丽军,王景川,陈卫东. 动态环境下智能轮椅的路径规划与导航 [J]. 上海交通大学学报(自然版), 2010, 44(11): 1524-1528. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||