李 强，于振中，樊启高，郭 龙

(1.江南大学 物联网工程学院，江苏 无锡 214000；2.哈工大机器人(合肥)国际创新研究院，合肥 230000)

0 引言

随着工业4.0与中国制造2025等战略的提出，大规模柔性制造工厂内物流运输与自动化生产需求促进了AGV的广泛使用[1]。其中，AGV主要负责物料库与工位之间和成品库与工位之间的物料转运。因此，AGV的运行效率对于整个生产系统的生产效率和柔性化提高至关重要。为了提高生产效率，不仅要考虑多AGV的协调控制问题，而且需要为每台AGV规划出最优的路径[2-3]。AGV路径规划指的是依据某些指标(如最短距离等)在给定的工作空间中规划出一条不与障碍物碰撞的从起点到目标点的最优或近似最优路径[4]。

A*算法是1968年由Hart等[5]提出，是一种经典的启发式搜索算法，搜索具有一定的方向性，实现简单，目前已经成功应用于移动机器人路径规划上。但A*算法在诸如工厂车间这种较为复杂的环境地图下搜索路径时也存在一些缺陷[6]，如搜索速度慢、路径不够平滑，扩展节点和搜索面积大等。因此很多学者在平滑性[7]、节点扩展及运行效率[8]、计算时间[9]等方面提出了A*的改进算法，但是这些改进后的A*算法仍然存在一些缺陷，如文献[7]未考虑改进A*算法的运行效率，文献[8]与文献[9]未考虑路径平滑性。因此，上述改进A*算法还不能完全满足工厂车间复杂环境下AGV路径规划的要求。

为解决复杂环境下AGV的路径规划问题，结合AGV的实际运动特性，本文从节点扩展方式、启发函数的选择和估价函数的构建对A*算法进行研究和改进，提出了一种基于象限概念的节点扩展算法，并在估价函数中引入AGV行驶和转向时间消耗成本，仿真结果表明改进算法能减少路径规划时间、降低转折次数和搜索节点数。

1 问题的描述

1.1 环境的表示方法

本文采用基于栅格法的地图模型，将工厂车间AGV工作环境视作矩形，地图中栅格大小一致且AGV承载货物在地面投影的尺寸应小于栅格的最小尺寸。图1所示为包含障碍物的栅格地图。

图1 栅格地图

考虑到工厂车间复杂环境下AGV实际工作的可靠性要求，本文采用4邻域节点扩展搜索方法，因此AGV可以向周围的4个方向的栅格移动，如图2所示。

图2 AGV运动方向

1.2 A*算法简介

A*算法是一种启发式搜索算法，是解决静态网络中最短路径的一种最有效的方法。A*算法的估价函数如下：

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

(1)

其中,f(n)是从初始点经由任意节点n到目标点的估价函数，g(n)是从起始节点到节点n的实际成本[10]，h(n)为启发函数，表示节点n到目标节点的最优路径估计成本。本文选取两节点间的欧几里得距离作为h(n)的估计代价，即：

(2)

其中，(xs,ys)是当前节点s的坐标，(xg,yg)是 目标点g的坐标。A*算法的寻路过程如图3所示。

图3 A*算法路径规划图

图3中，s表示起点，g表示目标点，黑色栅格表示障碍物，灰色栅格表示路径搜索过程中扩展过的节点及其子节点，黑色连线表示搜索到的路径。A*算法路径搜索的相关参数如表1所示。

表1 A*算法搜索结果

由表1可以看出，A*算法存在以下缺点：

(1)A*算法路径搜索时间较长；

(2)A*算法搜索路径转折次数多，不够平滑；

(3)A*算法搜索的节点较多，计算量大。

2 改进的A*算法

为了解决A*算法寻路过程中存在的搜索节点多，搜索时间长，转向次数多的问题，本文提出了一种改进的A*算法。

2.1 基于目标点所处象限的节点扩展算法

由图3可以看出，传统A*算法每次都要扩展当前节点的全部后继节点，然后再根据估价函数计算出具有最小f值的节点并将其加入closed列表中，在这个过程中需要查询的节点较多，特别是当环境地图较大时非常耗费时间，影响了路径搜索效率。

因此，本文提出了一种基于象限概念的节点扩展算法，通过计算目标点与当前点的坐标差值来确定目标点所处的象限。目标点所处的象限确定之后，就只需朝目标点所处的一个象限扩展节点。由于节点之间为4连接方式，所以算法只需扩展与当前节点相邻的目标象限的两个子节点，从而能减少对扩展节点评估的计算成本，提高搜索效率。算法根据式(3)实时计算得到目标点所处的象限。

(3)

式(3)中，Dx=xg-xs，Dy=yg-ys，(xg,yg)表示目标点g的坐标，(xs,ys)表示当前节点s的坐标。

具体的节点扩展算法流程如图4所示。

图4 基于象限概念的节点扩展算法流程图

其中，点(xE,yE)表示扩展节点E，点(xC,yC)表示当前节点C。

2.2 考虑AGV行驶和转向时间成本的估价函数

在物料搬运过程中，AGV频繁的转向动作会使得路径不够平滑，并消耗路径规划大量的时间，影响工作效率。为了得到更加符合AGV实际运行中的成本代价，并使得路径更加平滑，搜索时间最短。提出了一种基于时间模型的估价函数，估价函数由AGV的行驶和转向时间所耗成本共同构成。为了计算简便，我们做如下假设：

假设1：AGV匀速行驶且速度为v0。

假设2：AGV转弯半径为0，转向时间为常数Ct。

基于以上的假设，可以总结出AGV在一次启停和转向过程中的时间成本为：

Tc=T0+Ct

(4)

其中，T0为匀速时所耗时间成本，可由下式计算得出：

T0=d/v0

(5)

d为两节点之间的欧几里得距离。如图5所示为扩展节点示意图，C表示当前节点，F表示父节点，E表示实际无障碍时下一步可能的扩展节点，于是可以根据夹角θ值判断扩展节点是否发生转向。

图5 扩展节点示意图

则从当前节点C到扩展节点E的行走时间成本Tce可由下式计算：

(6)

其中，θ可由下式判断：

(7)

dEF为扩展节点E(xE,yE)到父节点F(xF,yF)之间的欧几里得距离的平方，可由下式计算：

(8)

为了更加精确估算扩展节点E到目标节点G的启发时间成本Teg，将AGV由扩展节点E到目标节点G可能出现的情况分为如图6所示4种类型进行讨论。

(a) 类型1 (b) 类型2

(c) 类型3 (d) 类型4 图6 扩展节点E到目标点G启发成本

图6a为扩展节点E与目标节点G共线且沿扩展节点方向扩展无障碍物。

AGV从扩展节点E到目标节点G为匀速运动，即启发时间成本可表示为：

Teg=T0

(9)

图6b为扩展节点E与目标节点G共线且沿扩展节点方向扩展有障碍物。

AGV从扩展节点E无障碍移动到目标节点G的过程至少要转向3次，则启发时间成本可表示为：

Teg=T0+3×Ct

(10)

图6c为扩展节点E与目标节点G不共线且沿扩展节点方向扩展无障碍物。

AGV从节点E移动到节点G至少包含一次转向过程，则启发时间成本可表示为：

Teg=T0+Ct

(11)

图6d为扩展节点E与目标节点G不共线且沿扩展节点方向扩展有障碍物。

AGV从节点E移动到节点G至少包含两次转向过程，则启发时间成本可表示为：

Teg=T0+2*Ct

(12)

式(9)～式(12)中，T0都按照式(5)计算，式(5)中的d都由式(2)计算得到。

则改进后的扩展节点E的估价函数为：

f(e)=g(e)+h(e)

(13)

其中，g(e)表示扩展节点E到起点的实际代价，可由下式表达：

g(e)=g(c)+Tce

(14)

g(c)表示当前节点到起点的已知成本，Tce为当前节点到扩展节点的成本，可由式(6)计算得出。

h(e)表示扩展节点到目标节点的最优路径的估计代价，可根据实际情况由式(9)～式(12)计算得到。

2.3 改进后的A*算法

改进后的A*算法中也有两个列表：open列表和closed列表。open列表包含所有已经生成待考察的节点。closed列表包含已经访问过的节点。采用基于目标点所处象限的节点扩展算法决定下一步加入closed列表中的节点，并在估价函数中引入行驶和转向时间消耗成本。本文改进A*算法流程如图7所示。

图7 改进A*算法流程图

3 仿真验证

为了验证本文提出的改进A*算法的有效性，在计算机(处理器：Inter(R) Core i5-7200U-2.5GHz; RAM: 8.00GB)Windows10 ×64位操作系统下进行测试，仿真平台采用Matlab R2014a实现，仿真地图采用20×20的二维栅格地图。在相同条件下，即环境障碍率p=37.5%，起点为(2,1)，终点是(19,20)，研究A*算法、本文改进A*算法以及文献[8]改进A*算法的路径规划性能，仿真结果如图8所示。

(a) 文献[8]算法规划路径 (b) 本文算法规划路径图8 文献[8]改进A*算法和本文改进A*算法仿真结果

图8a为文献[8]改进A*算法规划的路径，从仿真结果图可以看出，路径转向次数为10次，搜索节点数为58个，相较于普通A*算法路径规划性能有了一定的提升，特别是搜索的节点数量降幅较大，但是仍然存在路径不够平滑的缺陷；图8b为本文改进A*算法，可以看到转折次数仅为2次，搜索节点数为53个，说明了本文改进A*算法路径规划性较文献[8]有了进一步优化。表2从算法用时、转向次数、搜索节点数以及所求路径成本等指标给出了三种算法详细参数对比结果。

表2 普通A*算法、文献[8]改进A*算法与本文改进A*算法路径规划性能比较

从表2可以看出，与文献[8]改进A*算法相比，本文改进A*算法路径搜索性能有了进一步的提升，在运行时间上减少了36.64%、转向次数减少了80%、搜索节点数降低了8.62%，在AGV路径规划中的总的路径成本减少了46.51%。从而表明了本文改进A*算法可更高效地搜索到最优路径，减少搜索节点数，降低路径成本，使得路径更加平滑。

4 结论

本文主要研究了工厂车间环境下AGV的全局路径规划问题。针对车间复杂环境下A*算法路径规划时存在搜索时间长，搜索节点多，折弯次数多，路径不够平滑的缺点，从搜索方向、启发函数构建、转向成本等几个方面对A*算法进行研究改进，提出了一种基于目标点所在象限的节点扩展算法，并在估价函数中引入了AGV行驶与转向时间消耗成本。基于Matlab的仿真实验表明，改进A*算法相比传统A*算法，大幅降低了转折次数和搜索节点数，减少了计算时间和路径成本，提高了搜索效率和路径平滑度。