黄令苇，全燕鸣，王荣辉

（华南理工大学 机械与汽车工程学院，广州510641）

近些年来，自动导引车（AGV）在物料运输、电力巡检等方面得到广泛应用。为完成工作任务，AGV 需进行自主运动规划，实现从起点到终点的运动，主动避开障碍物。其中由于A*算法作为一种静态路网中求解最短路径最有效的方法被广泛应用。

不少学者对其进行了研究。文献[1]在评价函数中引入惩罚因子和奖励因子， 解决了传统A* 算法拐点多的问题；文献[2]使用多层变步长搜索策略和姿态角信息，文献[3]基于二叉堆优化，两者均加快了路径搜索效率， 但所得轨迹拐点数均有增加；文献[4]采用双向预处理结构减少冗余节点数，但增加了路径长度；文献[5]在评价函数中引入机器人转向所需时间，减少了路径拐点，缩短了路径规划所需时间，但目前仅能在静态环境下运行。

以上研究均未能解决一个关键问题——传统A*算法所得路径易与障碍物十分接近， 对AGV 运行带来安全隐患。而且，此时AGV 为保证避开障碍物，需要降低速度。故在此改进评价函数，引入障碍物距离，提高AGV 运行过程的安全性及工作效率。

1 环境建模

对于AGV 的运行环境， 可以用二维栅格单元进行划分。对于一个大小为n×m 的栅格地图，可以根据某一个栅格位置是否有障碍物将地图分为2种区域， 即可行驶区域和不可行驶区域。当n=10，m=10 时，栅格地图如图1 所示。图中，白色栅格为可行驶区域，灰色栅格为不可行驶区域。

图1 栅格地图Fig.1 Grid map

定义集合P=｛1，2，…，n*m｝表示所有的栅格编号，对于编号为i∈P 的栅格对应的坐标Pi=（xi，yi）有

式中：mod（）为取余函数；int（）为向下取整函数。

2 安全A*算法

2.1 传统A*算法

传统的A* 算法是在Dijkstra 算法的基础上引入启发式函数，用于引导路径的搜索方向。算法的评价函数为

该算法步骤描述如下：

步骤1初始化2 个列表openlist 和closelist。openlist 用于存放已生成而未访问的节点，closelist用于存放已访问过的节点。

步骤2将起始点加入openlist。

步骤3若openlist 为空，则结束算法。否则计算代价最小的节点，并将该节点添置最优路径。

步骤4对当前节点n，以4 邻域或8 邻域的方式计算邻节点，遍历openlist 和closelist。若均不包含邻节点，则将其加入openlist。

步骤5循环执行步骤3 和步骤4，直至算法结束。

2.2 安全A* 算法

所提出的安全A* 算法是在传统A* 算法代价函数的基础上，引入当前节点n 距最近障碍物的代价，从而使生成的路径远离障碍物，保证路径的安全性，提高工作效率。

在拔桩过程中，假定管桩被土体掩埋，且地下水位降至桩底以下，此时为最不利情况。如图1所示，桩体受力作用分别为：桩体上拔力F，桩体自重G，桩底下吸力P以及桩周摩擦力 f。

2.2.1 凸走廊生成

要找到距n 的最近障碍物，需要计算栅格地图M 中每一个栅格到n 的距离， 这样做的效率很低，因此参考文献[6]，在此引入了凸走廊的概念。节点n对应的凸走廊如图2 所示。图中，黑灰色节点为n；浅灰色节点为所生成的凸走廊；A，B，C，D 为该凸走廊的4 个顶点。

图2 节点n 对应的凸走廊Fig.2 Convex corridor corresponding to node n

本文生成凸走廊的方法为： 以n 为起始点，按顺序依次沿y 轴正向y+，y 轴负向y-，x 轴正向x+，x轴负向x-进行扩展，当到达地图边界或遇到障碍物时停止扩展。其算法流程如图3 所示。

图3 凸走廊生成流程Fig.3 Flow chart of convex corridor generation

图中，ylo，yup，xlo，xup的计算公式为

式中：xmax为地图在x 方向栅格的个数；ymax为地图在y 方向栅格的个数；step 为搜索步长。

2.2.2 搜索最近障碍物

生成凸走廊后，选取安全距离safe_dis，该值可根据实际需求更改，取值范围为［0，min（length，width）］，其中length 和width 分别为凸走廊的长和宽。然后，以n 为中心生成方形安全区域S，如图4 所示。

图中， 白色边框包围的区域为safe_dis=3 时的安全区域S。计算该区域中每一个障碍物到n 的距离，找到最小值min_dis。其算法流程如图5 所示。

2.2.3 评价函数改进

将传统A*算法的评价函数改为

式中：d（n）为n 到障碍物的代价；neutral_cost 为中等代价值，在此取常数50。

图4 生成的安全区域Fig.4 Generated security area

图5 最近障碍物搜索流程Fig.5 Flow chart of nearest obstacle search

3 仿真试验

为验证该算法的有效性，在此进行仿真试验。试验用计算机CPU 为Intel 酷睿i5-4200H 型，内存8 GB，在Gazebo 和机器人操作系统ROS （robot operating system）平台下进行仿真试验，仿真用AGV 为麦克纳姆轮系。仿真的三维环境及其膨胀地图如图6 所示， 考虑到计算栅格距离方法的不同会带来影响，统一设置使用曼哈顿距离计算。

图6 仿真的三维环境及其膨胀地图Fig.6 Simulation of 3D environment and its expansion map

设置safe_dis=min（length，width），分别使用传统A*算法和安全A*算法进行仿真试验，结果如图7 所示。图中，路径的起点为S，终点为E。可见在当前情况下，由于safe_dis 较大，图7（a）中路径所在通道宽度较小，所有点的代价值较大，故会优先选择图7（b）所示通道宽度较大处的路径。

图7 不同算法所得到的路径Fig.7 Paths obtained by different algorithms

选取相同起点与终点， 分别进行10 次路径规划后的统计结果见表1。

表1 算法改进前后10 次的结果统计Tab.1 Result statistics of 10 runs before and after algorithm improvement

由表可知， 虽然安全A* 算法所得平均路径长度比传统A* 算法长5.64%， 但其每个路径点到最近障碍物的平均距离增加了50.00%，AGV 沿路径运行平均速度提高了42.86%，平均所需时间减少了22.57%。

由于设置不同的safe_dis 对结果会产生影响，故令

式中：α 为取值权重。在此，对α 取不同值后，分别进行试验，结果统计见表2。

由表可知，随着safe_dis 取值增大，所规划路径的长度呈上升趋势，到最近障碍物的平均距离呈上升趋势，平均运行时间呈下降趋势，平均运行速度呈上升趋势。这说明在该范围内，safe_dis 的取值应该越大越好。

表2 α 不同取值时安全A*结果统计Tab.2 Safe-A* result statistics with different values of safe_dis

4 结语

利用提出的安全A* 算法，通过引入凸走廊，建立了安全区域， 得到了一条远离障碍物的安全路径。经过试验验证，相比于传统A*算法，安全A*算法提高了AGV 在运行过程中的安全性， 有效降低安全事故发生的概率， 且由于到障碍物的距离增大，可以给AGV 发送更大的速度指令，因此也缩短了AGV 执行任务的时间。