基于邻接节点聚合的多层级MQA-A~*路径规划算法

作者：杨肖宁; 程承旗; 陈波; 童晓冲; 何静

来源：地理信息世界, 2018, 25(01): 71-94.

• 网格聚合
• 路径规划
• MQA-A~*
• 抽象网格地图

针对执行A~*算法的计算机资源消耗随网格规模的扩大而急剧增长的问题,提出了一种基于邻接节点聚合的多层级MQA-A~*(multiscalequarteraggregation-A~*)栅格路径规划算法。算法聚合邻接节点为抽象节点,从原始栅格地图起始逐层构造高层级抽象地图,通过A~*算法在高层级抽象地图上规划粗糙路径,并基于抽象网格内部连通属性及抽象网格间的连接信息将粗糙路径向低层级抽象地图逐层细化,最终得到原始栅格地图上的路径规划方案。实验结果表明,MQA-A~*栅格路径规划算法可以在保障规划路径长度的基础上大幅缩减计算机的内存消耗及算法计算时间,高层级抽象网格上的MQA-A~*算法的计算加速比随扩展节点占比提升而提高。

• 单位
  北京大学; 信息工程大学地理空间信息学院