基于无人叉车行驶时间优化的改进A*算法

童亚男, 肖本贤

(合肥工业大学 电气与自动化工程学院,安徽 合肥 230009)

当下世界范围内蓬勃发展的电子商务带来的日益增长的仓储物流需求与手动操纵工业车辆的熟练技术人员的不足之间的矛盾日益凸显,人工手动操作显然不足以应付物流高峰期的生产和交付需求。为保持高质量的生产和供应水平[1-3],越来越多的仓库系统选择采用各种机器人和无人驾驶工业运输和搬运车辆来替代传统劳动力完成一系列不需要专业知识的工作[4-6]。因此,移动机器人和无人驾驶车辆的路径规划算法成为研究热点,如神经网络[7-8]、Dijkstra算法、蚁群算法[9]、人工势场法、RRT*算法[10-12]、A*算法[13-16]等智能路径规划算法。

神经网络算法学习时间长,规划效率低。Dijkstra算法搜索为盲搜索,可以得到全局最优路径,但运行效率低下。人工势场法计算量小,但存在局部极小陷阱。RRT*算法搜索速度快,但具有很强的随机性,导致收敛速度慢、生成路径不平滑。

A*算法是一种启发式搜索算法,近年来被广泛应用于路径规划领域。由于该算法具有最优性、完备性和高效性,其系列改进算法一直是路径规划领域的研究热点。启发函数能引导搜索向最优方向进行,在静态网络中搜索路径有效而直接,能搜索到最优路径;但也存在不足,得到的路径转折点多,存在大量冗余节点,不利于无人驾驶车辆进行实际跟踪[17-19];文献[20]提出一种可搜索无线邻域的改进A*算法为无人驾驶车辆寻找可行路径,对栅格进行线性插值,提高搜索效率,但在复杂地图上优势不明显;文献[21]提出以矩阵单元进行拓展,提高了算法效率,优化了路径质量,但在低复杂度且不开阔环境中,性能优化不明显;文献[22]通过拓展可搜索邻域来增加路径搜索方向,规划所得路径比传统A*算法的更短,转弯次数更少,但搜索时间大大增加,在复杂精细地图上实用性不高。

本文提出一种基于行驶时间优化的改进A*算法。以无人叉车为研究对象,从以下3个方面进行改进:

1) 对实际代价函数进行优化。引入转弯代价补偿参数用以表示转弯额外行驶时间,将转弯操作导致的额外操作时间纳入评估函数,使搜索过程趋向于航向不变的节点。

2) 对启发函数优化。引入父节点启发函数值,同时对启发函数权重进行自适应调整,确保搜索过程快速靠近目标节点且路径最优。

3) 对路径规划的初步结果进行路径剪枝,平滑路径降低路径转弯总角度,使路径适于无人叉车的实际跟踪。

针对以上改进,本文设计了不同环境地图进行仿真实验,证明所提出改进算法的有效性和实用性。

1 环境建模

无人叉车的出现提高了工作效率,降低了人力和设备成本。无人叉车的工作效率提升不仅意味着提升叉车行驶速度,还意味着缩短工作循环内的工作时间。叉车在弯道行驶时,需要进行额外减速、制动和重新加速,这不仅增加了工作循环内的工作时间,还会影响无人叉车的整体性能,带来侧翻风险,导致更高的车辆维护成本[4]。

栅格法是目前最常用的环境建模方法之一。将地图切割成大小相同相互连接的栅格,用黑色栅格代表障碍物所在区域,即不可通行,空白栅格表示该区域可供穿越行驶。在常见的8向栅格图中,叉车可在相邻可通行栅格间横向、纵向或斜向45°行驶;16向24邻域栅格图进一步增加了搜索方向,拓展邻域的增加使得拓展节点时搜索量成倍增加。文献[22]证明机械地增加搜索邻域来扩大A*算法的搜索方向在一定程度上改善了路径的平滑度,但算法搜索时间和存储空间显著增加。出于搜索效率考量,本文改进算法基于8向栅格地图进行环境建模。

在结构化地图中,叉车在通道中行驶,通道可分为单行道、双行道和多行道,在通道两侧有货架、堆叠货物等多种类型的障碍物。因为在非结构化环境,如小型非结构化仓库中障碍物分布不规则、通道宽度不确定的情况下,叉车行驶可能产生更多转弯,转弯角度更大,所以有更大的路径优化需求。因此,本文的改进A*算法在进行有效性验证时建立了多种栅格地图对叉车工作环境进行模拟。

2 传统A*算法

A*算法通过设计带约束性的启发式函数,在状态空间内对当前节点的每一个待扩展节点的成本进行评估,并且设计与问题特征相关的启发函数对性能进行调整,通过比较每个扩展节点的成本,选择最理想的节点去扩展,直到发现目标节点。在执行路径规划时,OPEN list用于保存搜索过程中遇到的扩展节点,将这些节点按评估函数成本f(n)值的大小排序;CLOSE list用于保存OPEN list中评估函数f(n)值最小的可扩展节点。

A*算法的评估函数f(n)计算公式为:

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

(1)

该函数计算由两部分组成,即从初始节点S到候选节点n的路径的实际距离成本g(n)和从候选节点n到目标节点G的最优路径的评估成本h(n)。

实际距离成本g(n)使用欧几里德距离累加表示,两点间欧几里德计算公式如下:

(2)

则相邻节点n的实际代价函数g(n)值和启发函数h(n)值可用下列公式进行计算:

(3)

(4)

其中:xG、yG为目标节点G的横坐标和纵坐标;xn、yn为候选节点n的横坐标和纵坐标。

传统A*算法路径规划过程如图1所示。

图1 传统A*算法流程

为提高搜索效率、缩短运算时间,本文将栅格图中每个栅格大小设置为1×10,当叉车在栅格间横向或竖向移动时,其运动距离记为1,斜向移动时,运动距离记为14,h(n)的计算公式如下:

h(n)=1.4min(Δx,Δy)+|Δx-Δy|

(5)

其中:Δx=|xn-xn+1|;Δy=|yn-yn+1|;xn+1、yn+1分别为节点n+1的横、纵坐标。

传统A*算法的评价函数综合了Dijkstra算法和最佳优先搜索(best-first-search,BFS)算法。将A*算法评价函数f(n)一般化,用下列公式表示:

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

(6)

当系数α=1、β=0时,算法退化为Dijkstra算法,倾向于广度优先搜索,即搜索偏向接近起点的节点,搜索范围大、时间长,但可求得两点之间的最短路径;当系数α=0、β=1时,算法搜索启发性更强,更倾向于搜索离目标节点更近的节点,此时A*算法可视为广度优先搜索(breadth first search,BFS)算法,但规划所得路径不一定是最优路径,因此评估函数f(n)中各项权重需要结合实际需要合理分配以得到更优、更平滑的路径。

3 改进A*算法

本节对传统A*算法进行改进,目标是取得静态环境下无人叉车行驶时间最短的路径。一方面向实际代价估计函数g(n)中引入转弯代价补偿参数构造转弯行驶时间函数,以此减少生成路径中的转弯次数;另一方面同时向原有的启发函数中引入父节点启发函数h(p),并对自身权重进行自适应调整;最后对规划所得初始路径进行剪枝,得到最优路径。

3.1 转弯代价补偿

叉车行驶过程中存在5种不同的直行与转弯情形,如图2所示。父节点p、当前节点m和拓展节点n的坐标位置可以用于判断前进方向是否发生改变:

图2 节点与行驶方向

λ1=(xm-xp)-(xn-xm)

(7)

λ2=(ym-yp)-(yn-ym)

(8)

其中:(xm,ym)为当前节点m的坐标;(xp,yp)为父节点p的坐标;(xn,yn)为拓展节点n的坐标;λ1为横向转向因子;λ2为纵向转向因子;当λ1=λ2时,叉车行驶方向不变,当λ1≠λ2时,航向改变,需转弯。

实际行驶过程中,同样距离行驶在转弯路段所需时间远超过直行路段,而传统A*算法评估函数中g(n)和h(n)仅表示实际已规划的路径长度和候选节点到目标节点的最短距离,未考虑转弯操作过程中由减速制动、重新加速等操作带来的额外时间成本,规划所得路径转弯次数多,转弯角度大,在无人叉车的实际工作中并不适用。

为解决上述问题,本文将行驶时间细分为直行行驶时间成本和由当前节点m拓展到候选节点n因转弯增加的行驶时间成本gt(n)。直行行驶时间由实际代价函数g(n)表示;转弯行驶时间gt(n)需要引入转弯代价补偿参数ω进行计算,由转弯代价补偿参数ω与拓展栅格的实际距离d加权表示,即

gt(n)=ω(λ1-λ2)dm,n

(9)

改进后实际代价函数g′(n)由两部分组成,即固有的直线行驶成本g(n)和额外的转弯时间成本gt(n),其计算公式为:

g′(n)=g(n)+gt(n)=

(10)

3.2 启发函数优化

A*算法的启发函数能使算法的搜索方向趋向于更有目的地接近端点。为约束算法搜索方向,减少往返搜索次数,使其快速靠近目标节点,本文在启发函数中引入了父节点的启发估计代价h(p),改进后的启发函数计算公式为:

h′(n)=h(n)+h(p)

(11)

考虑到本文启发函数h(p)使用欧几里德距离对两点间距离进行估计,此距离为两点之间最短距离,而无人叉车的实际工作环境中存在货架、货物、建筑等障碍物,使得两点间实际路径距离要远大于启发函数所估计的最短距离。在传统A*算法中,启发函数权重为1,在小范围内有多个评价函数值相等的候选节点,需要进行多次比较,搜索效率低。针对上述问题,本文通过比较拓展节点到目标节点及起始节点的距离远近,对启发函数的权重β进行自适应调整,以提高搜索效率,同时避免路径规划结果陷入局部最优,启发函数权重β的计算公式如下:

β=1+h(n)/D

(12)

其中,D为起始节点到目标节点的欧几里德距离,是一个常量。D的计算公式如下:

(13)

其中:(xG,yG)为起始节点坐标;(xS,yS)为目标节点坐标。当候选节点离目标节点较远时,h(n)较大,启发函数权重β取值较大,路径搜索方向快速接近目标节点;当候选节点逐渐靠近目标节点时,h(n)减小,启发函数权重β也随之减小,此时算法搜索范围扩大以确保目标点可达,避免陷入局部最优解。

经改进后评价函数f(n)的计算公式为:

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

(14)

3.3 路径剪枝

对改进后的A*算法所得路径采取全局路径剪枝,以剔除冗余拐点,进一步平滑路径,减小路径拐弯总角度。

得到初始路径后,从目标节点G开始,直接将点G与倒数第2个拐点N2相连接,若两点连线不与障碍物相交,则与倒数第3个拐点N3连接,依此类推,直到连线遇到障碍物。假设目标节点G与倒数第i个拐点Ni的连线与障碍物相交,即L(G,Ni)=+∞,则依次连接目标节点G与倒数第i个拐点Ni和倒数第i-1个拐点Ni-1之间(包括拐点Ni-1)的所有节点,直到节点X与目标节点G的连线是一条不与障碍物相交的直线,保留节点X与节点G,舍弃节点X到节点G间其余节点,以节点X为起点,继续向前回溯,直到回溯到起始节点S;最后依次连接所有剩余关键节点,得到剪枝后的优化路径。

路径剪枝过程演示如图3所示。

图3 路径剪枝过程

其中:红、绿色节点分别表示路径目标节点和起始节点;黑色实线为初始路径;红色虚线为剪枝过程路径。

首先将目标节点G与倒数第2个拐点N2相连,路径与障碍物不交叉;继续依次连接倒数第3个拐点N3、倒数第4个拐点N4连接,其路径与障碍物均不交叉;直到G与倒数第5个拐点N5相连,路径与障碍物交叉,即L(G,N5)=+∞;N4、N5存在中间节点B,连接G、B,其路径与障碍物相交L(G,B)=+∞,则该段路径剪枝结果为:

Path(G,N4)=G→N4

(15)

以N4为下一次剪枝的起点,将其与其后倒数第2个拐点即N6连接,路径与障碍物不交叉;继续向前回溯,到达起始节点S,连接S、N4,L(S,N4)=+∞;连接两拐点的中间节点D,有L(D,N4)=+∞,则该段路径剪枝结果为:

Path(N4,S)=N4→N6→S

(16)

剪枝完成后最优路径完整表示如下:

Path(G,S)=G→N4→N6→S

(17)

剪枝前、后路径对比如图4所示。其中,红色路线为路径剪枝得到的最优路径。

传统A*算法和本文改进A*算法的最优路径对比数据见表1所列。

表1 最优路径对比

由表1可知,相较于传统A*算法,本文改进A*算法所得到的最优路径长度减少20.80%,拐点总数减少83.33%,转弯总角度减少215.5°,优化效果显著。

文献[23]提出的改进A*算法只保留起始点和拐点进行剪枝操作,共线节点在路径优化的第1步就被忽略,剪枝过程粗放,导致所得最终路径并非最优,在复杂地图上优化效果欠佳。本文所提出的改进A*算法优先判断拐点间的连线是否与障碍物相交,无需逐个节点搜索,缩短了计算时间;同时保留了与障碍物相交和不相交的相邻连线间的共线节点用于精确搜索,得到最优路径。

4 实验分析

4.1 参数ω的选取对结果的影响

为研究不同的转弯代价补偿参数ω对A*算法所得路径长度和拐弯节点总数的影响,在30×30的栅格地图中,随机生成50组起始节点和目标节点,在转弯代价补偿参数ω取不同值时,使用本文改进A*算法进行路径规划实验。实验过程中,参数ω的变化范围控制在[0,1.2]之间,取值间隔设置为0.1,记录改进A*算法关键性能参数,性能表现变化趋势如图5所示。

图5 ω不同取值时算法性能

由图5可知:ω=0时为传统A*算法,与本文改进A*算法相比,其规划结果拐点数量最多,路径长度最长;在进行实际代价估计函数和启发函数的优化以及对路径剪枝后,本文改进A*算法规划所得路径整体的拐点个数和路径总长度大大减小;在转弯代价补偿参数ω=0.2时,转弯次数显著减少,且路径长度最短,本文改进的A*算法比传统A*算法转弯节点个数减少了29.23%,路径总长度减少了20.63%,效果最为理想。

因此本文改进A*算法转弯代价补偿参数ω的最佳取值为0.2,下文所有仿真对比实验皆基于此条件进行。

4.2 仿真结果

为了评估本文提出的基于无人叉车行驶时间优化的改进A*算法的性能,在2.3 GHz处理器、16 GiB运行内存的Windows 11平台上进行仿真实验。

本文分别模拟结构化和非结构化环境构造栅格地图,使用传统A*算法、蚁群(ant colony optimization,ACO)算法、Dijkstra算法和本文改进A*算法进行路径规划,分析并对比4种算法的性能。

4.2.1 结构化环境地图

本文建立了叉车结构化工作环境栅格地图,在该地图上设立相同的起始节点,使用4种算法进行路径规划,仿真实验结果如图6所示。其中:绿色栅格为起始节点;红色栅格为目标节点;黑色栅格为障碍物;白色栅格为可通行区域;红色轨迹为算法规划所得路径。

图6 工作实景栅格地图仿真结果

工厂地图上各算法的仿真性能指标结果对比见表2所列。由表2可知:在搜索时间上,本文改进A*算法比传统A*算法减少了28.10%,比Dijkstra算法减少了34.80%,实时性得到明显提升;本文改进A*算法所得路径长度为463.49,比传统A*算法缩短了4.20%。

表2 4种算法性能指标对比

决定路径平滑程度的关键数据为拐点个数及拐弯总角度。拐点个数越少,拐弯总角度越小,路径就越平滑,单个工作循环内需要进行的降速制动等操作频率就越低,行驶时间就越短。从表2还可以看出:本文改进A*算法比传统A*算法拐点个数减少了46.20%,比Dijkstra算法减少了41.70%,比ACO算法减少了36.40%;拐点个数的减少,使得路径拐弯总角度明显减少,这一指标本文改进A*算法比传统A*算法减少53.60%,比Dijkstra算法减少50.10%,比ACO算法减少45.30%。

综上分析可知,本文改进A*算法的效率更高,路径长度更短,且转弯角度更小,路径更平滑。

4.2.1 非结构化环境地图

为了验证本文改进A*算法的普适性及在复杂环境下的有效性,分别构建30×30和50×50的非结构性地图用于模拟更为复杂的工作环境。各算法仿真结果如图7、图8所示。

图7 30×30非结构化环境地图仿真结果

图8 50×50非结构化环境地图仿真结果

2种非结构化地图中各算法性能参数及本文改进A*算法、传统A*算法、ACO算法和Dijkstra算法的性能对比见表3、表4所列。

表3 30×30地图各算法性能参数

表4 50×50地图各算法性能参数

本文改进A*算法旨在降低无人叉车单个工作循环内的行驶时间。从图7、图8可以看出,3种改进算法相较于传统A*算法路径规划结果都更平滑,路径长度更短。但对比2种尺寸地图下3种改进算法的仿真结果可知:随着地图复杂程度增加,ACO算法、Dijkstra算法减少拐点数量、平滑路径转弯角度的效果变差,在50×50环境地图中仍有较多冗余拐点保留;而本文改进A*算法在50×50地图中路径剪枝效果仍然稳定,使得拐点个数和转弯角度大大减小,大幅减少因转弯而增加的操作时间。

由表4可知:本文改进A*算法在50×50的地图中比传统A*算法拐点数量减少47.10%,拐弯总角度减少65.90%,路径总长度减少2.24%,路径平滑程度有很大提升;比ACO算法、Dijkstra改进算法表现更稳定,实时性更强,优化效果更好。

5 结 论

针对传统A*算法路径规划结果实际应用于工业无人叉车上的不足,本文提出了一种改进的A*算法对无人叉车行驶时间进行优化。该算法通过引入转弯代价补偿参数设计转弯行驶时间函数和启发函数的优化,在保证路径最优的情况下减少路径规划中拐点个数和转弯总角度,引入自适应权重缩短无人叉车从起始位置到目标位置所需的时间,确保目标可达。仿真实验结果验证了该算法的有效性和可靠性。

本文提出的改进A*算法适用于已知环境的路径规划,规划所得路径拐点少,转弯角度小,更适用于无人叉车的实际作业,能大大减少无人叉车工作中转向、刹车次数,提高车身稳定性及工作效率。未来的工作需要考虑单个无人叉车载重不同、重心位置改变时所能跟踪的最大转角并进行路径规划,进一步考虑在多个无人叉车协同工作的动态环境中得到路径短、拐点少的平滑路径,以适应更加多变的工作场景。