改进Informed-RRT*的移动机器人路径规划算法研究

doi:10.3778/j.issn.1002-8331.2212-0131

摘要/Abstract

摘要： 针对目前Informed-RRT*算法在路径规划时速度慢，目的性差且所得路径不平滑的特点，提出了一种基于节点优化的改进Informed-RRT*路径规划算法。引入自适应t-分布函数改变随机点在不同环境下的分布概率，提高算法的效率。采用椭圆的焦距偏置策略，将单个偏置点扩展为整个椭圆焦距，使随机树的生长贴近起始点与目标点的最小距离，增加了算法的目的性。采用重选祖辈节点策略对整条路径减冗余，对于路径转折处采用对称多极式曲线法进行平滑处理。通过多组实验对比表明，改进后的Informed-RRT*算法搜索效率更高，目的性更强，且规划所得路径更为平滑。

关键词: 路径规划, Informed-RRT*, 节点优化, 路径平滑

Abstract: An improved Informed-RRT* path planning algorithm based on node optimization is proposed to address the characteristics of the current Informed-RRT* algorithm that is slow, poorly purposeful and unsmooth in path planning. The adaptive t-distribution function is introduced to change the distribution probability of random points in different environments to improve the efficiency of the algorithm. Then an elliptic focal bias strategy is used to extend a single bias point to the whole elliptic focal point to make the random tree grow close to the minimum distance between the starting point and the target point, which increases the purposefulness of the algorithm. Finally, the re-election grandparent node strategy is used to reduce redundancy for the whole path, and the symmetric multipole type curve method is used to smooth for the path turns. The improved Informed-RRT* algorithm has higher search efficiency, more purposefulness, and smoother planned paths by comparing the surface with multiple sets of experiments.

Key words: path planning, informed-RRT*, node optimization, path smoothing

靳午煊, 马向华, 赵金良. 改进Informed-RRT*的移动机器人路径规划算法研究[J]. 计算机工程与应用, 2023, 59(19): 75-81.

JIN Wuxuan, MA Xianghua, ZHAO Jinliang. Research on Path Planning Algorithm of Mobile Robot Based on Improved Informed-RRT*[J]. Computer Engineering and Applications, 2023, 59(19): 75-81.

参考文献

[1] 周睿慜，李辉.改进动态规划算法的移动机器人路径规划[J].计算机工程与应用，2020，56（21）：20-24.
ZHOU R M，LI H.Path planning of mobile robot based on improved dynamic programming algorithm[J].Computer Engineering and Applications，2020，56（21）：20-24.
[2] 叶颖诗，魏福义，蔡贤资.基于并行计算的快速Dijkstra算法研究[J].计算机工程与应用，2020，56（6）：58-65.
YE Y S，WEI F Y，CAI X Z.Research on fast Dijkstra algorithm based on parallel computing[J].Computer Engineering and Applications，2020，56（6）：58-65.
[3] HONG Z，SUN P，TONG X.Improved A-star algorithm for long-distance off-road path planning using terrain data map[J].ISPRS International Journal of Geo Information，2021，10（11）：785.
[4] RAHMANIAR W，RAKHMANIA A E.Mobile robot path planning in a trajectory with multiple obstacles using genetic algorithms[J].Journal of Robotics and Control（JRC），2022，3（1）：1-7.
[5] 李珺，段钰蓉，郝丽艳，等.混合优化算法求解同时送取货车辆路径问题[J].计算机科学与探索，2022，16（7）：1623-1632.
LI J，DUAN Y R，HAO L Y，et al.Hybrid optimization algorithm for vehicle routing problem with simultaneous delivery-pickup[J].Journal of Frontiers of Computer Science and Technology，2022，16（7）：1623-1632.
[6] 罗辉，蒋涛，周楠，许林，等.改进RRT的二阶段平滑搜索算法[J].计算机工程与应用，2022，58（12）：74-84.
LUO H，JIANG T，ZHOU N，et al.Improved RRT based twostage smooth search algorithm[J].Computer Engineering and Applications，2022，58（12）：74-84.
[7] 曹凯，陈阳泉，高嵩，等.涡流人工势场引导下的RRT*移动机器人路径规划[J].计算机科学与探索，2021，15（4）：723-732.
CAO K，CHEN Y Q，GAO S，et al.Vortex artificial-potential-field guided RRT* for path planning of mobile robot[J].Journal of Frontiers of Computer Science and Technology，2021，15（4）：723-732.
[8] 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]//Proceedings of 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems，2014：2997-3004.
[9] LI C，WANG C，WANG J，et al.Sliding-window informed RRT*：a method for speeding up the optimization and path smoothing[C]//Proceedings of 2021 IEEE International Conference on Real-time Computing and Robotics（RCAR），2021：141-146.
[10] 王杨斌，章伟，王为科，等.改进Informed-RRT*的动态环境路径规划算法[J].电光与控制，2022，29（5）：28-32.
WANG Y B，ZHANG W，WANG W K，et al.Improved dynamic environment path planning algorithm for Informed-RRT*[J].Electronics Optics & Control，2022，29（5）：28-32.
[11] 刘逸凡，黄友锐，韩涛.融合有向D*与RRT*的移动机器人路径规划算法[J].计算机仿真，2021，38（7）：317-322.
LIU Y F，HUANG Y R，HAN T.Path planning algorithm of mobile robot based on directional D* and RRT*[J].Computer Simulation，2021，38（7）：317-322.
[12] FAUZI M，POHAN M A R.Informed-RRT* using hybrid sampling to finding fast final path solution[J].Telekontran：Jurnal Ilmiah Telekomunikasi，Kendali dan Elektronika Tepan，2021，9（2）：94-105.
[13] UZUN G，?ZDEMIR A，BOGOSYAN S.N-sliced informed RRT*：intelligent sampling-based path planning in high eccentricity informed ellipsis[C]//Proceedings of IEEE 31st International Symposium on Industrial Electronics（ISIE），2022：741-746.
[14] ZHAO Y，LIU Y，GAO H，et al.Research on Infor-med-RRT* with improved initial solution[C]//Proceedings of the 4th International Conference on Intelligent Control，Measurement and Signal Processing（ICMSP），2022：977-981.
[15] 张玉伟，左云波，吴国新，等.基于改进Informed-RRT算法的路径规划研究[J].组合机床与自动化加工技术，2020（7）：21-25.
ZHANG Y W，ZUO Y B，WU G X，et al.Research on path planning based on improved Informed-RRT algorithm[J].Modular Machine Tool & Automatic Manufacturing Technique，2020（7）：21-25.