Journal of Frontiers of Computer Science and Technology ›› 2021, Vol. 15 ›› Issue (4): 723-732.DOI: 10.3778/j.issn.1673-9418.2004037

• Artificial Intelligence • Previous Articles     Next Articles

Vortex Artificial-Potential-Field Guided RRT* for Path Planning of Mobile Robot

CAO Kai, CHEN Yangquan, GAO Song, GAO Jiajia   

  1. 1. School of Mechatronics Engineering, Xi'an Technological University, Xi'an 710021, China
    2. School of Electronic Information Engineering, Xi'an Technological University, Xi'an 710021, China
    3. School of Engineering, University of California, Merced 95343, USA
  • Online:2021-04-01 Published:2021-04-02

涡流人工势场引导下的RRT*移动机器人路径规划

曹凯陈阳泉高嵩高佳佳   

  1. 1. 西安工业大学 机电工程学院,西安 710021
    2. 西安工业大学 电子信息工程学院,西安 710021
    3. 加州大学默塞德分校 工程学院,美国 默塞德 95343

Abstract:

The rapidly-exploring random tree (RRT) has the problems of slow convergence, dense sampling nodes, and complicated path twists under the condition of dense obstacles and narrow channels. In this paper, a common variant of the RRT algorithm, RRT*, is designed with atificial potential fields (APF) to guide RRT* for path planning. First, vortex is used to constrain the repulsive field that diverges outward to form a vortex field along the tangential gradient. And vortex-APF (VAPF) is used to guide the sampling node to perform directional sampling in the RRT* deflection area, so as to reduce the execution time and accelerate the convergence speed. Simultaneously, the node rejection is used to remove high cost nodes and invalid nodes and a more centralized tree can be generated to reduce memory requirements. Finally, the extra nodes are pruned and the path is smoothed by vortex potential field to achieve the path optimization. Considering that the RRT algorithm has probabilistic randomness, 32 experi-ments are carried out on the RRT, the improved RRT* and the VAPF-RRT* respectively. The simulation results show that the VAPF-RRT* method significantly reduces the number of iterations, converges to shorter and smoother paths with fewer sampling nodes and execution time, and thus leads to more efficient memory utilization and an accelerated convergence rate.

Key words: path planning, rapidly-exploring random tree (RRT), arti?cial potential ?elds (APF), mobile robot, vortex

摘要:

为了解决快速扩展随机树(RRT)在障碍物密集、通道狭窄的环境中收敛速度缓慢、采样节点密集、路径曲折复杂等问题,围绕RRT的一种常见的变体算法RRT*,设计了一种由人工势场(APF)引导RRT*进行路径规划的方法。首先,使用涡流约束向外发散的斥力场,沿着切向梯度方向形成涡流场,并利用涡流人工势场(VAPF)在RRT*偏向区域中引导采样节点进行偏向采样,以减少执行时间,加快收敛速度;同时,利用节点拒绝技术去除高成本节点和无效节点,生成节点更为集中的轨迹树,降低内存需求;最后,通过修剪路径中的多余节点,并利用涡流势场的特性对路径进行平滑处理,达到路径优化的效果。考虑到RRT类算法具有概率随机性,对RRT算法、改进RRT*算法和VAPF-RRT*算法分别进行了32次对比实验。仿真结果表明,提出的VAPF-RRT*算法明显降低了迭代次数,以更少的采样节点和执行时间收敛到更短更平滑的路径,提高了内存利用率,加快了收敛速度。

关键词: 路径规划, 快速扩展随机树(RRT), 人工势场法(APF), 移动机器人, 涡流