Abstract: To solve the problem of redundant exploration in the recursive expansion of the Fast Marching Tree algorithm (FMT*),a Direction Selection-based FMT* algorithm (DS-FMT*) was proposed.The algorithm generated a uniform distribution of  direction selection lines around the extended sample to judge the surrounding obstacles and select the direction favorable for expansion as the candidate exploration direction.Then,the actual exploration direction of the sample to be expanded to the next sample was compared with the candidate exploration direction.If the angle between the actual exploration direction and the candidate exploration direction was consistent,the sample in this direction would be given priority.Meanwhile,combined with the cost comparison of samples,the recursive expansion process of FMT* was improved to reduce the computational complexity.The proposed DS-FMT* algorithm was compared with other advanced similar algorithms,which proved that DS-FMT* could improve the planning efficiency while ensuring the good-quality of the path.Besides,the effectiveness of the proposed algorithm was verified by practical application experiments of mobile robot path planning.

Key words: path planning, heuristic strategy, direction selection, mobile robots, computational efficiency

摘要： 针对快速行进树算法(FMT*)在逐层递归扩展中产生的冗余探索问题,提出一种基于方向选择的快速行进树算法(DS-FMT*)。该算法首先对拟扩展样本的四周产生均匀分布的方向选择线,判断周围的障碍物情况并选择有利于扩展的方向作为候选探索方向。随后将拟扩展到下一样本的实际探索方向与候选探索方向做比对,若实际探索方向与候选探索方向夹角一致,则优先考虑扩展该方向的样本。同时,结合样本的成本对比,改进FMT*递归扩展过程,降低了计算复杂度。最后,将所提出的DS-FMT算法与其他同类算法进行仿真比较,证明了DS-FMT*在保证路径良好质量的同时,提高了规划效率。通过移动机器人路径规划的实际应用实验,验证了所提算法的有效性。

关键词: 路径规划, 启发式策略, 方向选择, 移动机器人, 计算效率