郭大林，王淑营，曾文驱，杨 娟

(1.西南交通大学 唐山研究生院，河北 唐山 063000；2.西南交通大学 计算机与人工智能学院，四川 成都 611756；3.广州地铁设计研究院股份有限公司 自动化和通号所，广东 广州 510010)

0 引 言

随着我国机器人智能化水平不断提高，自动导引车(automated guided vehicle，AGV)的应用随处可见。比如柔性制造系统(flexible manufacturing system，FMS)[1]、大型智能化码头[2]、智慧物流仓库[3]以及智能地下停车场[4]等。AGV路径规划是AGV应用研究的重要基础问题之一[5]，指的是在一个存在障碍物的环境中，AGV小车按照时间最短或路径最短等性能指标从起点到终点找到一条安全无碰撞路径[6]。目前主要的路径规划算法有迪杰斯特拉(Dijkstra)算法[7]、A*算法[8]，除此之外还有蚁群算法[9]、遗传算法[10]等。A*算法是一种基于全局最优的启发式搜索算法，能够快速寻找最优解的同时，避免陷入局部最优问题。但是A*算法在实际应用中存在搜索的转弯次数频繁导致路径呈阶梯状，搜索节点数量大导致效率低下等问题，对此，国内外学者进行了大量改进研究。吕云峰[11]提出一种变步长优化传统A*算法，该算法在传统A*算法规划出路径结果之后，重新剔除路径上的冗余节点，从而减少转弯次数；李红[12]提出一种转弯因子在A*算法寻路过程中减少大量的转弯来平滑路径。但这两种算法均未提升搜索效率。吴鹏等[13]提出一种简单的双向搜索A*算法，从正向和反向两个方向交替搜索来提高寻路效率，但该算法牺牲了最优路径。孔继利等[14]在双向搜索算法的基础上对启发式函数重新加权，减少了搜索的节点量。而Lin等[15]利用当前搜索节点的父节点对启发式函数的影响来优化路径，从而缩短搜索时间，但是该算法同样以牺牲最优路径为代价。赵晓等[16]提出一种结合跳点搜索的改进A*算法，通过跳跃搜索标志性节点来减少搜索的节点数，但是环境中障碍物较多时，反而降低了算法的求解速度。

本文在不牺牲最短路径的情况下，为避免AGV频繁转向，并进一步提高路径寻优的效率，设计在传统A*算法的启发函数中引入转弯惩罚机制用以平滑路径，同时增加“选择因子”,用以控制相同代价节点的选择，来对传统A*算法进行优化。并通过实验结果验证改进算法的可行性。

1 环境建模

目前，AGV常常使用栅格法[17]、拓扑地图法[18]等地图进行路径规划研究，由于使用栅格法建立的环境地图能够更加直观表示地图信息，同时也利于算法程序的编写，所以本文将采用栅格法进行建模。常用的栅格地图如图1所示，栅格分为两种：

图1 普通栅格地图

黑色节点：障碍物。

白色节点：可通行节点。

在实际的列检环境中，节点类型比较复杂，如图2所示，主要分为4种：

图2 列检环境栅格地图

黑色节点：障碍物。

白色节点：可通行普通节点。

*节点：可通行升降平台节点。

#节点：可通行检测轨道节点。

其中升降平台节点成对出现，位于检修轨道节点的首尾处。根据列检环境的实际需求，AGV运行规则做出如下假设：

(1)AGV在某些方向(45°方向)行走中可能会与障碍物角发生碰撞，造成损失。故如图3中箭头方向所示，本文AGV行走只考虑上下左右4个方向；

(2)在栅格地图中，障碍物节点无法通行，普通节点与升降平台节点AGV可以4个方向通行，检测轨道节点左右通行会碰撞墙壁，故只能上下通行；

(3)在栅格地图中，AGV通行规则如图3所示。

图3 节点通行方向与规则

障碍物节点：AGV无法通行。

普通节点：AGV可以直接到达普通节点、升降平台节点，无法直接到达检修轨道节点。

升降平台节点：AGV可以直接到达普通节点、升降平台节点、检修轨道节点。

检测轨道节点：AGV只能到达升降平台节点和其它同一检修轨道节点。

(4)AGV匀速运行，不考虑起始点出发时加速和到达目的地减速的过程。

2 传统A*算法

A*算法是一种全局最优的启发式搜索算法，它是通过估价函数来确定搜索前进的方向，从而不断向目标节点不断靠近，避免在搜索过程中的盲目性。其表达式如式(1)所示

f(n)=g(n)+h(n)

(1)

式中：n为当前被搜索节点，f(n)为从起点通过n节点再到目标节点m的估计代价，它由g(n)和h(n)两部分组成。其中g(n)表示起点到当前节点n的实际所花费的代价，如果路径搜索中函数g(n)的值一直取0，则估价函数所表示的算法退化为广度优先搜索(BFS)算法，h(n)表示当前节点n到目标节点m的估计最短距离，h(n)常常选用欧式距离、曼哈顿距离或切比雪夫距离计算，其对应表达式分别如式(2)～式(4)所示

(2)

h(n)=|xn-xm|+|yn-ym|

(3)

h(n)=max(|xn-xm|,|yn-ym|)

(4)

如果路径搜索中函数h(n)的值一直取0，则估价函数所表示的算法退化为Dijkstra算法。要保证算法找到的解是最优解，则需要保证函数h(n)的值始终小于等于实际节点n到终点m的距离。

传统A*算法主要核心即是维护open列表和close列表，其主要处理流程如下：

(1)初始化open列表和close列表，并把起点加入open列表中。

(2)重复如下步骤：

1)遍历open列表，查找f(n)值最小的节点，把它移到close列表中，并把它作为当前要处理的节点，记为节点n。

2)遍历节点n的上下左右相邻节点，忽略不可达节点和已在close列表的节点。如果这些可达节点不在open列表中，则添加到open列表，并把节点n设为该节点的父节点，再计算它的g(n)值和f(n)值。如果该节点已经在open列表中，则比较当前路线的g(n)值和原线路g(n)值，如果当前线路更好，即当前路线的g(n)值更小，则更新该节点在open列表中的g(n)值和f(n)值信息，并把节点n设为该节点的父节点。

(3)终止条件：

1)open列表为空，说明此次寻路搜索失败，无法规划出一条到终点的路径，此时输出提示信息。

2)open列表中加入了终点，说明此时路径已经找到，输入路径信息。

传统A*算法的处理流程如图4所示。

图4 传统A*算法处理流程

3 改进A*算法设计

3.1 传统A*算法的不足与改进

在采用传统A*算法的AGV系统中，当某些节点的代价f(n)相同的时候，选择不同的节点进行遍历，最终总的搜索节点数不同，极端情况下它们可能都会被搜索一遍，尽管有时候我们只需要搜索其中的一条便能到达最终节点，本文使用曼哈顿距离度量两点间的预估代价，如图5地图所示，start节点表示起点。end节点表示终点。黑色节点表示障碍物。此时地图中存在A，B两个代价f(n)相同的节点。

图5 相同代价节点

如图6斜杠节点所示，当选择A节点作为当前处理节点，最终遍历节点总数为23个。

图6 分别采用A和B节点的遍历节点数

如图6灰色节点所示，当选择B节点作为当前处理节点，最终遍历节点数20个。

因此，相同f(n)代价节点的选择导致额外遍历节点，使计算量增加也是传统A*算法性能较低的一个原因。为了解决这个问题，本文在启发式函数中增加一个“选择因子”β，使其作用于h(n)函数上，从而让传统A*算法中那些具有相同的f(n)代价节点体现出区别。因为A*算法会根据f(n)值对节点排序，寻找最小代价节点时，让f(n)值不同意味着只有一个唯一的最小f(n)值的节点被选取。同时，“选择因子”β产生的附加值添加到h(n)函数上能够使得A*算法搜索过程中倾向于向目标结点扩展，减少A*算法遍历的节点总数。当然，“选择因子”β产生的附加值不宜过大，否则会导致h(n)值偏大，A*算法退化为BFS算法。具体设计如下

f(n)=g(n)+h′(n)

(5)

h′(n)=(1+β)*h(n)

(6)

如式(5)、式(6)所示，修改传统估价函数h(n)的计算方式，增加“选择因子”β，从而使open列表中的节点具有唯一的f(n)值，减少A*算法遍历的节点数。如图7所示，当增加的“选择因子”β根据h(n)函数为每个节点产生额外附加值时，由于B节点的h(n)函数值小于A节点，产生的附加值k2小于k1，从而B节点的f(n)值小于A节点。因此A*算法将选择遍历节点数小的B节点作为当前处理节点。

图7 带“选择因子”的相同代价节点

另一方面，在传统A*算法在路径规划时，代价函数只考虑起始节点到当前节点的实际路径和当前节点到目标节点的估计路径。这种简单的启发式函数带来的后果是导致AGV路径规划中路径不平滑，呈阶梯形，特别是在开始阶段和结束阶段比较明显。频繁的改变AGV移动方向势必会对AGV造成更多能耗，同时转向也会导致AGV减速，行驶效率大大降低。因此本文针对此问题引入转弯惩罚机制，对于那些需要转弯的节点增加相应的惩罚代价。具体设计如下

f(n)=g(n)+h(n)+αT

(7)

如式(7)所示，在传统估价函数f(n)中加入额外惩罚代价αT用于惩罚转弯节点，其中α取值范围为(0,1)，T为转向次数。因此本文最终使用的启发式函数如式(8)所示

f(n)=αT+g(n)+(1+β)*h(n)

(8)

3.2 改进A*算法的参数确定

在启发式函数的参数α、β确定过程中，本文选择50*50的普通栅格地图进行测试。每组参数测试5组用例，每组测试用例使用相同的起点和终点，记录不同参数下路径规划遍历的节点数、转弯次数和路径长度。首先确定参数α，通过实验发现：α的取值不影响搜索路径长度，无论α为何值，搜索路径长度均不变。如图8所示，不同测试用例的转弯次数在α≠0时，都能明显减少AGV转弯次数(由于图8中转弯次数最终收敛为2次或3次，所以导致线段重叠只能看到两条线段)。

图8 不同α取值转弯次数

每组测试用例在α取不同值时遍历的节点数如图9所示，由图可知，当α=0.3时，都能保证遍历节点数最少。

图9 不同α取值遍历节点数

确定参数β同样选择50*50的普通栅格地图、测试5组用例，记录不同参数下路径规划遍历的节点数和路径长度。通过实验发现，如图10所示，β的取值不影响搜索路径长度，无论β为何值，均能够获取到最短路径长度。如图11所示，β=0时，遍历节点数较多，β≠0时能够明显减少额外节点的遍历，大大减少路径搜索中节点遍历总数。

图10 不同β取值最优路径长度

图11 不同β取值遍历节点数

当β=0.001之后遍历节点数能够收敛于同一数值。而在β=0.1时，能够保证遍历的节点总数最少。

综上实验结果，本文最终确定参数α取值为0.3，参数β取值为0.1。启发式函数如式(9)所示

f(n)=0.3T+g(n)+(1+0.1)*h(n)

(9)

4 实验设计与分析

4.1 仿真实验分析

本文选择50×50尺寸的普通栅格地图进行实验。与传统A*算法、文献[12]提出的改进A*转向算法进行比较。来验证本文提出的改进A*算法路径寻优的性能。

在地图中：

白色节点：可通行节点。

黑色节点：障碍物节点。

灰色节点：寻找最优路径遍历过的节点。

最终路径规划结果如图12所示。

图12 50×50栅格地图不同A*算法结果对比

不同算法在50×50普通栅格地图中的对比见表1。

表1 不同算法在50×50地图中的对比

由上述实验结果可知，3种算法都能保证寻找最短路径，但是传统A*算法遍历节点量大，转弯次数较多。文献[12]提出的算法虽然够减少转弯次数，遍历节点数并没有提高，使得整体搜索效率并没有多大的提升，与传统A*算法时间花费相当。本文提出的A*算法能够明显减少转弯次数，并且大大减少节点的遍历数，搜索时间明显较小，搜索效率较高。

为了验证本文算法在不同尺寸的地图中的性能，分别在尺寸为25×25地图、50×50地图、75×75地图、100×100地图中分别进行实验。和Dijkstra算法、蚁群算法、传统A*算法、文献[12]的A*算法进行对比验证。实验结果见表2～表5。

表2 不同算法遍历节点对比/个

表3 不同算法转弯次数对比/次

表4 不同算法路径长度对比/个

表5 不同算法搜索时间对比/ms

由上述对比结果可知：本文算法相对于Dijkstra算法、蚁群算法、传统A*算法和文献[12]改进A*算法均能寻找到最短路径，而且本文算法在遍历节点和搜索时间上具有较高的效率，随着栅格地图尺寸的增加，效果更加明显。

在转弯次数上，Dijkstra算法、蚁群算法、传统A*算法均存在较多次数的转弯，而本文算法与文献[12]算法均能够明显减少转弯次数，但是本文算法遍历节点数大大减少，搜索效率更高。

4.2 列检环境实验分析

本文依据某公司实际列检环境构建20×100尺寸的栅格地图进行模拟实验。与传统A*算法、文献[12]提出的改进A*转向算法进行比较,来验证本文算法在列检环境地图中的性能。

在地图中：

白色节点：可通行节点。

黑色节点：障碍物节点。

*节点：升降平台节点。

斜格(#)节点：检修轨道节点。

灰色节点：寻找最优路径遍历过的节点。实验结果如图13所示。

图13 20×100列检栅格地图不同A*算法结果对比

不同算法性能在列检环境地图中的对比见表6。

表6 不同算法性能在列检环境地图中的对比

由上述实验结果可知，在列检环境下，不同算法都能保证寻优路径为最短路径。但是传统A*算法遍历节点量大，转弯次数较多，搜索效率低下，而文献[12]提出的改进A*算法虽然能够减少转弯次数，但是对搜索效率没有提升。本文算法能够保证最少转弯次数的情况下，大大减少无用节点的遍历，提高路径寻优效率。验证了本文算法在列检环境应用中的高效率性和可行性。

5 结束语

针对传统A*算法在AGV路径寻优过程中转弯次数较多和遍历节点量大的问题。本文对其进行了改进，首先，采用了转弯惩罚机制来减少AGV路径寻优时的转弯次数，然后，在启发式函数中加入“选择因子”用于控制那些具有相同代价值的节点的选取，从而减少额外节点的遍历，提高算法的效率。经过多组不同规格的地图进行的仿真实验，验证了本文改进A*算法相对于其它路径搜索算法提升了寻路效率并大大减少了转弯次数。同时在仿真实验的基础上，实现了基于实际复杂列检环境的AGV路径规划，搜索时间和规划的路径均能满足列检环境中的要求，具有一定的实际价值。在下一步的研究工作中，主要方向是能够结合相关碰避算法实现多AGV的路径规划，解决动态的、复杂的多任务的调度，不断提高算法的实际应用价值。