Abstract:

As for the problems of searching too many nodes and running inefficiently on traditional A-Star algorithm, this paper proposes a path planning algorithm with obligatory node constraint. Considering the layout of obstacles, this algorithm limites searching directions of A* by finding out an obligatory node of shortest path. And then it connects both shortest path segments to form the shortest path. An experiment is performed between traditional A-Star algorithm and improved algorithm in maps of 100×100 grids. It shows that the operation efficiency of A-Star algorithm has been significantly improved.

Key words: A-Star algorithm, obstacle block, landing point, simulate path, obligatory node, path planning

摘要：

针对传统A*算法存在搜索范围广、运行效率低的问题，提出了一种引入必经点约束的路径规划算法。该算法结合障碍物分布特点，通过寻找最短路径必经点，实现对A*搜索方向的约束，再对最短路径段进行拼接得到最短路径。最后，在100×100网格地图中进行对比实验，结果表明，引入必经点约束的改进算法比传统A*算法的结点访问量大幅降低，运行效率得到显著提高。

关键词: A*算法, 障碍物块, 登陆点, 模拟路径, 必经点, 路径规划