Real-Time Sampling Path Replanning of Mobile Robot

doi:10.3778/j.issn.1002-8331.2012-0053

Abstract

Abstract:

A real-time sampling replanning algorithm DRT-RRT* using the reverse optimal rapidly-exploring random tree is proposed to solve poor path quality, serious jitter, poor real-time optimization effect when the traditional sampling-based planning algorithm is replanning in the dynamic environment due to its strong randomness. Firstly, a pruning strategy based on triangle inequality is introduced to smooth the path to reduce the inflection point. Then, in the process of optimizing the execution path, a combined sampling strategy and a local terminal jumping strategy are proposed, which focus the optimization target from the global path to the local path segment from the current position of the robot to the nearest inflection point, and then the execution path segment is modified in real time, so as to improve the stability of the path quality. Next, only the affected random trees are pruned in the path replanning, and the goal-biased sampling strategy is introduced when the random tree grows again, which works together with the combined sampling strategy to improve the search speed and stability of the path. Finally, RRT*-Pruning which is added triangular inequality pruning strategy and DRT-RRT* and RRT* are compared and analyzed. The experimental results verify the efficiency and stability of DRT-RRT* replanning.

Key words: mobile robot, path planning, Dynamic Real-Time Rapidly-exploring Random Trees*（DRT-RRT*）, combined sampling, real-time path replaning

摘要：

针对传统采样规划算法因随机性强，在动态环境中重规划时路径质量差，抖动严重，实时优化效果不明显等问题，提出了一种利用反向生长最优快速搜索随机树的实时采样重规划算法DRT-RRT*（Dynamic Real-Time RRT*）。引入基于三角不等式的剪枝策略对路径进行平滑处理以减少路径拐点；提出了组合采样策略和局部终点跳动策略，将优化目标由全局路径聚焦于机器人当前位置至最近路径拐点的局部路径段，实时对执行路径段进行修正，进而提高路径质量的稳定性；在路径重规划时仅对受影响的随机树枝进行修剪，并在随机树重新生长时引入了目标偏置采样策略，与组合采样策略共同作用，提高路径搜索速率和稳定程度；将DRT-RRT*与RRT*和增加了三角不等式剪枝策略的RRT*-Pruning进行仿真对比分析，实验结果验证了DRT-RRT*重规划的高效性和稳定性。

关键词: 移动机器人, 路径规划, 动态实时-快速搜索随机树*（DRT-RRT*）, 组合采样, 实时重规划

TU Rui, WANG Wenge, LU Chengyang. Real-Time Sampling Path Replanning of Mobile Robot[J]. Computer Engineering and Applications, 2021, 57(20): 157-163.

涂睿，王文格，卢成阳. 移动机器人实时采样路径重规划[J]. 计算机工程与应用, 2021, 57(20): 157-163.

References

[1] DIAZ D，KELLY R.On modeling and position tracking control of the generalized differential driven wheeled mobile robot[C]//IEEE International Conference on Automatica（ICA-ACCA），2016：1-6.
[2] 霍凤财，迟金，黄梓健，等.移动机器人路径规划算法综述[J].吉林大学学报（信息科学版），2018，36（6）：639-647.
HUO F C，CHI J，HUANG Z J，et al.Overview of path planning algorithms for mobile robots[J].Journal of Jilin University（Information Science Edition），2018，36（6）：639-647.
[3] 刘新宇，谭力铭，杨春曦，等.未知环境下的蚁群-聚类自适应动态路径规划[J].计算机科学与探索，2019，13（5）：846-857.
LIU X Y，TAN L M，YANG C X，et al.Self-adjustable dynamic path planning of unknown environment based on ant colony-clustering algorithm[J].Journal of Frontiers of Computer Science and Technology，2019，13（5）：846-857.
[4] LAVALLE S M.Rapidly-exploring random trees：a new tool for path planning[R].Iowa State University，1998.
[5] 郭银景，孟庆良，孔芳，等.AUV路径规划算法研究现状与展望[J].计算机科学与探索，2020，14（12）：1981-1994.
GUO Y J，MENG Q L，KONG F，et al.Research status and prospect of AUV path planning algorithms[J].Journal of Frontiers of Computer Science and Technology，2020，14（12）：1981-1994.
[6] LAN X，CAIRANO S D.Continuous curvature path planning for semi-autonomous vehicle maneuvers using RRT[C]//2015 European Control Conference（ECC），2015.
[7] SOZZI A，BONFè M，FARSONI S，et al.Dynamic motion planning for autonomous assistive surgical robots[J].Electronics，2019，8（9）：957.
[8] 刘紫燕，张杰.改进RRT算法的室内移动机器人路径规划[J].计算机工程与应用，2020，56（9）：190-197.
LIU Z Y，ZHANG J.Path planning using improved RRT algorithm for indoor mobile robot[J].Computer Engineering and Applications，2020，56（9）：190-197.
[9] BAK J H，HWANG S W，YOON J，et al.Collision-free path planning of cable-driven parallel robots in cluttered environments[J].Intelligent Service Robotics，2019，12（3）：243-253.
[10] 张卫波，肖继亮.改进RRT在复杂环境下智能车路径规划中的应用[J/OL].中国公路学报：1-16[2020-12-22].http：//kns.cnki.net/kcms/detail/61.1313.U.20200628.1740.002.html.
ZHANG W B，XIAO J L.Application of improved RRT in intelligent vehicle path planning under complicated environment[J/OL].China Journal of Highway and Transport：1-16[2020-12-22].http：//kns.cnki.net/kcms/detail/61.
1313.U.20200628.1740.002.html.
[11] BRUCE J，VELOSO M M.Real-time randomized path planning for robot navigation[C]//IEEE/RSJ International Conference on Intelligent Robots & Systems，2002.
[12] FERGUSON D，KALRA N，STENTZ A.Replanning with RRTs[C]//Proceedings 2006 IEEE International Conference on Robotics and Automation，2006.
[13] 刘成菊，韩俊强，安康.基于改进RRT算法的RoboCup机器人动态路径规划[J].机器人，2017，39（1）：8-15.
LIU C J，HAN J Q，AN K.Dynamic path planning based on an improved RRT algorithm for RoboCup robot[J].Robot，2017，39（1）：8-15.
[14] 司徒华杰，雷海波，庄春刚.动态环境下基于人工势场引导的RRT路径规划算法[J].计算机应用研究，2021（3）：714-717.
SITU H J，LEI H B，ZHUANG C G.Artificial potential field based RRT algorithm for path planning in dynamic environment[J].Application Research of Computers，2021（3）：714-717.
[15] KARAMAN S，FRAZZOLI E.Sampling-based algorithms for optimal motion planning[M].[S.l.]：Sage Publications，Inc，2011.
[16] 张伟民，付仕雄.基于改进RRT*算法的移动机器人路径规划[J].华中科技大学学报（自然科学版），2021，49（1）：31-36.
ZHANG W M，FU S X.Mobile robot path planning based on improved RRT* algorithm[J].Journal of Huazhong University of Science & Technology（Natural Science Edition），2021，49（1）：31-36.
[17] CONNELL D，LA H M.Dynamic path planning and replanning for mobile robots using RRT*[C]//IEEE International Conference on Systems，2017：1429-1434.
[18] ISLAM F，NASIR J，MALIK U，et al.RRT?-smart：rapid convergence implementation of RRT? towards optimal solution[C]//International Conference on Mechatronics & Automation，2012.