基于MI-RRT*算法的路径规划研究

doi:10.3969/j.issn.1009-086x.2023.04.015

摘要/Abstract

摘要：

针对Informed-RRT(rapidly-exploring random tree)*算法收敛速度慢、优化效率低和生成路径无法满足实际需求等问题，开展了基于MI-RRT* (Modified Informed-RRT*)算法的路径规划研究，通过引入贪心采样和自适应步长的方法提高算法的收敛率，减少路径生成时间、降低内存占用；利用最小化Snap曲线优化的方法使路径平滑的同时动力也变化平缓，达到节省能量的效果，并提供实际可执行的路径。最后通过多组不同复杂度的实验环境表明，较Informed-RRT*算法MI-RRT*算法稳定性更高、所得规划路径平滑可执行，并且能够减少20%的迭代次数和25% 的搜索时间，得出在开阔以及密集环境中MI-RRT*算法较Informed-RRT*和RRT*算法有明显的优势。

关键词: Informed-RRT*算法, 贪心采样, 自适应步长, MI-RRT*, 最小化Snap曲线优化, RRT*算法

Abstract:

Aiming at the problems of the Informed-RRT（rapidly-exploring random tree）* algorithm， such as slow convergence speed， low optimization efficiency and inability to execute the generated path， path planning research based on MI-RRT* （modified informed-RRT*） algorithm is carried out. The method of greedy sampling and adaptive step size is introduced to improve the convergence rate of the algorithm， reduce the path generation time and the memory usage. Minimum Snap curve is used to make the path smooth and the power change smoothly， so as to achieve the effect of saving energy and the path to generate the executable. Several sets of different experimental environments are run to show that the MI-RRT* algorithm is more advantageous than the original algorithm， the resulting planned path is smooth executable and it can reduce the number of iterations by 20% and the search time by 25%. Compared with the open and dense environment， the MI-RRT* algorithm has obvious advantages over the Informed-RRT* ，RRT* algorithms.

Key words: Informed-RRT*（rapidly-exploring random tree） algorithm, reedy sampling, adaptive step size, modifiend informed-RRT*（MI-RRT*）, minimum snap, RRT* algorithm

中图分类号:

TP301.6

于强, 彭昭鸿, 黎旦, 李利彬, 高艺成. 基于MI-RRT^*算法的路径规划研究[J]. 现代防御技术, 2023, 51(4): 116-125.

Qiang YU, Zhaohong PENG, Dan LI, Libin LI, Yicheng GAO. Research of Path Planning Based on MI-RRT* Algorithm[J]. Modern Defense Technology, 2023, 51(4): 116-125.

图/表 12

参考文献 18

1	KUMAR P B， RAWAT H， PARHI D R. Path Planning of Humanoids Based on Artificial Potential Field Method in Unknown Environments［J］. Expert Systems： The International Journal of Knowledge Engineering， 2019，36（1）：1-12.
2	欧阳志宏，郭强. 改进蚁群算法的无人机突防航路规划［J］. 现代防御技术，2018， 46（1）：74-78，114.
	OUYANG Zhihong， GUO Qiang.Improved Ant Colony Algorithm for UAV Penetration Route Planning ［J］. Modern Defence Technology， 2018， 46（1）：74-78， 114.
3	赵玉新，刘利强，李刚. 无人智能运载器航路规划方法及其应用［M］. 北京：科学出版社，2014.
	ZHAO Yuxing， LIU Liqiang， LI Gang. Route Planning Method of Unmanned Intelligent Vehicle and Its Application ［M］. Beijing： Science Press，2014.
4	孔慧芳，盛阳. 基于改进A算法的AGV路径规划研究［J］. 现代制造工程，2021 （10）：60-64.
	KONG Huifang， SHENG Yang.Research on AGV Path Planning Based on Improved Aalgorithm ［J］. Modern Manufacturing Engineering， 2021 （10）：60-64.
5	LAMINI C， BENHLIMA S， ELBEKRI A. Genetic Algorithm Based Approach for Autonomous Mobile Robot Path Planning［J］.Procedia Computer Science， 2018：180-189.
6	SONG Baoye， WANG Zidong， ZOU Lei. On Global Smooth Path Planning for Mobile Robots Using a Novel Multimodal Delayed PSO Algorithm ［J］. Cognitive Computation， 2017（1）：5-17.
7	霍凤财，迟金，黄梓健，等.移动机器人路径规划算法综述［J］. 吉林大学学报（信息科学版），2018 （6）：639-647.
	HUO Fengcai， CHI Jin， HUANG Zijian， et al. A Survey of Path Planning Algorithms for Mobile Robots ［J］.Journal of Jilin University （Information Science Edition），2018（6）： 639-647.
8	KARAMAN S， FRAZZOLI E. Sampling-Based Algorithms for Optimal Motion Planning ［J］. International Journal of Robotics Research， 2011（7）：846-894.
9	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］∥IEEE/RSJ International Conference on Intelligent Robots and Systems， 2014：2997-3004.
10	RYU H， PARK Y. Improved Informed RRT* Using Gridmap Skeletonization for Mobile Robot Path Planning ［J］. International Journal of Precision Engineering and Manufacturing， 2019（11）：2033-2039.
11	张玉伟，左云波，吴国新，等. 基于改进Informed-RRT*算法的路径规划研究［J］. 组合机床与自动化加工技术，2020 （7）：21-25.
	ZHANG Yuwei， ZUO Yunbo， WU Guoxing， et al. Research on Path Planning Based on Improved Informed-RRT* Algorithm ［J］.Combined Machine Tools and Automated Processing Technology，2020 （7）：21-25.
12	DAI Jun， LI Dongfang， ZHAO Junwei， et al. Autonomous Navigation of Robots Based on the Improved Informed-RRT* Algorithm and DWA ［J］. Journal of Robotics， 2022，2022：1-9.
13	代军，李志明，李艳琴，等. 基于改进Informed-RRT*算法的机器人路径规划［J］. 河南理工大学学报（自然科学版），2021（1）：1-11.
	DAI Jun， LI Zhiming， LI Yanqin， et al. Robot Path Planning Based on Improved Informed-RRT* Algorithm ［J］.Journal of Henan University of Technology（Natural Science Edition）， 2021（1）：1-11.
14	朱奕航. 四旋翼无人机路径规划及跟踪控制技术［D］.南京：南京航空航天大学，2020.
	ZHU Yihang. Four-Rotor UAV Path Planning and Tracking Control Technology ［D］. Nanjing： Nanjing University of Aeronautics and Astronautics，2020.
15	陈晋音，施晋，杜文耀，等. 基于MB-RRT*的无人机航迹规划算法研究［J］. 计算机科学，2017 （8）：198-206.
	CHENG Jinyin， SHI jin， DU Wenyao， et al. Research on UAV Track Planning Algorithm Based on MB-RRT* ［J］. Computer Science， 2017 （8）：198-206.
16	MELLINGER D， KUMAR V. Minimum Snap Trajectory Generation and Control for Quadrotors ［C］∥2011 IEEE International Conference on Robotics and Automation. Shanghai，China： IEEE International Conference on Robotics and Automation （ICRA 2011），2011： 2520-2525.
17	韩晓微，刘宏宇，石泽亮，等. 移动机器人最小化snap与A*的联合轨迹优化［J］. 沈阳大学学报（自然科学版），2021 （4）：321-327.
	HAN Xiaowei， LIU Hongyu， SHI Zeliang， et al.Joint Trajectory Optimization of Minimizing Snap and A* for Mobile Robots ［J］. Journal of Shenyang University（Natural Science Edition）， 2021 （4）：321-327.
18	RICHTER C， BRY A， ROY N. Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments［C］∥Proceedings of the 16th International Symposium on Robotics Research （ISSR）， 2016： 114， 649-666.

地图	起始点	目标点	障碍物数量	障碍物占空比
Map1	（150，150）	（550，450）	1	36/1 200
Map2	（200，450）	（650，150）	11	59.5/1 200
Map3	（350，220）	（600，480）	42	286.1/1 200

地图	起始点	目标点	障碍物数量	障碍物占空比
Map1	（150，150）	（550，450）	1	36/1 200
Map2	（200，450）	（650，150）	11	59.5/1 200
Map3	（350，220）	（600，480）	42	286.1/1 200

地图	算法	初次得到可行解迭代次数	初次得到可行解所需时间/s	初次得到可行解的路径长度	总迭代次数
Map1	RRT*	121	0.163	785.25	200
	Informed-RRT*	72	0.146	657.86	200
	MI-RRT*	12	0.131	563.94	200
Map2	RRT*	217	0.365	663.86	400
	Informed-RRT*	124	0.234	679.12	400
	MI-RRT*	35	0.185	583.59	400
Map3	RRT*	234	0.604	617.75	400
	Informed-RRT*	193	0.544	504.57	400
	MI-RRT*	154	0.415	464.77	400

地图	算法	初次得到可行解迭代次数	初次得到可行解所需时间/s	初次得到可行解的路径长度	总迭代次数
Map1	RRT*	121	0.163	785.25	200
	Informed-RRT*	72	0.146	657.86	200
	MI-RRT*	12	0.131	563.94	200
Map2	RRT*	217	0.365	663.86	400
	Informed-RRT*	124	0.234	679.12	400
	MI-RRT*	35	0.185	583.59	400
Map3	RRT*	234	0.604	617.75	400
	Informed-RRT*	193	0.544	504.57	400
	MI-RRT*	154	0.415	464.77	400

路径长度	算法	Map1	Map2	Map3
迭代100次所得路径长度	RRT*	-	-	-
	Informed-RRT*	657.86	679.12	504.57
	MI-RRT*	563.94	583.59	464.77
迭代500次所得路径长度	RRT*	785.25	694.05	648.11
	Informed-RRT*	642.46	630.55	441.99
	MI-RRT*	551.22	576.49	425.14
迭代1 000次所得路径长度	RRT*	701.38	663.86	637.89
	Informed-RRT*	617.26	617.88	425.14
	MI-RRT*	551.22	575.51	420.93
迭代2 000次所得路径长度	RRT*	670.54	647.60	526.31
	Informed-RRT*	616.15	611.19	422.80
	MI-RRT*	547.19	564.08	419.86
迭代3 000次所得路径长度	RRT*	649.61	643.62	506.58
	Informed-RRT*	611.49	609.63	422.50
	MI-RRT*	541.59	562.95	409.42
迭代4 000次所得路径长度	RRT*	591.14	629.36	465.58
	Informed-RRT*	588.33	591.82	409.74
	MI-RRT*	538.41	560.22	409.42
迭代5 000次所得路径长度	RRT*	591.14	629.36	414.02
	Informed-RRT*	588.33	591.82	409.74
	MI-RRT*	536.67	560.22	408.77