一种考虑地图分布信息的分层路径搜索算法

A Hierarchical Pathfinding Algorithm Based on Map Distribution Information

目前存在大量的路径搜索算法,但大多数如传统的A*,Dijkstra等算法没有考虑地图中障碍物的分布信息,造成不必要的存储和时间耗费.实际上,搜索空间的分布在很大程度上影响着算法的性能,因此提出一种结合障碍物分布信息和抽象图思想的分层路径搜索算法CDHPA*.该算法首先依据障碍物的分布将地图划分为不均等的子区域,划分区域的数目由可调阈值确定;然后将子区域边界上的非障碍点作为抽象节点来构成完整的抽象图.根据障碍分布,抽象节点之间的最短路径采用曼哈顿距离或自底向上融合算法来计算;最后在抽象图上找到抽象路径并进行细化,得到实际路径.CDHPA*在同一幅地图上进行多次寻路时仅需一次预处理,在线寻路相比同类方法 M-A*、HPA*更快,并且得出的路径为最优路径.

Most of the present pathfinding algorithms, such as traditional A ＊ and Dijkstra algorithm, did not consider the distribution information of obstacles in the map. That may cause unnecessary memory and time cost. In fact, the distribution information of the search space will greatly influence the performance of these algorithms. In this paper, we propose a new hierarchical pathfinding algo- rithm called CDHPA ＊ , which considers the obstacle distribution in the generation of abstract graph. Firstly, the given map is divided into unequal sub-regions based on the obstacle distribution, where the number of sub-regions can be determined by predefined thresh-old that can be adjusted. Secondly, the free boundary nodes on the sub-regions are connected as abstract nodes to form a complete ab-stract graph. The shortest path between each pair of abstract nodes is calculated by Manhattan distance or bottom-up fusion algorithm depending on the density of obstacles. Finally, find an abstract path on the generated abstract graph and then refine the abstract path to the actual path. CDHPA ＊ only needs one preprocess for multiple-task pathfinding in the same map. Compared with some typical al- gorithms such as M-A ＊ and HPA ＊ . CDHPA ＊ is faster in on-line searching and the path is optimal.