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

Multi-level MQA-A~* Path Planning Algorithm Based on Adjacent Node Aggregation

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

A multiscale quarter aggregation A＊ （MQA-A＊） algorithm was developed as an improved A＊ algorithm to plan path efficiently on large and complex grid maps. The algorithm builds high-level abstract grid maps layer by layer via adjacent grid aggregation, generates a rough path on the high-level map, and refines the rough path down to the original grid map based on the intra-connection information within high-level aggregation grids. MQA-A＊ was demonstrated in several scenarios, which varied in the complexity of obstacle distribution. The experiments showed that MQA-A＊ was able to improve the computational efficiency significantly in reducing memory usage and decreasing algorithm CPU time. Particularly, the algorithm can obtain much better performance as the proportion of examined grids increases.