Abstract: The Rapidly exploring Random Tree star (RRT^*) algorithm ensures its probabilistic completeness and asymptotic optimality in the path planning process, but still has problems such as slow convergence speed and large and dense sampling space. In order to speed up the convergence of the algorithm, a fast obtaining method of optimal path based on artificial potential field method and informed set sampling was proposed. First, the artificial potential field method was used to construct an initial path from the starting point to the target point. Then, the positions of and the distance between the starting point and the target point as well as the path cost of the initial path were used as parameters to construct the initial informed sampling set. At last, the sampling was limited in the informed set, and the range of the informed sampling set was adjusted during the running process of the algorithm to accelerate the path convergence speed. Simulation experiments show that, Potential Informed-RRT^* (PI-RRT^*) algorithm based on the artificial potential field combined with informed sampling method reduces the number of sampling points by about 67%, and shortens the algorithm running time by about 74.5% on average compared with RRT^* algorithm; and has the number of sampling points reduced by about 40%-50%, the algorithm running time shortened by about 62.5% on average compared with Informed RRT^* (Informed-RRT^*) algorithm. The proposed optimal path convergence method greatly reduces the number of redundant sampling and the algorithm running time, has higher algorithm efficiency, and converges to the optimal path with faster speed.

Key words: path planning, Rapidly exploring Random Tree (RRT) algorithm, Artificial Potential Field (APF) method, informed sampling set, Informed Rapidly exploring Random Tree star (Informed-RRT^*) algorithm

摘要： 具有渐进最优性的快速搜索随机树（RRT^*）算法在路径规划过程中确保了其概率完备性和渐进最优性，然而仍存在收敛速度慢且产生大而密集的采样空间等问题。为了加快算法的收敛速度，提出了一种基于人工势场法和启发集合采样来快速获取最优路径的方法。首先，利用人工势场法构建出一条由起点到目标点的初始路径；然后，以起点和目标点的位置和之间的距离以及初始路径的路径代价作为参数来构建初始启发采样集合；最后，限定在启发集合内进行采样，并且在算法进行的过程中调整启发采样集合的范围，进而加快路径收敛速度。仿真实验中，获取相同路径代价的路径时，所提人工势场结合启发式采样的方法为基础的结合人工势场法和启发采样策略的快速获取最优路径的RRT^*（PI-RRT^*）算法相较于RRT^*算法，采样点数减少了约67%，算法运行时间平均缩短了约74.5%；相较于启发式RRT^*（Informed-RRT^*）算法，采样点数减少了约40~50%，算法运行时间平均缩短了约62.5%。所提出的最优路径收敛方法大量减少了冗余采样次数并缩短了算法运行时间，具有更高的算法效率，收敛到最优路径的速度更快。

关键词: 路径规划, 快速搜索随机树算法, 人工势场法, 启发采样集合, 启发式渐进最优快速搜索随机树算法