基于改进A＊算法的无人配送车避障最优路径规划

陈荣军，谢永平，于永兴，赵慧民★，卢 旭，陆许明

（1.广东技术师范大学 计算机科学学院，广东 广州 510665；2.中山大学 花都科技研究院，广东 广州 510006）

0 引言

无人配送车是近年来智能移动机器人发展的产物，是由科学研究走向产品落地的阶段性成果，无人配送车路径规划问题，是指按照某一性能指标搜索一条从起始状态到目标状态的最优或次最优的无碰路径[1].其主要解决三个问题：(1)使无人配送车能从初始点运动到目标点；(2)用一定算法使无人配送车能绕开障碍物，并且经过某些必须经过的点；(3)在完成以上任务的前提下，尽量优化无人配送车运行轨迹[2].无人配送车根据对外部环境信息的感知程度，细分为感知全部环境信息的全局路径规划和感知部分环境信息的局部路径规划，基于A*算法进行无人配送车的路径规划主要研究的内容是全局路径规划[3].无人配送车的全局路径规划一般是在静态已知环境地图下进行研究的，而在静态已知环境中，影响无人配送车实现快速安全配送的性能指标主要包括规划生成的路径长度，路径平滑度，路径离障碍物的距离和规划路径过程中消耗的时间等.

无人配送车路径规划的研究属于智能移动机器人领域研究范畴，而针对智能移动机器人路径规划问题目前已进行了大量的研究，包括基于节点的Dijkstra算法[4]、A*算法[5-8]等，基于采样的RRT算法[9-10]等，基于生物启发式的遗传算法[11]、蚁群算法[12]等，基于模型的动态窗口法[13]、人工势场法[14]等.传统A*算法在静态环境下能够快速搜索到可行有效的路径，因此广泛用于智能移动机器人路径规划，但基于八邻域搜索的A*算法规划生成的路径包含了很多不必要的冗余点，且在拐点处的转折角度过大，致使规划生成的路径长度过长，路径曲率不连续，不利于无人配送车的平稳运行，同时基于八邻域搜索的A*算法路径规划耗时较长，满足不了无人配送车快速规划路径的需要.张超超等人[7]提出了一种针对路径长度和转折角度进行改进的算法，有效缩短了基于八邻域搜索A*算法规划的路径长度和转折角度，路径规划的时间也有较大幅度降低，但其算法规划生成的路径转折线段仍然存在，且路径规划的时间也较长，致使无人配送车无法稳定快速地规划生成出最优的路径；陈若男等人[15]通过引入最佳的邻域矩阵进行障碍搜索，并结合分区自适应距离信息改进启发函数，明显提升了路径的安全性，但是路径距离和规划时间都无明显改善；李冲等人[16]提出了一种基于方向约束的A*算法，通过方向约束和定向扩展机制进行路径规划，有效提高了路径规划的搜索效率，但在复杂环境下，规划生成的路径距离达不到最优，且路径搜索效率也不高.

综上所述，现有改进A*算法的相关研究工作，在一定的条件约束下，路径规划的单一性能指标有了明显提升，但还无法兼顾规划生成路径的安全性、实时性、平滑性等问题.为此，本文提出一种能够适用于无人配送车全局路径规划的改进A*算法.在基于八邻域搜索A*算法的基础上，设计出了一种适应无人配送车运行环境的多启发式搜索方法，使其能够很好地衡量每个路径扩展节点的计算成本，进而快速规划出更优的路径.同时，本文还提出一种路径优化策略，将初步生成的路径转折曲线优化为圆弧，进一步降低路径的转折角度.最后，改进A*算法的搜索路径机制，使规划生成的路径与障碍物保持在一定的距离，以此保证无人配送车在运行的过程中不碰到障碍物，安全到达目标位置.本文改进的A*算法不仅保证了规划生成的路径全局最优，实现了最大限度地平滑路径，同时有效地增强了无人配送车的避障能力，提高了路径规划的快速性和安全性.

1 构建环境模型

在无人配送车路径规划中，构建无人配送车工作环境模型是非常重要的环节.首先需要将所有传感器感知的环境信息融合在一起，建立一张表示无人配送车工作场景的环境地图.之后将地图以栅格为单位进行划分，可以非常方便地把无人配送车工作场景映射成包含二值信息的网格模型.栅格地图将无人配送车工作环境划分成一系列等尺寸的栅格，并且根据外部环境信息将栅格划分为障碍物区域和可自由通行区域.图1中的白色栅格部分表示无人配送车可自由通行区域，黑色栅格部分表示障碍物区域.

基于研究和验证算法的需要，对所建立的环境模型限定以下3点约束条件：(1) 栅格边界是在考虑无人配送车安全距离的基础上确定的，因此无人配送车在环境中可视为一个质点；(2) 栅格地图是一个简单有限的二维空间，不考虑障碍物和无人配送车高度的影响，并且无人配送车的移动方向是任意的；(3) 栅格地图是静态固定的，无人配送车全局路径规划是在一个静态的已知空间内运动.图1是由栅格地图构建的无人配送车工作环境，无人配送车路径规划的目的是实时找到一条从起始位置到目标位置的最优无碰路径.

图1 栅格地图

2 传统A★算法

A*算法是一种基于图的搜索算法，也是一种基于启发式搜索的高效寻路算法，其中基于栅格地图的启发式搜索方式有四邻域和八邻域搜索等.

四邻域搜索是指从当前栅格同时向周围的上下左右四个栅格方向进行搜索，八邻域搜索除了沿上下左右四个栅格方向搜索，还增加了左上、右上、左下、右下四个栅格搜索方向.基于栅格地图的四邻域和八邻域搜索如图2所示.传统A*算法通过估价函数的设计，深度融合了广度优先搜索算法和深度优先搜索算法所具有的特点，使其能够在静态已知环境中找到一条合适可行的路径.因此，A*算法广泛应用于静态已知环境下的全局路径规划.

图2 四邻域和八邻域搜索

此外，A*算法的优劣，极大程度取决于估价函数的设计.设计好估价函数之后，便确定了路径搜索时的启发规则和方向.它首先从起始点开始搜索周围的每一个节点，同时估价函数计算周围每个节点的估价值，选取最小估价值的节点作为下一个扩展的节点，更新起始点，之后不断循环搜索，搜索到目标位置之后，再从目标位置不断回溯到起始位置，最终生成路径.A*算法在整个的路径搜索过程中，始终都是以最低的估价值不断循环搜索，因此最终的估价值也是最小的.用于计算A*算法估价值的数学表达式定义如式(1)所示：

表达式1中：F(n)是从起始位置到目标位置的估价值，G(n)是从起始位置到节点n的实际代价值，H(n)是从节点n到目标位置的启发函数估价值.因此，A*算法要找到最优路径，关键在于H(n)的选取，设节点n到目标位置的实际代价为R(n)，H(n)＞R(n)时，搜索的节点少，搜索范围小，效率高，但不能保证搜索到最优的路径；H(n)=R(n)时，估计代价等于实际代价，A*算法将沿着最短路径进行搜索，找到最优的路径；H(n)＜R(n)时，搜索的节点多，搜索范围大，效率低，但能找到最优路径.定义启发函数的距离有Chebyshev距离、Euclidean距离、Manhattan距离及文献[6]根据Euclidean距离和Manhattan距离设计的定义启发函数的距离，即

其中nx是节点n的横坐标，ny是节点n的纵坐标，gx是目标点的横坐标，gy是目标点的纵坐标..由于无人配送车路径规划是以实际距离进行评估的，以规划生成最短的路径为目标，因此Chebyshev距离不适用.此外，计算两点间的最短距离，Euclidean距离和Manhattan距离都是常用的距离定义启发函数，其中基于八邻域栅格的搜索，Euclidean距离定义的启发函数明显优于Manhattan距离定义的启发函数.再者文献[6]距离定义的启发函数在八邻域栅格搜索方式中，大大增加了路径搜索时间，也不是最优选择.通过对以上四种距离进行分析后发现，都不能很好地适应无人配送车工作环境.因此，本文将结合Euclidean和Manhattan距离，设计出一种搜索效率更高，生成路径更优的启发函数.

3 改进A★算法

针对无人配送车路径规划过程中耗时较长，路径不够平滑，避障性能不足等问题，本文在传统A*算法的基础上，对基于八邻域搜索方向的A*算法进行了三方面的改进及优化，通过重新设计距离定义启发函数使得改进A*算法能够在搜寻路径的过程中，兼顾了可通行区域和障碍物区域，并且优化了路径的生成策略，最大限度地平滑了算法生成的路径.同时，改进了A*算法的搜索路径机制，使规划生成的路径与障碍物保持在一定的距离，实现了适合无人配送车行驶的最优安全路径的快速规划.本文算法流程图如图3所示.

3.1 距离定义智能启发函数的设计

改进的A*算法采用基于栅格地图的八邻域搜索方式，设计出一种基于多启发式搜索的智能启发函数，使其能够根据无人配送车的工作场景.结合Euclidean距离和Manhattan距离，在不同的搜索方向中使用不同的但保持一定比例的距离加权值，通过两种方式的改进，设计出的智能启发函数能很好的兼顾无人配送车可通行区域和障碍物区域，找到最适合无人配送车通行的路径.改进的距离定义智能启发函数的具体形式如式(6)和式(7)所示.式(8)和式(9)是将改进的距离定义智能启发函数融入A*算法估价函数的具体形式.

图3 改进A＊算法的路径规划流程图

其中，式(6)表示改进了搜索方向上所采用的距离方式，在当前栅格的上、下、左、右四个方向上，通过采用Manhattan距离进行定义；在当前栅格的左上、右上、左下、右下四个方向上，通过采用欧几里得距离进行定义；式(7)改进之处是在Euclidean距离和Manhattan距离定义的基础上，使Euclidean距离定义的启发函数和Manhattan距离定义的启发函数保持一定比例，其中K表示距离加权值，n为正整数.公式(8)和(9)是将公式(6)和(7)修改的启发函数代入A*算法总的估价函数中，是改进A*算法估价函数的具体实现形式，即公式(8)是在当前栅格的上、下、左、右四个方向上进行使用，公式(9)是在当前栅格的左上、右上、左下、右下四个方向上进行使用.因此改进后的距离定义启发函数更为智能，提高了搜索的效率，缩短了无人配送车的路径规划时间.

3.2 路径转折线段优化策略

A*算法在栅格地图中进行路径规划，起初是以起始点作为当前扩展点，估价函数不断评估当前扩展点的周围节点并选取具有最低估价值的节点作为下一个扩展节点，不断向周围节点进行扩展，直到目标节点找到，从目标节点进行回溯生成路径，完成搜索的过程.但此时生成的路径曲线转折点过多，转折角度过大，致使无人配送车不能安全平稳实时的运行.针对这个问题，本文提出了一种优化策略，可以优化路径的转折曲线为圆弧，最大限度地平滑所规划生成的路径.路径转折线段优化前后效果图如图4所示.

图4 路径转折线段优化前后效果图

本文提出的路径转折线段优化策略是依据数学上的边弧优化原理，对之前融入智能启发函数后规划生成的初始路径进行边弧优化.关键步骤是计算出路径转折处节点间的转折角度α，并通过公式(10)求出其余弦值，计算公式如下：

其中(x1,y1),(x2,y2),(x3,y3)为初始路径三个相邻节点的坐标.由于无人配送车在栅格地图中转动的角度只存在0°、45°和90°这三种情况，因此只需根据节点间的夹角和方向，便可以采用边弧优化理论计算出所有转弯情况的半径，圆心和转弯的弧度.具体实现过程如下：

(1)当α＞0°时，无人配送车向左转动，并根据α值的大小，控制转动的角度；

(2)当α=0°时，无人配送车行驶方向保持不变；

(3)当α＜0°时，无人配送车向右转动，并根据值的大小，控制转动的角度.

根据路径转折处节点间的转折角度α的值，无人配送车在转折点处的运动状态有以上三种情况，对此采取的路径转折线段优化策略流程图如图5所示.

图5 路径转折线段优化策略流程图

3.3 安全避障的路径生成策略

针对无人配送车配送过程中的安全问题，平滑规划生成的路径依然无法保证不与障碍物发生碰撞，对此，进一步优化算法的路径生成策略，使改进后的算法规划生成的路径与障碍物保持最少半个栅格的距离，以此保证无人配送车在运行的过程中不碰到障碍物，安全地到达目标位置.安全避障的路径生成策略如图6所示.

本文提出的安全避障路径生成策略主要是对子节点的估价值进行调整.实现方法如下:(1) 若当前的节点与相邻节点的方向和当前节点与其父节点方向相同,则减小公式(1)中G(n)的估价值；若方向相反，则增加G(n)的估价值.(2)初始路径转折点间的转弯程度与G(n)的估价值呈正比例相关.转弯程度越大，G(n)的估价值也越大.(3)扩展子节点的过程中，优先扩展垂直水平方向上的节点，随后根据垂直水平方向上是否存在障碍物，如果存在，则不扩展与障碍物相邻的对角线节点；如果不存在，则扩展对角线方向节点.安全避障路径生成策略的流程图如图7所示.

图6 安全避障的路径生成策略

图7 安全避障路径生成策略的流程图

4 仿真实验及结果分析

为了验证本文改进的A*算法在无人配送车全局路径规划中具备优良的特性，本文根据无人配送车运行环境，建立与之完全对应的栅格地图，聚焦规划生成路径的长度，转折角度，生成路径与障碍物的距离，路径规划时间等一系列影响无人配送车运行的性能指标，进行实验和仿真，并与定向加权A*算法[7]进行对比.用于仿真实验的计算机配置为：Ubuntu 16.04.6 LTS Linux 操作系统，处理器：Intel®CoreTM i5-3230M CPU @ 2.60GHZ，运行内存为4Gb，仿真平台采用Matlab R2017b版本.

4.1 改进A＊算法仿真实验

由于定向加权A*算法在仿真环境下，采用较小单位制来约束路径距离，以提高路径规划的精确性.因此，为搭建与其相同的实验环境，对之前所构建的栅格进行细分化处理，每个栅格由之前表示100 个单位细分表示为1个单位，每个单位以厘米计算，在20*20的栅格地图中进行算法对比仿真实验.

图8 融入智能启发函数规划生成的路径

图8是融入智能启发函数之后规划生成的路径，其规划生成的路径长度能够达到最优，并且路径规划的时间明显减少，与定向加权A*算法相比，时间从1.379秒减少为0.988秒.因此，融入了智能启发函数之后的A*算法优化生成路径的同时，减少了规划生成路径的时间.

图9 启用路径转折线段优化策略规划生成的路径

图9是启用路径转折线段优化策略之后规划生成的路径，从图中可以看出，启用路径转折线段优化策略之后规划生成的路径能够将路径转折线段部分优化为圆弧，路径折点数和路径转折角度进一步减少，使得整体规划生成的路径更加平滑，这对于无人配送车的平稳运行具有重要的参考价值.

图10 启用安全避障路径生成策略规划生成的路径

图10是启用安全避障路径生成策略之后规划生成的路径，从图中可以看出，启用安全避障路径生成策略之后规划生成的路径与障碍物始终保持半个栅格单位的距离，虽然路径长度从优化之前的23.4cm增加到25.8cm，但是大大提高了无人配送车的避障性能，能够很好的满足无人配送车安全无碰的到达目标位置.

4.2 实验结果分析

为了进一步清晰直观的说明本文改进的A*算法能够规划生成出更优的路径，将影响路径规划性能的主要参数列表显示，根据路径规划算法仿真实验得出的数据，对传统A*算法、定向加权A*算法[7]和本文改进算法的优劣进行量化对比分析.

表1 算法改进前后性能参数比较1

在安全距离这列数据中，定向加权A*算法规划生成的路径穿过栅格图中的障碍物顶点时，其路径的安全距离为0，未穿过障碍物顶点时，其路径的安全距离为0.707，表2此处表示相同含义.

通过表1可以看出，本文算法规划生成的路径，多项性能参数都要优于传统A*算法和定向加权A*算法.其中，本文改进的A*算法规划生成的路径距离为25.8cm，路径规划的时间为0.988s，路径折点数显著减少.此外，本文针对无人配送车路径规划问题进行研究，对初步生成的路径转折曲线优化为圆弧，最大限度的平滑路径，使生成的路径转折点数降至为零，在启用安全避障路径生成策略之后，规划生成的路径距离达不到最短，比定向加权A*算法规划生成的路径距离要长2.4cm，但是本文算法能够很好地避开障碍物，这对于无人配送车平稳安全的运行具有更加重要的意义.

针对配送车在更大工作场景下，本文改进A*算法、定向加权A*算法及传统的A*算法在生成路径距离，算法运行时间，路径折点数，安全距离等性能的表现，接下来进行更大环境下算法的仿真对比实验.

图11 传统A＊算法规划生成的路径

图12 定向加权A＊算法规划生成的路径

图13 本文改进A＊算法规划生成的路径

通过对图11，图12和图13进行对比分析可知，本文改进A*算法能根据无人配送车的运行环境，生成更优无碰可行的路径，不仅进一步减小了规划的路径长度和转折角度，而且还缩短了路径规划的时间，具体的路径规划性能指标如表2所示.

通过表2可以看出，本文改进A*算法规划生成的路径，各项性能参数都比定向加权A*算法和传统A*算法更优，相较于定向加权A*算法，本文算法在路径距离上减少了4.6cm，运行时间上减少了7.381s.相较于传统A*算法，本文算法在路径距离上减少了11.4cm，运行时间上减少了8.915s.通过表1、2和图10、13，可以非常清晰的看出本文改进的A*算法规划生成的距离和路径规划的时间均有明显减少.

表2 算法改进前后性能参数比较2

5 结语

为进一步减小路径转折角度，提高避障性能，满足无人配送车快速规划路径的要求，本文设计了一种智能启发函数，并提出了路径转折线段优化策略和安全避障的路径生成策略，使得改进A*算法更稳定有效地减少了路径规划的时间，同时进一步优化生成路径的转折角度，最后使得规划生成的路径安全可靠地避开障碍物.不过本文主要研究的是无人配送车在静态已知环境中的全局路径规划及安全避障研究，虽然改进后的算法进一步减少了规划路径的长度和转折角度，缩短了路径规划的时间，安全有效地避开障碍物，但是在动态未知环境下的无人配送车路径规划，还存在一定的局限性.下一步的研究工作是在无人配送车全局路径规划的基础上，设计并改进局部路径规划算法，使无人配送车在动态未知环境下也能规划出最优无碰路径，满足无人配送车智能配送的需要.