Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (9): 190-197.DOI: 10.3778/j.issn.1002-8331.1903-0105

Previous Articles     Next Articles

Path Planning Using Improved RRT Algorithm for Indoor Mobile Robot

LIU Ziyan,ZHANG Jie   

  1. College of Big Data and Information Engineering, Guizhou University, Guiyang 550025, China
  • Online:2020-05-01 Published:2020-04-29

改进RRT算法的室内移动机器人路径规划

刘紫燕,张杰   

  1. 贵州大学 大数据与信息工程学院,贵阳 550025

Abstract:

Aiming at the defects of low sampling efficiency and high deviation from optimal solutions of basic RRT algorithm due to randomly selecting extended nodes, an improved RRT algorithm with goal-biased is proposed. After the extended nodes being selected by using the target bias strategy and the odor diffusion, random trees grow to target points. A path smoothing method based on B-spline curve is proposed, which has higher searching efficiency and path quality. The simulation results demonstrate that the path generated by the proposed algorithm is around 22.1% shorter than that of basic RRT algorithm and the path is smoother as well. Furthermore, the proposed algorithm has stronger ability of avoiding obstacles. Finally, the improved RRT algorithm is applied it to Turtlebot2 in real environment. The experimental results illustrate that the improved RRT algorithm achieves higher reliability and practicability.

Key words: path planning, RRT algorithm, target bias, odor diffusion, B-spline curve

摘要:

针对传统RRT(快速扩展随机树)寻路算法由于扩展点的随机选取而存在搜索平均、采样效率低、偏离最优解的缺陷,提出一种偏向目标型的改进RRT算法。该算法采用目标偏向策略和气味扩散法来改善扩展节点的选取,使得随机树的生长趋向于目标点,并提出一种基于3次B样条曲线的路径平滑方法,极大地提升了搜索效率和路径质量。在仿真环境下对算法有效性进行验证,并将算法应用到真实环境下。仿真结果表明,与传统RRT算法相比,改进算法的路径长度缩短约22.1%,且路径更为平滑,在复杂环境中避障能力强。将改进RRT算法应用到Turtlebot2中,在真实环境下开展实验,实验结果证明了该算法的可靠性和实用性。

关键词: 路径规划, RRT算法, 目标偏向, 气味扩散, B样条曲线