Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (16): 10-17.DOI: 10.3778/j.issn.1002-8331.1905-0061

Previous Articles     Next Articles

Summary of Rapidly-Exploring Random Tree Algorithm in Robot Path Planning

CHEN Qiulian, JIANG Huanyu, ZHENG Yijun   

  1. School of Computer and Electronical Information, Guangxi University, Nanning 530004, China
  • Online:2019-08-15 Published:2019-08-13



  1. 广西大学 计算机与电子信息学院,南宁 530004

Abstract: Path planning is a vital research content of mobile robot technology. Rapidly-Exploring Random Tree(RRT) algorithm has been studied and developed since it was proposed because of its successful application in robot path planning. As a novel random node sampling algorithm, compared with traditional algorithms, the rapidly-exploring random tree has the characteristics of short modeling time, robust search ability and convenience to add nonholonomic constraints. This paper introduces the basic principle and properties of the rapidly-exploring random tree algorithm, summarizes the research status of the algorithm from the aspects of single random tree extension, multiple random tree extension and other improvements. Finally, the future research directions and challenges of the algorithm are prospected.

Key words: robot path planning, rapidly-exploring random tree, random sampling algorithm, nonholonomic constraint

摘要: 路径规划是移动机器人的重要研究内容。快速扩展随机树(Rapidly-Exploring Random Tree,RRT)算法因在机器人路径规划中的成功应用,自提出以来就得到了极大的研究与发展。快速扩展随机树作为一种新颖的随机节点采样算法,相对传统路径规划算法,具有建模时间短、搜索能力强、方便添加非完整约束等优点。介绍了快速扩展随机树算法的基本原理与性质,并从单向随机树扩展、多向随机树扩展、其他改进等方面概括了算法的研究现状。最后,展望了算法未来的研究方向与挑战。

关键词: 机器人路径规划, 快速扩展随机树, 随机采样算法, 非完整约束