欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
目前存在大量的路径搜索算法，但大多数如传统的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.
同期刊论文项目
同项目期刊论文
Local similarity and diversity preserving discriminant projection for face and handwriting digits re
A study on relationship between generalization abilities and fuzziness of base classifiers in ensemb
An improved differential evolution and its application to determining feature weights in similarity-
期刊信息
位置：