复杂环境下基于改进Informed RRT*的无人机路径规划算法

doi:10.16183/j.cnki.jsjtu.2022.442

上海交通大学学报 ›› 2024, Vol. 58 ›› Issue (4): 511-524.doi: 10.16183/j.cnki.jsjtu.2022.442

复杂环境下基于改进Informed RRT^*的无人机路径规划算法

刘文倩¹, 单梁¹(), 张伟龙¹, 刘成林², 马强¹

1.南京理工大学自动化学院,南京 210094
2.江南大学轻工过程先进控制教育部重点实验室,江苏无锡 214122

收稿日期: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-),硕士生,从事无人机路径规划与控制算法研究.
基金资助:
国家自然科学基金资助项目(61973139);江苏省自然科学基金面上项目(BK20191286);中央高校基本科研业务费专项资金资助项目(30920021139)

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

LIU Wenqian¹, SHAN Liang¹(), ZHANG Weilong¹, LIU Chenglin², MA Qiang¹

1. School of Automation, Nanjing University of Science and Technology, Nanjing 210094, China
2. Key Laboratory of Advanced Process Control of Light Industry of the Ministry of Education, Jiangnan University, Wuxi 214122, Jiangsu, China

Received:2022-11-04 Revised:2022-12-12 Accepted:2022-12-21 Online:2024-04-28 Published:2024-04-30

摘要/Abstract

摘要：

针对无人机在复杂环境中进行路径规划时,快速搜索随机树(RRT)算法易出现规划时间长、路径冗余、狭窄空间中易陷入局部约束导致规划失败的问题,提出一种改进的Informed RRT^*算法.首先,引入人工势场法使采样点按照势场下降的方式向目标点移动,以提高RRT树扩展的目的性和方向性.然后,考虑随机树在扩展过程中全局环境的复杂度,引入自适应步长调整策略以增加随机树在无障碍环境下的扩展速度,并在随机树扩展的过程中加入相关约束条件以确保生成路径的可行性.在找到第一条可达路径后,采用变化的椭圆或椭球采样域限制采样点选取和自适应步长的扩展范围,加快算法收敛到渐进最优的速度.最后,在复杂二维和三维环境下进行传统算法和改进算法的对比实验,仿真分析表明:改进算法可以在很少的迭代次数下找到更优的初始路径,更快地锁定椭圆或椭球采样域,从而给路径优化留出更多时间,算法规划效果更好.

关键词: 路径规划, Informed RRT^*, 人工势场法, 自适应步长, 椭圆采样域

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

中图分类号:

TP242.2

刘文倩, 单梁, 张伟龙, 刘成林, 马强. 复杂环境下基于改进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.

图/表 27

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

图17

图18

图19

图20

图21

图22

图23

图24

图25

表1

图26

参考文献 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

复杂环境下基于改进Informed RRT^*的无人机路径规划算法

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 27

参考文献 25

相关文章 15

编辑推荐

Metrics

本文评价

[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.

复杂环境下基于改进Informed RRT*的无人机路径规划算法

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 27

参考文献 25

相关文章 15

编辑推荐

Metrics

本文评价

复杂环境下基于改进Informed RRT^*的无人机路径规划算法

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