基于改进RRT*FN算法的机器人路径规划

针对固定节点数的渐近最优快速扩展随机数算法(RRT*FN)精度低、收敛到最优值速度慢等问题,提出一种改进的RRT*FN路径规划算法,并用于解决二维静态环境下的移动机器人全局路径规划问题.首先,改进算法使用与RRT*FN算法相同的均匀采样方法进行路径搜索,当搜索到一条初始路径时,在之后的路径规划中使用启发式采样方法.在之后的每次迭代中,改进算法在椭圆子集采样方法与路径点邻近区域采样方法中随机选择一种作为当前采样方法.然后,当树中的总节点数达到预设值时,对树中的叶子结点采用加权方法进行删除.通过给予采样区域内的叶子结点更高的权重,从而将采样区域外的叶子结点以更高概率删除,得以保留树中的高性能节点,以便提高算法性能.最后,通过仿真实验验证改进算法的有效性.

Robot path planning based on improved RRT*FN algorithm

Aiming at the problems of low accuracy and slow convergence of rapidly-exploring random trees star fixed nodes(RRT*FN) algorithms, this paper proposes an improved RRT*FN path planning algorithm, which is used to solve the global path planning problem of mobile robots in the two-dimensional static environment. Firstly, the improved algorithm uses the same uniform sampling method as the RRT*FN algorithm for path planning. When the improved algorithm gets an initial path, the heuristic sampling method will be used in subsequent path searching. In each next iteration, the improved algorithm randomly selects a method from the ellipse subset sampling method and the path point neighboring area sampling method as the current sampling method. Then, when the total number of nodes in the tree reaches the preset value, the leaf nodes in the tree are deleted using a weighted method. By giving higher weight to the leaf nodes in the sampling area, the leaf nodes outside the sampling area are deleted with a higher probability. Therefore, high-performance nodes in the tree can be retained, and algorithm performance is improved. Finally, the simulation experiments verify the effectiveness of the improved algorithm.