基于改进FMT^(*)算法的机器人路径规划

Path Planning of Robot Based on Improved FMT^(*) Algorithm

为了解决FMT^(*)算法在路径规划过程中收敛速度慢、路径优化效率低的问题,提出了一种基于启发函数的知情快速行进树(HIFMT^(*))算法。HIFMT^(*)算法将路径规划分为寻找初始路径和路径优化两个阶段,在寻找初始路径阶段,通过引入启发函数加快了算法的收敛速度。在路径优化阶段,先去除初始路径的冗余节点进行初步优化,再对处理后的路径进行知情优化操作,直到最终生成的路径为最优路径。通过对比HIFMT^(*)算法与同种类型的算法在二维地图中的仿真结果,在规则障碍物环境与杂乱障碍物环境下,HIFMT^(*)算法找到最优解的速度相较于FMT^(*)算法和BBI-FMT^(*)算法分别提升了75.73%和68.35%、53.25%和29.44%,验证了HIFMT^(*)算法的有效性。

In order to solve the problems of slow convergence speed and low efficiency of path optimization of FMT^(*) algorithm in the process of path planning,this paper proposes an informed fast marching tree(HIFMT^(*))algorithm based on heuristic function.HIFMT^(*) algorithm divides path planning into two stages:initial path finding and path optimization.In the initial path finding stage,heuristic function is introduced to speed up the convergence of the algorithm.In the path optimization stage,the redundant nodes of the initial path are removed for initial optimization,and then the processed path is optimized in an informed way until the finally generated path is the optimal path.Compared with the FMT^(*) algorithm and BBI-FMT algorithm,the simulation results of HIFMT^(*) algorithm in two-dimensional maps show that the speed of finding the optimal solution is increased by 75.73% and 68.35%,53.25%and 29.44%respectively in regular obstacle environment and chaotic obstacle environment,which verifies the effectiveness of HIFMT^(*) algorithm.