基于A*算法的路径规划研究综述

冉东可 彭富伦 李红光

（西安应用光学研究所 陕西省西安市 710065）

A*（A-Star）算法是一种静态路网中求解最短路径的直接搜索方法，因其灵活简便和对完整性及最优性的保证得以在机器人低维路径规划领域中广泛应用。但同时也存在以下缺陷：一是在大规模环境中应用时，节点网络非常庞大，算法运行时间长；二是扩展节点时占用内存开销较大；三是计算复杂度依赖环境网格分辨率大小。针对这些缺陷，已有很多学者提出了改进。本文首先介绍A*算法原理并进行影响因素分析，然后从启发函数、搜索策略、数据存储与查找等方面介绍A*算法的改进方法及研究现状，进而展望了算法未来发展和面临的挑战。

1 A*算法原理

A*算法是一种有序搜索算法，相比于Dijkstra 算法，加入了启发函数，使其朝着目标点有方向性的扩展节点，因此算法效率有了较大的提升。

A*算法的特点是，对于遍历的每一个节点，都采用一个评价函数f(n)来计算其通过该节点的代价，在每一次搜索时总是选择当前位置周围通行代价f(n)最小的点来扩展，如此从起始节点不断搜索直到找到目标节点，生成一条通行代价最小的路径。关于评价函数的计算方式如下式：

其中，h(n)代表从当前点到目标点的估计代价，同时也是启发函数，g(n)计算方式为从起点到节点n 的实际行走距离。

2 算法分析

由原理分析可知，影响A*算法搜索效率的主要因素是：

2.1 启发函数的设置

一般来说，从当前节点到目标点的启发函数一般小于实际路径代价，这样才可能得到最优解，但同时会增加扩展的节点数，增大算法时间开销。理想情况是启发函数h(n)恰好等于实际路径代价，这样扩展节点最少，且刚好能找到最优路径。

2.2 访问open表寻找f(n)最小值的时间开销大

传统的open 表可能采用Array、List、Queue 等结构来存储节点信息，随着搜索深度越深，要查找的节点就越多，每次扩展节点时都需要对open 表排序，查找f 最小值的节点，这会耗费部分时间，所以优化open 表的排序和查找是一个关键的改进方向。

2.3 搜索速度慢，时间开销随地图规模增大而增大

路径规划搜索算法的效率与地图搜索空间的规模成反比，A*算法的时间复杂度为O(n2) (n 为节点数)。当地图规模增大时，待扩展节点增多，算法运行时间也随之增加。同时，环境越复杂，障碍物较多时，也会导致搜索速度的降低。因此，减少不必要的搜索节点是改善搜索效率的有效方法。

3 算法改进

针对以上缺陷，目前已有学者对其进行了研究和改进，搜索效率已经有所提升。本节主要从启发函数的设置、搜索策略的选择、数据存储与查找及其他方面总结介绍现有的改进方法，概述A*算法的研究现状。

3.1 启发函数设置

启发函数的设置直接影响搜索效率。由A*算法具体搜索过程可知，导致其效率低的一个重要原因是，选择f 值最小的点作为下一个扩展节点时，总是会出现往返搜索的情况。针对这一问题，文献增大了启发函数的权重，使其更偏向目标节点处扩展，如式（2），改进后搜索效率较传统 A*算法有所提高。文献[5]在此基础上在启发函数中又加入了父节点信息，如式（3），有效减少了往返搜索次数。

式中，a 为权值，h(p)是当前节点n 的父节点p 到目标点的距离。

对于加权A*算法中的权值设置，文献分别研究了加权曼哈顿距离和切比雪夫距离中权值的选择对算法效率的影响。文献提出一种定向加权A*算法，对距离代价的X 轴和Y 轴进行双轴加权计算，结果表明转折点数明显减小。但有时仅用一个常数来表示并不能得到很好的结果。文献提出了新的设置方法，对当前节点及其父节点的估计路径代价采用指数衰减方式加权，使得A*算法在离目标点较远时能够很快地向目标点靠近，在距目标点较近时能够局部细致搜索保证目标点附近障碍物较多时目标可达。但缺点是当环境规模较大时，指数权重在路径搜索初期代价函数会严重退化，致使初期得到路径非最短路径，增加了路径长度。

3.2 搜索策略选择

选择合适的搜索策略有助于让搜索快速收敛到最优路径。文献[10]引入双向搜索机制，在环境规模较大时体现出其搜索速度快的优势。文献采用移动窗口法获取搜索网格候选集，每次扩展节点时只选取代价最小的5 个方向，缩小搜索范围。

文献提出了JPS 跳点搜索策略，根据一定规则从网格中选择性地扩展某些点，“跳跃”不影响搜索的最优性。结果表明JPS 跳点搜索在搜索效率方面比传统A*算法提升了一个数量级。在此基础上，文献提出双向跳点搜索算法，进一步减少了跳点的数量，加快搜索速度。

针对传统8 邻域搜索范围规划的路径不平滑问题，文献在此基础上又增加了外层8个节点，即对当前节点来说有16个待扩展节点，使得规划的路径更加平滑。

3.3 数据存储与查找改进

由A*算法原理知，搜索时需要不断访问open 表和closed 表，为了找某个节点，每次访问时，都需要遍历多个节点才能找到指定的节点，并执行添加节点和删除节点的操作，这会耗费部分时间。关于如何设计表的结构以及访问方式已有一些研究成果。文献提出了Lambda*算法，令open 表仅保存当前扩展节点的后续节点，丢掉了当前扩展节点的父节点和子节点，这在很大程度上减少了open 表保存的节点数量，减少了计算量和时耗，但会导致算法获得的路径规划方案质量降低。文献采用二叉堆方法对open 表中节点进行排序，优化f(n)最小值的查找速度，进一步提升地图路径搜索的速度。文献提出一种改进存储数组的方法，通过访问结构化数据，可以一次找到节点，并确定节点的状态，不需要遍历多个节点才能找到指定元素。这一方法有效保留算法的优点，提升运行效果。

3.4 其他方面改进

针对算法耗时长问题，文献提出了稀疏A*搜索算法（SAS），将不满足约束条件的不可行区域剔除，将可行区域分为若干子区域，利用代价函数寻找各子区域中的最优路径。该方法通过将约束条件与搜索算法结合起来，有效剪裁搜索空间，节省了搜索时间。

针对动态环境实时规划需求，文献提出了D*(Dynamic A*)算法，即从目标点开始反向搜索，并存储其到各个节点的最短路径及代价信息，在向目标点移动时，只检查最短路径上下一节点或临近节点的变化情况，这使得遇到未知障碍进行重规划时效率大大提升。该算法适用于动态场景，被应用于美国火星探测器的寻路规划。

4 面临的挑战与研究方向

A*算法发展至今，取得了大量研究成果。但依然存在以下问题亟待解决：地图精度与算法搜索效率的平衡、搜索范围与最优性保证的权衡。本文对现存问题进行总结，并对未来研究方向提出了以下几点建议。

4.1 扩展A*算法的应用环境

目前针对A*算法的研究主要集中在平坦路面上，障碍物单纯表示为能通过或不能通过需绕行。然而在实际应用中，例如野外环境，存在斜坡等可以跨越的障碍。A*算法在二维简单环境中表现良好，但在复杂环境及三维环境中的应用还有待优化。

4.2 合理剪枝缩小搜索范围

A*算法在搜索过程中会访问扩展大量节点，避免陷入局部最优，但是许多距最优路径较远的无关节点也会被扩展。现有的改进方法是以牺牲路径最优性为代价减少待扩展节点。如何剪枝缩小搜索范围，同时保证能够找到最优路径是未来一个关键挑战。

4.3 与其他算法融合

随着现代设备无人化智能化的应用需求，对于规划技术的要求也越来越高。单一算法有时不能很好地解决问题，因此将多个算法融合起来将是一个新的发展趋势。A*算法作为一种传统规划方法应用广泛，可与近年来出现的智能算法相结合，取长补短，更好的发挥优势。

5 总结与展望

A*算法自提出以来，因其直接简便、搜索能力强、保证路径最优性等优点被应用于无人驾驶、医疗给药、灾后救援、采矿探测等领域，能够完成从起点到目标点的路径规划任务。对于其运行时间长、占用内存大、转折点较多的缺点，已涌现出许多改进方法。虽然在一定程度上使得算法性能得以提升，但在实际应用中还不够成熟，存在改进空间，尤其是针对野外无路网环境的规划研究相对较少。因此为了更好的实现路径规划和无人驾驶，使其能应用于各种需求场景，对A*算法的进一步改进与优化，具有重要的现实意义。