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

摘要：

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

关键词：路径搜索、地图分布、抽象图、自底向上、细化路径、最优路径

所属期刊栏目：34

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目60903088,61170040;河北省百名优秀人才支持计划项目CPRC002

在线出版日期：2013-12-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2607-2611