SUO Chao, HE Lile
（College of Electrical & Mechanical Engineering, Xi’an University of Architecture & Technology, Xi’an 710055, China）
Abstract：In order to solve the problem of path planning of mobile robots in a dynamic environment, an improved rapidly-exploring random tree* (RRT*) algorithm is proposed in this paper. First, the target bias sampling is introduced to reduce the randomness of the RRT* algorithm, and then the initial path planning is carried out in a static environment. Secondly, apply the path in a dynamic environment, and use the initially planned path as the path cache. When a new obstacle appears in the path, the invalid path is clipped and the path is replanned. At this time, there is a certain probability to select the point in the path cache as the new node, so that the new path maintains the trend of the original path to a greater extent. Finally, MATLAB is used to carry out simulation experiments for the initial planning and replanning algorithms, respectively. More specifically, compared with the original RRT* algorithm, the simulation results show that the number of nodes used by the new improved algorithm is reduced by 43.19% on average.
Key words：mobile robot; path planning; rapidly-exploring random tree* (RRT*) algorithm; dynamic environment; target bias sampling
References
［1］HUO F C, CHI J, HUANG Z J, et al. Review of path planning for mobile robots. Journal of Jilin University (Information Science Edition), 2018, 36(6)： 639-647.
［2］SONG X R, REN Y Y, GAO S, et al. Survey on technology of mobile robot path planning. Computer Measurement & Control, 2019, 27(4)： 1-5, 17.
［3］CHEN Q L, JIANG H Y, ZHENG Y J. Summary of rapidly-exploring random tree algorithm in robot path planning. Computer Engineering and Applications, 2019, 55(16)： 10-17.
［4］CHOUDHURY S, GAMMELL J D, BARFOOT T D, et al. Regionally accelerated batch informed trees (RABIT*)： a framework to integrate local information into optimal path planning//International Conference on Robotics and Automation, May 16-21, 2016, IEEE, Sweden, Stockholm. Washington: IEEE computer Society, 2016: 4207-4214.
［5］IRAM N, AMNA K, HYEJEONG R, et al. Optimal path planning in cluttered environment using RRT*-AB. Intelligent Service Robotics, 2018, 11(1)： 41-52.
［6］WANG C, MENG M Q. Variant step size RRT：an efficient path planner for UAV in complex environments//International Conference on Real-Time Computing and Robotics， Jun. 6-10, 2016, IEEE, Angkor Wat, Cambodia. Washington: IEEE Computer Society, 2016： 555-560.
［7］HYEJEONG R, YOUNGHOON P. Improved informed RRT* using grid map skeletonization for mobile robot path planning. International Journal of Precision Engineering and Manufacturing, 2019, 20(11)： 2033-2039.
［8］SHIARLIS K, MESSIAS J, WHITESON S. Rapidly exploring learning trees//International Conference on Robotics and Automation, May 29-Jun. 3, 2017, IEEE, Singapore. Washington: IEEE Computer Society, 2017： 541-548.
［9］ICHTER B, HARRISON J, PAVONE M. Learning sampling distributions for robot motion planning//International Conference on Robotics and Automation, May 21-25, 2018, IEEE, Brisbane, Australia. Washington: IEEE Computer Society, 2018： 7087-7094.
［10］KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 2010, 30(7)： 846-894.
［11］FERGUSON D, KALRA N, STENTZ A. Replanning with RRTs//International Conference on Robotics and Automation, May 15-19, 2006, IEEE, Orlando, Florida, USA. Washington: IEEE Computer Society, 2006： 1243-1248.
［12］LAVALLE S M, KUFFNER J J J. Randomized kinodynamic planning. International Journal of Robotics & Research, 1999, 15(5)： 378-400.
［13］LIU C J, HAN J Q, AN K. Dynamic path planning based on an improved RRT algorithm for RoboCup robot. Robot, 2017, 39(1)：8-15
基于改进RRT*算法的动态路径规划策略
索 超， 贺利乐
（西安建筑科技大学 机电工程学院， 陕西 西安 710055）
摘 要: 为了进一步解决移动机器人在动态环境下的路径规划问题， 提出了一种改进的快速扩展随机树*（RRT*）算法。 首先， 引入目标偏置采样以降低RRT*算法的随机性， 在静态环境下进行路径初规划。 其次， 在动态环境下应用该路径， 并将初规划的路径作为路径缓存， 当路径中出现新障碍物时， 将无效路径进行裁剪并进行路径重规划， 此时在进行节点采样时， 有一定概率选择路径缓存中的点作为新节点， 使得新路径更大程度上保持原有路径的趋势。 最后， 使用MATLAB分别进行初规划、 重规划的仿真实验。 与传统RRT*算法进行了对比， 新的改进算法使用的节点数量平均减少了43.19%。
关键词： 移动机器人； 路径规划； RRT*算法； 动态环境； 目标偏置采样
引用格式：SUO Chao, HE Lile. Dynamic path planning strategy based on improved RRT* algorithm. Journal of Measurement Science and Instrumentation， 2022， 13（2）：198-208. DOI：10.3969／j.issn.1674-8042.2022.02.009
[full text view]
