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

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

【关键词】网格聚合；路径规划；MQA-A*；抽象网格地图

【中图分类号】TP301.6 【文献标识码】A 【文章编号】1672-1586（2018）01-0071-06

0　引　言

栅格地图的路径规划问题是指在栅格地图环境中以较高效率规划出一条从起始点到目标点的最优或次优无碰撞的路径。对该问题的研究，在移动机器人、计算机游戏、人工智能等领域都具有重要意义。近年来许多学者和专家研究了多种应用于栅格地图的路径规划算法，如蚁群算法、遗传算法、神经网络法、人工势场法、A*算法等，其中，A*算法作为成熟的启发式算法，在移动机器人等领域已得到广泛应用和验证。

A*算法是Hart等人在1968年提出的一种启发式路径规划算法。A*算法在Dijkstra算法的基础上引入评价函数f (n )=g (n )+h (n )考察节点n 的代价，其中，g (n )表示从起始点到节点n 的实际路径长度，h (n )表示在不考虑障碍物的情况下从节点n 到目标点的估算路径长度，A*算法基于评价函数选择最优的移动节点，从而逐步构建完整路径。传统的A*算法可以规划从起始点到目标点的最优路径，然而，A*在算法效率上也存在以下问题：其一是内存方面，算法需要对网格节点的邻接信息及由算法引入的其他变量进行存储，其内存需求随网格规模的扩大而成比例增加，因此其用于大规模网格时内存消耗较大；其二是计算时间方面，算法扩展节点数目同样会随网格规模的扩大而成比例增加，特别地，算法在扩展节点中寻优的操作如果基于链表数据结构，扩展节点数目的增加会同时加深算法对链表的搜索深度，进而更严重地影响算法的规划路径效率。因此，结合以上两点，执行传统A*算法的计算机资源消耗会随网格规模的扩大而急剧增长，需要针对算法效率进行改进。

已有的对A*算法效率的改进主要是生成抽象地图，将真实栅格地图数据以一定规则生成总数较小的网格地图作为A*算法的输入地图，现有的生成抽象地图的方法包括四叉树划分法、多层级簇构建法、基于聚类的K-means A*算法等。为解决遍历大量邻居节点问题，H.Samet提出四叉树表示栅格地图 对非全障碍区域不断以四叉树形式划分，直到划分出的网格全为障碍区域（栅格标识为0）或非障碍区域（栅格标识为1），该方法可有效减少A*算法遍历的节点数，在n²个栅格的地图中只需遍历O (P )个节点即可得到路径，其中P表示障碍区域的总周长。但四叉树方法在障碍物区域较小、数量巨大且位置随机性较高的情况下，由于树的叶子节点繁多，遍历效率降低。此外，当起始点与目标点在树的根节点的不同子节点的后代中，由于树的多层次距离设定，规划出的路径可能与最优路径相差较大。A.Botea提出通过多层级地图结构优化A*算法（HPA），HPA算法将地图分为多个簇，通过簇内边界点以及簇之间的可通行边连接生成逻辑地图，多个簇合并形成更高层级的逻辑地图。该算法抽象出的节点数量较少，可有效提高A*的运算效率，但同样存在在障碍物随机性较高、地图复杂的情况下效率较低的问题，并且在第三层及更高层级优化效果不佳。

本文针对上述问题，提出一种基于邻接节点聚合的多层级算法，实现了对传统A*算法的效率改进。随后的内容首先从节点聚合方法、抽象网格构建方法、粗糙路径规划方法及路径细化方法这4个方面详细介绍了MQA-A*算法的实现途径；之后构造了3组仿真实验，对MQA-A*的内存需求、算法CPU时间及算法加速比进行研究，验证了算法在不同复杂程度的栅格地图上都可以对计算效率实现较大的提升，并进一步分析了仿真实验的扩展网格占比对算法加速比的影响。

1　多层级MQA-A*栅格路径规划算法

1.1 金字塔聚合地图构建

MQA-A*算法首先需要通过构造金字塔聚合地图，来缩减地图节点数目并同时降低栅格地图的空间复杂度。金字塔结构的多层级聚合地图需要从原始栅格地图开始逐层构造，构建第一层聚合地图的方法如图1所示，将原始栅格图1a每个2×2的网格划分为一个区域，将区域内4个相邻的1×1原始栅格聚合成第一层聚合地图的一个抽象节点，图1b给出了第一层级聚合地图的4个抽象节点，节点数相比原始栅格地图的图1a减少了3/4。

a

b

c

d

图1　第一层抽象地图节点的建立

Fig.1 The establishment of the first layer of abstract map nodes

第一层聚合地图上的抽象节点不能简单区分为障碍物或非障碍物，有鉴于此，为体现聚合地图的障碍物信息，本文借助抽象节点内部原始栅格上的障碍物分布情况，来构造第一层聚合地图上抽象节点间的连接属性。抽象节点间的连接属性可以分为边连通性及角连通性：首先，边连通性取决于紧贴该边两侧的原始栅格能否实现跨越边的连通，如图1c所示，在A、B两个第一层级抽象节点之中，由于b1和b4都是障碍物，不存在A、B间的通路，因此A、B两抽象节点不连接，而A、C之间则由于a4和c1连通，因此A、C两抽象节点是相互连接的；然后，角连通性取决于对顶角的两个原始栅格是否存在障碍物，如B、C之间b4及c2均为障碍物因而不连通，而A、D之间则由于a3及d1均非障碍物，因此A、D两抽象节点间相互连通，图1a的第一层级聚合地图如图1d所示（抽象节点通过矩形表示，节点间连接关系通过线表示）。抽象聚合地图是包含抽象节点及其邻居列表信息的数据结构，通过上述方法，可以得到抽象节点间的连接属性即节点邻居信息，从而可根据该信息抽象第一层级聚合网格。

第二层聚合地图的构造需要借助第一层聚合地图中抽象节点间的连接信息（仅连接信息即可，第一层聚合地图的数据结构不需要完整获取），来判断第二层抽象节点间的连接属性。抽象节点的聚合方式与第一层相同，即每4个邻接的第一层抽象节点聚合成一个第二层抽象节点。需要注意的是，从第二层聚合地图起始，该层上抽象节点的聚合方法需要考虑节点内部的连通性问题，节点内部连通性的概念是指聚合抽象节点内部的4个低层级节点是否相互连通，仅针对存在邻居的抽象节点（如底层全是障碍物的高层级抽象网格不属于内部不连通），显然该属性只用于第二层级或更高层级聚合地图的抽象节点中，考虑节点内部连通的必要性如图2所示，图2a中A1与[C ]1连通且[C ]1与B1连通，若不考虑节点内部连通性，在路径规划时可认为从A1到B1存在通路，但实际上[C ]1内部节点并不相互连通，在[C ]1内部的A1的邻居节点与B1的邻居节点间无连接，因此从A1到B1不存在第一层抽象节点间的通路；而图2b中节点[C ]2内部连通，A2只要与[C ]2中的任一低层级抽象节点连接，即可认为A2与[C ]2内的所有底层级节点间均存在通路，在图2b中A2、B2均与[C]2相连因此A2到B2存在通路。有鉴于此，判断节点内部连通性是保证能否规划出正确路径的前提，考虑到节点内部不连通的情况下，获取抽象节点的邻居需要根据多种不连通情况和邻居方位信息来判断，过程复杂并严重影响算法的总体效率，本文仅将聚合后内部可连通的抽象节点存储在第二层聚合地图上，而内部不可连通的第二层抽象节点将被重新打散成4个第一层级抽象节点进行存储，即第二层聚合地图上可能同时存在第一、第二两个层级的抽象网格。

图2　第二层抽象节点的内部连通性问题

Fig.2 The internal connectivity problem of the second layer of abstract map node

第二层聚合地图上，抽象节点间的连接关系可借助第一层抽象节点的连接关系来构造。记Lb为包含4个第一层抽象节点的一个第二层抽象节点，Lc表示Lb中的一个第一层级抽象节点，Ls表示第二层聚合地图中未被聚合而留下的一个第一层级抽象节点，分3种情况讨论：第1种是Lb与Lb相互连接，即某一个Lb中至少有一个Lc与相邻Lb中的一个Lc互为邻居；第2种是Lb与Ls互为邻居，即某一个Lb中至少有一个Lc与相邻Ls互为邻居；第3种是Ls与Ls互为邻居。第二层聚合网格的方式如图3所示。

图3　第二层抽象地图节点的建立

Fig.3 The establishment of the second layer of abstract map nodes

建立更高层级聚合地图的方法类似，其流程图如图4所示。

图4　建立多层级抽象网格地图的流程图

Fig.4 The flow chart of creating a multi-level abstract grid map

1.2 多层级A*路径规划

多层级A*路径规划方法，首先是在高层级聚合网格地图上运行A*算法，得到当前层级网格上的粗糙路径，并考虑该路径所经过的所有抽象节点，将这些节点对应到低一层级的地图中，根据抽象节点内部的连通属性、节点间的连接情况及障碍物信息，将粗糙路径逐层细化到底层栅格地图中。该算法首先要考虑起始点和目标点的层级转换，在第一层级中，起始点和目标点通过简单的坐标变换得到第一层级对应网格，将其带入到第一层级的A*路径规划过程中。在第二层级中，起始点和目标点对应的第二级节点可能是第二层级聚合节点，也可能是未聚合节点，具有不确定性，需要在得到第一层级对应节点后，判断该节点的第二级父节点是否为内部可连通节点，从而确定起始点和目标点属于哪个层级的节点并且计算出坐标。随着层级的升高，对起始点和目标点的坐标变换过程逐渐复杂。

在聚合地图上执行A*算法时，邻居节点的获取、启发函数的计算与传统A*不同。传统的A*算法对每一个待考虑节点都需要判断相邻节点是否可通，本文在金字塔结构的聚合地图生成后，每一抽象节点都存储了一个邻居列表，在多层级A*判断邻居节点时可直接调用。传统A*算法的启发式函数可采用当前节点到目标点的曼哈顿距离作为最小代价评估值，在第一层聚合地图上计算当前节点到目标点的曼哈顿距离与传统A*算法相同，直接用第一层的坐标进行计算。第二层聚合地图为了代价估计更精确，其两个节点间的距离为网格中心到另一个网格中心的欧几里得距离，由于抽象地图中存在两种层级的网格，所以该距离有可能为多种取值。

A*算法得到聚合地图上的粗糙路径后，需要在路径上抽象节点对应的低一层级抽象网格上逐层细化路径，直到细化到原始栅格地图中。细化路径时不需要启发函数的辅助判别，可根据高层级网格内部的连通情况，以及高层级网格间的连接信息得到细化的路径。以第一层级的细化路径为例，每一步的方位判断规则如图5所示，低一层级抽象地图上的起始点下一步的可选方向取决于它所在的高一层节点与粗糙路径上的下一节点的方位关系。下一节点为水平或竖直方向移动的情况，起始点的移动方向有3种，如图5a箭头所示，其中粗箭头表示优先选择的方向；下一节点为对角线方向移动的情况，起始点的移动方向有3种，如图5b箭头所示，其中粗箭头表示优先选择的方向，得到下一步路径点后，重复上述过程，即可得到最终路径。高层级抽象网格的细化原理与第一层级类似。该方法相比于原始的A*算法，步骤较少，判别规则简单，执行效率较高。

图5　细化路径方位判断示意图

Fig.5 Schematic diagram of the refinement path orientation

由此可得多层级A*路径规划算法的流程图如图6所示：

图6 多层级A*路径规划算法流程图

Fig.6 Multi-level A * path planning algorithm flow chart

2　仿真结果与分析

2.1 仿真准备

为验证本文算法的有效性，本文设计并实现了A*改进算法的仿真试验，实验选用3种不同障碍物数量、形态及分布情况的栅格地图，如图7所示，地图大小分为500×3 000像素和1 000×1 000像素2种，在这些地图上分别运行A*、MQA-A*第一层（实验结果中简称“MQA-A*1”）、MQA-A*第二层（实验结果中简称“MQA-A*2”）路径规划算法，进行对比实验。硬件环境为：Intel Core i5 1.7GHz处理器，4GB DDR3内存，Intel Visual Fortran 2010编译器。

a

b

c

图7　实验所用地图

Fig.7 Maps for simulation

2.2 仿真结果

对图7中3张地图进行A*算法和MQA-A*算法的仿真，收集抽象地图建立时间、路径规划总时间、扩展节点总数、总内存占用等数据，仿真结果见表1。

表1　仿真结果对比

Tab.1 Simulation results comparison

首先关注连接信息获取时间及抽象网格建立时间，这两部分时间的总和就是MQA-A*算法对网格的预处理CPU时间。图7a及图7b对应的两组仿真实验，其原始栅格地图的规模一致，因此其网格预处理CPU时间类似，一起进行分析：以图7a为例，MQA-A*2的连接信息获取时间相比MQA-A*1多了一倍，这是因为第二层聚合地图上的连接属性是基于第一层得到的；而抽象网格建立时间方面，由于该部分的效率主要取决于该层级聚合地图的抽象节点总数，在简单障碍物栅格地图中，第二层级聚合地图的抽象节点数目接近于第一层的1/4，因此MQA-A*2所需的CPU时间也要少于MQA-A*1；在总体网格预处理CPU时间方面，MQA-A*2相比MQA-A*1有小幅提升。图7c代表的地图具有复杂的障碍物分布，其连接信息获取时间及抽象网格建立时间的规律与图7a及图7b相同，但在总体网格预处理CPU时间方面MQA-A*2的预处理时间大于MQA-A*1，原因在于图7c第二层抽象网格地图中的内部不连通节点数较多，如图8a所示（图中黑色区域为可连通网格，蓝色区域为内部不连通网格，红色区域为底层全部是障碍物的高层网格），较多的内部不连通节点数导致第二层抽象网格数与第一层抽象网格数相差不多，而第二层抽象网格地图建立过程相对第一层更复杂，因此MQA-A*2的预处理CPU时间反而更长。

继续分析算法的路径规划时间。以图7c栅格地图上的MQA-A*2仿真实验为例，图8给出了第二层聚合地图上的粗糙路径及算法相关变量，其中图8b展示了粗糙路径，图8c展示了所有扩展节点的g 值，图8d展示了算法扩展节点的遍历顺序。在路径规划时间方面，3张不同的栅格地图上的实验均存在以下规律：MQA-A*算法在路径规划上相比传统的A*算法优势相当明显，MQA-A*1已经将路径规划效率在传统A*算法的基础上提升到了至少5倍，而MQA-A*2的路径规划效率还能进一步在MQA-A*1的基础上提升到至少3倍，最终的路径规划效率提升方面，图7a的栅格地图上MQA-A*2的路径规划时间仅为传统A*算法的1.14%，图7b及图7c的结果分别为2.56%及3.70%，如此大幅度的效率提升源于金字塔结构的高层级聚合地图大幅缩减了执行A*遍历的扩展节点数目，图7a及图7b的MQA-A*2扩展节点数目约为传统A*算法的1/16，而该数值在图7c中也同样小于1/10。扩展节点数目的缩减，首先成比例减少了路径规划中与扩展节点相关的链表处理次数，而在每次的链表处理中，扩展节点数目的减少使得链表的深度大幅下降，因而MQA-A*进一步提升了链表具体操作的效率，综合这两方面的因素，在路径规划方面MQA-A*可以大幅提升路径规划的效率，且网格的聚合层级越高，该部分的加速效果越好。

特别地，如果认为同一个栅格地图可以重复运用，基于不同的路径起始位置及结束位置构造多组实验，我们可以参考单独的路径规划时间作为算法效率提升的指标，如前文所述，在该指标下，算法效率提升的效果非常好。但如果每个栅格地图只运用一次，则考察算法的效率提升需要综合考虑网格预处理的CPU时间，将网格预处理时间加上路径规划时间，得到算法执行的总时间，并以该量定义加速比φ，记算法执行总时间为T ,加速比的表达式为：φ=TA*/T MQA-A*。对图7a、图7b及图7c，MQA-A*1分别提供了8.8倍、3.3倍及2.9倍的加速比，而更高层级聚合网格上的MQA-A*2分别提供了58.4倍、8倍及3.8倍的加速比。可以得到以下两个结论，首先是包括了网格预处理部分的时间之后，MQA-A*算法相比传统A*算法依然可以大幅度地提升计算效率，其次是MQA-A*算法的加速比对栅格地图的扩展节点数占比非常敏感，算法的加速效果随占比的减小而迅速降低，其原因在于扩展节点占比的减少导致路径规划的计算时间在算法执行总时间中的比重减少，于是虽然两个层级间A*路径规划部分的时间还是存在数倍的关系，但是该差异与网格预处理时间相比并非很大的，算法的提速效果降低。

最后关注算法的内存需求，MQA-A*所需内存相对于原始A*算法要少，且MQA-A*2的内存占用比MQA-A*1更低。内存占用包括连接信息内存占用和抽象网格内存占用两部分，其中连接信息内存占用是逐层累加的，即每个层级的连接信息都需要存储，所以第二层的连接信息内存占用大于第一层级；而抽象网格内存占用大致是每一层级为低一层级的1/4，如图7a和图7b情况，但图7c中第二层级内存占用大于第一层级的1/4是因为第二层级中的内部不连通网格相对较多，所以除了存储第二层级抽象网格，还需要存储大量的第一层级抽象网格，造成内存占用的增大。由于抽象网格内存占用在总内存占用中的占比大于连接信息内存占用，所以总内存占用趋势是逐层减少的。

a

b

c

d

图8　MQA-A*2中间过程变量云图

Fig.8 The contours of process variables of MQA-A*2

3　结束语

本文提出了基于邻接节点聚合的多层级MQA-A*栅格路径规划算法，具体工作主要分为以下两个部分：

1）首先是从节点聚合、抽象地图建立、粗糙路径规划及细化路径4个方面对算法进行了详细的解释。节点聚合方面，将传统的基于栅格障碍物来构造的网格邻居信息，抽象成节点间的连接属性并运用于高层级聚合地图，从而在蕴含邻居信息的同时大幅降低了用于路径规划的地图规模；抽象地图建立方面，考虑高层级网格抽象节点内部不连通的特点，建立多层级抽象节点共存的高层聚合地图，从而避免了抽象节点内部不连通给后续的路径规划部分带来的麻烦；粗糙路径规划及细化路径方面，算法在最高层级聚合地图上执行A*算法高效地得到粗糙路径，并根据抽象节点内的连通属性及节点间的连接信息将粗糙路径逐层细化，细化中仅保证单层细化中路径最短。

2）基于不同复杂程度的栅格地图，构造了3组仿真实验对MQA-A*算法的内存需求、算法CPU时间及算法加速比进行研究。实验结果表明，MQA-A*算法可以在路径规划方面较传统A*算法有巨大的提升，在3组实验中，基于MQA-A*2的路径规划时间分别是传统A*算法路径规划时间的1.14%、2.56%及3.70%，在考虑网格预处理CPU时间后，进而考察算法执行总时间加速比，MQA-A*2在3组实验中分别提供了58.4倍、8倍及3.8倍的加速比，分析得到了该加速比在后两组实验中没有第一组明显的原因在于其扩展节点占比较小。