AGV路径规划及避障算法研究综述

赵学健,叶 昊,贾 伟,孙知信

1(南京邮电大学 现代邮政学院,南京 210003)

2(南京邮电大学 江苏省邮政大数据技术与应用工程研究中心,南京 210003)

3(南京先维信息技术有限公司,南京 210001)

0 引 言

在工业4.0、“中国制造2025”、智慧物流和智慧工厂等概念的推动下,工业移动机器人市场呈现高速增长的态势.自动导向车(Automated Guided Vehicle,AGV)是指装备有电磁或光学等自动导引装置,能够沿规定的导引路径行驶,具有安全保护以及各种移载功能的运输车[1].AGV能够代替人工转移、装卸和搬运货品,有效地降低了人工劳动强度,提高了工作效率,提升在部分危险且复杂的环境中工作的安全性,目前广泛应用于物流、机械、电子、化工等行业.AGV的路径规划和避障算法是实现AGV自主导航的关键技术,决定了AGV在复杂环境中能否高效、安全地完成任务,近年来成为AGV领域的重要研究热点之一.

AGV路径规划是指为AGV在特定应用场景下,按照特定的性能指标搜索一条从起始状态到目标状态的最优或近似最优的运行路径.路径规划的目标可以是最大化AGV的效率,减少行驶时间,降低能耗,优化资源利用率等.路径规划算法需要考虑各种约束条件,如静态障碍物、动态障碍物、区域限制等,因此避障算法是路径规划算法的核心组成部分,用于判断、预测和避免AGV与障碍物之间的碰撞,从而确保AGV运行过程中的安全性和可靠性.

根据AGV路径规划及避障算法的原理与技术特点[2],AGV路径规划及避障算法大致划分为局部避障路径规划算法、基于几何模型的路径规划算法、智能路径规划算法及混合路径规划算法等,如图1所示.

根据图1分类方法,本文首先对各类AGV路径规划及避障算法的技术原理、工作流程、优势、局限性进行了深入分析阐述;在此基础上,进一步对比分析了不同方法的优劣;最后,本文对AGV路径规划及避障算法的未来发展趋势进行了总结展望,以期进一步推动AGV路径规划及避障算法的研究进展.

1 局部避障路径规划算法

局部避障路径规划算法是一种用于避免 AGV与局部环境中的障碍物发生碰撞或冲突的算法.它的目标是确定 AGV 在当前环境中的最佳移动路径,以避开静态或动态的障碍物,并以安全和高效的方式达到目标位置.此类算法通常先确立起点到终点间的直线为初始最优路径,再基于AGV周围的环境感知信息,采用一系列步骤尽可能以较小的调整实现对初始最优路径上一切障碍物的有效规避,形成最终最优路径.该类算法主要包含人工势场法、动态窗口法以及Bug算法等.

1.1 人工势场法

1)算法原理简介:人工势场法(Artificial Potential Field approach,APF)最早于1985年由Khatib提出[3],基于对AGV周围环境中潜在障碍物施加人工生成的势场,使AGV从高势场区域移动到低势场区域,其工作原理如图2所示.

图2 人工势场法原理示意图Fig.2 Schematic diagram of the principle of artificial potential field methods

该算法从车辆到目标点为方向设置目标点引力势场,以各障碍物到车辆为方向设置障碍物斥力势场,二者叠加形成合势场,车辆在该合势场的作用下运动,从而使车辆以尽可能短的路径,避开障碍物,到达目标点.具体的合势场函数U如式(1)所示:

U=

(1)

式中,n为引力势场正比例系数;k为斥力势场正比例系数;d0为障碍物影响范围;x为车辆的位置坐标;xgoal为目标点的位置坐标;xobs为障碍物的位置坐标;d(x,xgoal)为车辆当前位置与目标点之间的距离一个矢量,方向从车辆指向目标点;d(x,xobs)为车辆与障碍物之间的距离.

对合势场函数进行求导即可得到作用于车辆的人工合力F,其表达式如公式(2)所示:

(2)

2)算法优缺点:人工势场法算法具有定义直观、结构简单且计算量较小等优点,深受广大研究者偏爱.但也具有局限性,人工势场法易出现路径振荡、路径过长以及局部最优等问题.

3)算法改进措施:近几年,研究人员针对传统人工势场法存在的缺陷提出了各种改进措施,主要包括增设速度势场、优化斥力势场与斥力调节因子、增设虚拟目标点等措施.Joe Sfeir等人[3]优化了排斥力势场,将离心力等旋转力以及小车惯性整合入势场之中,减少了路径振荡问题,得到更加平滑的行车轨迹.陈冠星等[4]通过增添虚拟目标点辅助机器人规避局域最优问题.张涌等[5]通过改进斥力调节因子和斥力作用域的方式优化传统人工势场,赋予了AGV同向超车能力.张钟元等[6]根据无人设备控制律设计保持速度、位置一致的控制协议,采用归一化和高阶指数对人工势场力进行缩放变换,解决势场力变化幅度过大导致的路径损失以及震荡失效问题.桂雪琪等人[7]提出将极限环与人工势场法相结合构造避障速度引导项,解决了局部极小值带来的集群遇障分群困难、避障徘徊停滞等问题.

1.2 动态窗口法

1)算法原理简介:动态窗口法(Dynamic Window Approach,DWA)最早于1997年由Dieter Fox等人提出[8],该算法将车辆所在的位置看作是窗口的中心,而窗口的宽度和长度则是车辆的大小和下一跳可到达的最大范围.该算法从车辆的当前位置开始,基于车辆当前位置(x(t),y(t),θ(t))及车辆的线速度v(t)和角速度w(t),预判t+1时刻车辆位置(x(t+1),y(t+1),θ(t+1))的可能范围,形成窗口,并计算窗口内是否存在障碍物.如果存在障碍物,则需要调整车辆运动方向,并重新计算窗口的位置和大小,实现避障.车辆状态更新过程如式(3)所示:

x(t+1)=x(t)+v(t)dtcos(θ(t))
y(t+1)=y(t)+v(t)dtsin(θ(t))
θ(t+1)=θ(t)+w(t)dt

(3)

2)算法优缺点分析:在局部避障中,动态窗口法的优点在于它的实时性和精度,该算法只需要计算当前窗口内的元素,而不需要重新计算整个地图,因此可以实时检测障碍物,并进行快速的路径规划和调整.但该算法高度依赖全局参数,容易在未知环境中失败[9].

3)算法改进措施:Seder等[9]针对未知且动态的障碍物环境,将动态障碍物的移动视为所占据网格单元的移动,与AGV的运动单元轨迹进行碰撞预测,扩展了AGV在缺少全局参数更新时的无碰撞运动能力.Wang等人[10]重新设计了无人设备运动学模型和基于动态窗口法的局部路径规划方法评价函数,提高了环境负荷强度的权重,从而提高窗口灵敏度,缩减了路径长度和航行时间.

1.3 Bug算法

(4)

其中,d(x,qgoal)为机器人当前位置到终点距离;F为爬虫指向终点方向与第一个可见障碍物的距离;dmin(qgoal)为走过的路径点与终点最近的距离;P为障碍物最小壁厚.

2)算法优缺点分析:Bug算法结构相对简单,可以逐步探测避开障碍物,不需要全局环境信息,但从始至终只以最新获得的环境数据为操作依据,高度依赖传感器提供数据,易因信息不足而规划失败,且无法处理动态障碍物.

3)算法改进措施:当前研究者对Bug算法的改进研究主要针对其数据获取及处理能力的缺陷.查荣瑞等人[14]提出的一种基于深层卷积神经网络和改进Bug算法的机器人避障方法,该方法采用多任务深度卷积神经网络提取道路图像特征,实现图像分类和语义分割任务,实验结果表明,所提方法有效的平衡了多视觉任务的精度与效率,并能准确规划出安全的避障路径,辅助机器人完成导航避障.Melo等人[15]提出一种由矩阵红外传感器与常规相机叠加组成的热测量系统,提高了AGV实时获取环境信息的能力,降低了Bug算法的传感器成本.

2 基于几何模型算法

基于几何模型的路径规划算法主要包含栅格法和Voronoi图法.其中,栅格法又包含Dijkstra最短路径算法、A*算法、D*算法及向量场直方图法等多个分支.

2.1 栅格法

栅格法(Grid method),最早于1968年由W.E.Howden提出,又称格点法或点阵法,是一种数值计算方法,用于将连续域(如平面或空间)中的各种物理量离散化,并在离散空间中求解微分方程或其它数学问题[16],其基本思想是把处理区域(如二维平面)分割成一系列小方格(称为栅格或像元).每个小方格内的物理量用单个节点(或称为格点或像素)来表示,而节点之间的值则通过对小方格之间的相对位置关系进行差分逼近来计算.

利用该类方法处理AGV路径规划及避障问题时,需要将环境中所有栅格分为自由栅格与占用栅格,并将环境内所有障碍物信息保存于占用栅格信息中,以便搜索算法在只有自由栅格的连通图中找到一条由起点栅格至目标栅格的无碰撞路径.栅格法常用的搜索算法有Dijkstra最短路径算法、A*算法、D*算法等.

2.1.1 Dijkstra算法

1)算法原理简介:Dijkstra算法由荷兰计算机科学家Edsger W.Dijkstra于1959年提出[17],可用于解决有权图的单源最短路径问题,1973年Johnson将该算法用于交通路径规划[18].Dijkstra算法适用于有向或无向带权图,其算法思想基于贪心策略,每次选择当前最短距离的节点作为下一步的处理对象,在求解过程中使用了一个距离数组记录已经确定最短路径的节点到起点的距离,以及一个集合S记录已经确定了最短路径的节点,最终求解出起点到所有节点的最短路径[19].

Dijkstra算法的基本步骤如图4所示[20].该算法最主要的两个步骤是求出从源点出发到各顶点的最短路径和遍历下一跳最短路径,如式(5)所示:

(5)

图4 Dijkstra算法步骤图Fig.4 Step diagram of Dijkstra algorithm

其中,lkj是从任意已知最短源点路径的顶点k到各顶点j的直接连接距离;dj为源点到各个顶点的最短路径;dk为已经最短源点路径的顶点k的最短源点路径;di为指定最短路径下一跳选择顶点的最短源点路径.

2)算法优缺点分析:Dijkstra算法具有较强的鲁棒性与健壮性,适用范围广,可用于非联通图,且可以得到完整路径.但它的时间复杂度非常高,用于大规模地图时计算成本极高,效率偏低.Dijkstra算法的时间复杂度为O(n2),其中n表示图中节点的数量.为了提高算法效率,通常使用优先队列来实现选择当前最短距离的节点,这时Dijkstra算法的时间复杂度可以降低到O(mlogn),其中m表示边的数量[17-20].

3)算法改进措施:得益于其较强的鲁棒性与健壮性[21],这款古老且效率较低的算法仍然吸引了众多学者的研究与改进.一部分学者们选择通过优化有权图权重标准改善该算法性能.例如,蒋丹阳[22]结合实际问题,将气温、拥挤度等特定环境参数纳入权重计算中,得到一种更加贴合其室外小车寻址需求的Dijkstra算法;刘维民等[23]同样也再传统Dijkstra算法的基础上加入了热度值对路径繁忙程度进行评估,是规划的路径更合理,预防了AGV之间的冲突.另一部分学者则通过限定搜索区域改善该算法性能.例如,黄翼虎等[24]结合时间窗算法,通过改变规划中的路径节点向量,将每一个节点的所有前节点记录在路径节点向量中,在所有的路径中,搜索出一条最短路径,保证此最短路径与其他路径无冲突;李茂森等人[25]研究了一种顾及约束条件的Dijkstra算法快速自动生成接缝线多边形的方法,通过影像外方位元素对Dijkstra算法的搜索区域进行约束,快速搜索出最短路径并生成接缝线多边形,生成的接缝线多边形中对极大与极小多边形进行基于定位影像与单张正射影像外轮廓的多边形优化,达到快速自动生产数字正射影像的目的.实验结果表明此方法在生成效率上大大优于voronoi图生成接缝线多边形方法.综上,该算法的优化潜力巨大,值得进一步研究.

2.1.2 A*算法

1)算法原理简介:A*算法由Nils John Nilsson等人于1968年提出,和Dijkstra算法一样都是使用贪心策略来解决路径规划问题的成熟算法,而A*算法实际上是对Dijkstra算法的一种扩展和优化[26-28].相比于传统的搜索算法,它引入了一个启发式函数h(n),用来评估当前节点到目标节点的距离,进而预测可以找到最优路径的下一跳节点.因此,A*算法能够更快地找到最优路径.

A*算法的启发代价函数如式(6)所示[28]:

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

(6)

其中,g(n)代表节点n至起点的代价,是当前的实际代价;h(n)代表节点n至目标点的代价,是估计代价,代价通常用欧氏距离、曼哈顿距离表示.

2)算法优缺点分析:相对于需要将所有节点展开进行搜寻的算法,A*算法最大的优点就是引入了启发信息作为向目标点移动的决策辅助,所以不再需要遍历整个地图,降低了计算复杂度,减少了时间损耗少.但是,如果代价函数选择不合理,该算法可能会输出不符合最优解的过长路径.此外,栅格法精度越高,栅格分的就越小,会导致计算工作量几何式增长及节点冗余问题.

3)算法改进措施:为了解决路径过长问题,并进一步缩短搜索时间,Chen Jiqing等人[29]结合自适应扩展方法和方向约束最优节点扩展方法,提出了一种方向约束自适应扩展双向A*算法.在与传统A*算法对比实验的结果表明,在3种障碍比例下均获得了显著更优的搜索时间,在10%和25%障碍比例下获得了更短的路径长度.为了解决节点冗余问题,秦浩然等人[30]采用了动态加权系数和引入转弯惩罚的方法,对A*算法中代价函数的实际累积代价和估计代价分别加权,平衡累积代价和估计代价对算法搜索速度的影响,构造与AGV能耗相关联的惩罚项,减少路径转折点数量,提高系统工作效率.实验结果表明,相比传统A*算法,改进算法经动态加权,搜索时间平均缩短了11.8%,引入转弯惩罚后,转弯角度平均缩短了66.1%,生成的路径质量更高.王毅恒等人[31]则在冲突A*算法基础上,增添了一个扩展节点消减模块,通过该模块可以生成一个候选节点序列,当模型部件生成的输出与实际观测值不一致时,改进的冲突A*算法会缩减可扩展的冲突节点,然后生成下一个候选诊断并进行循环,直到搜索结束;实验结果表明,改进的冲突A*算法在搜索速度上相比冲突A*算法提升50%.

2.1.3 D*算法

1)算法原理简介:D*算法(Dynamic A*)是由Sven Koenig与Maxim Likhachev于2002年提出的一种基于A*算法的增量式路径规划算法[32].D*算法通过一个启发式评估函数评估已知和未知部分的路径,动态生成从起点到终点的最佳路径,并动态更新路径,使其适应环境的变化[33].在搜索过程中,D*算法会不断更新路径上的各个节点的代价值,这样即使其中某些节点发生了变化,也可以立即确定新的最短路径.

D*算法的启发函数可传递.当中心栅格向周围栅格扩展时,可将其启发值传递给周围邻点.D*算法的代价公式由A*函数发展而来,如式(7)所示:

F(s)=G(s)+H(s)

(7)

其中,G(s)为起始点至s的代价值,H(s)为启发值,其计算方式如式(8)所示:

(8)

上式中,s′为s的拓展节点,H(s′)为s′的启发值,C(s,s′)为相邻节点的代价值,sgoal为目标点.进行栅格扩展的过程中,被扩展节点的启发值由其拓展点s′的代价值以及拓展点s′的启发值计算得来.

2)算法优缺点分析:相对于A*算法,D*算法在搜索效率方法有极大的提升,在100*100方阵图中可以节省约33%的寻址时间和74.5%的节点个数[34].但是,D*算法规划的路径大多贴近障碍物边缘,路径平滑度较差.

3)算法改进措施:研究者大多针对D*算法路径平滑度较差的缺陷进行改进.温广辉等人[35]利用贝塞尔曲线进行优化以提高路径的平滑度;刘春霞[36]采用元胞自动机扩展Moore型邻居结构,向当前点周围的16个方向进行搜索,将转动角度的最小增量降低到π/8,可有效减少机器人不必要的旋转,使得路径更加平滑.

2.1.4 向量场直方图法

1)算法原理简介:向量场直方图法(Vector Field Histogram,VFH)是由Koren于1991年提出的[37],向量场直方图法的关键是在传感器的周围建立栅格,且每个栅格对应当前AGV向该方向运动的概率指数.这样可以避免由于传感器所获得数据暂时延迟而或丢失可能导致的错误.任意时刻创建的图形都是一个划分的栅格,只有在传感器扫描范围内的数据才会在栅格内从而取代已有的旧数据.为了能够有效避开障碍物,它形成了一个极坐标图,其中x轴代表行走的方向与障碍物所构成的角度,y轴是根据占有栅格的多少来计算障碍物就在运动方向的概率,如图5所示.

图5 向量场直方图法示意图Fig.5 Schematic diagram of vector field histogram method

利用此极坐标图可以计算出机器人的行走方向.首先确定出移动机器人可以安全避开障碍物所有路径范围,再在这些范围内选择损耗最低的路径,即最优路径.损耗函数L如式(9)所示:

L=k×θtar+u×θwheel+w×θbef

(9)

式中,θtar表示目的角度;θwheel表示轮子角度;θbef表示原来角度;k、u、w为比例系数,损耗最小的就是最优路径,调整这些系数可以改变移动机器人的避障效果.

2)算法优缺点分析:VFH算法的优点包括实现简单、计算速度快以及处理噪声干扰的能力强.同时,由于该算法可以使用机器人激光扫描数据构建向量场,因此该算法还可以应用于机器人导航的许多不同领域.虽然VFH算法确实是一种有效的避障算法,但是其处理速度及精度的限制,在某些环境下,例如高速控制或需要快速反应的避障应用中,VFH算法可能无法满足要求.

3)算法改进措施:研究者们对VFH算法的改进主要针对其精度和速度方面,朱茂飞等人[38]在VFH+算法中引入车辆的最大转角约束与引导路径的离散点方向,来限制VFH+的候选方向范围,并修改代价函数获取合适的前进方向,提高了传统VFH算法的精度.D Díaz等人[39]提出了一种称为VFH+D的增强算法,该算法考虑了不同的障碍物矢量大小和动态避障的衰减,在不影响安全的情况下使AGV的平均速度提升了30%.Jake Ormond等人[40]将引入“海马体”思想,优化传感器数据的处理模式,提出了一个基于矢量的模型来支持灵活的导航,表现出强烈的方向极化,获得的路径更优.

2.2 Voronoi图法

1)算法原理简介:Voronoi图法由俄罗斯数学家Georgy Voronoi于1908年提出,是一种用于测定给定点集分割几何形状的方法,是计算机视觉和图像处理算法的重要基础[41,42],常用于自主导航机器人,如AGV或无人机的路径规划.该算法主要利用障碍物位置、工作单元边界等信息生成机器人可移动区域的多边形结构,缩小最优路径搜索范围.多边形结构的拓展需要车辆立足当前栅格坐标,计算其到周边未搜索栅格的欧式距离,选择距离较近的无障碍的栅格纳入多边形结构,如式(10)所示:

(10)

其中,D[(i,j),(x,y)]为栅格(i,j)到目标点(x,y)的欧氏距离;i,j与x,y为相应行列号.

2)算法优缺点分析:Voronoi图法能够实现平滑导航,同时避开障碍物,但是其算法时间复杂度高达O(n3),为时间复杂度最高的路径规划算法之一.

3)算法改进措施:Voronoi图算法导航路径虽然具有较好的平滑度和避障精度,但是算法的导航性能和效率较低.Abboud等人[43]在Voronoi图算法基础上,提出了一种时间复杂度为O(n7/3)的算法,降低了原始Voronoi图算法的时间复杂度.Marreiros E.C.等人[44]通过分析和计算确定了一种特定非线性情况下Voronoi图边界的框架,洞悉了AGV路径规划及避障的数学本质,精简了目标函数处理的问题.张晓贺等人[45]提出了一种异质空间下加权Voronoi图的栅格生成算法,根据空间传导能力确定每个栅格的传导权重,然后进行十字交叉光栅扫描,在距离变换中按栅格对距离进行分解,将目标影响权重和栅格传导权重纳入变换公式,最后连通每个栅格到最近目标点的最短路径,全过程不受目标数量的影响.黄莲花等人[46]采用NURBS样条规划曲线对机器人的全局路径进行细化插补,进一步提升了Voronoi图算法的路径平滑度.

3 智能规划算法

智能规划算法是一种使用启发式方法搜索空间来寻找最优路径的方法,对环境的适应能力强,能够根据规划过程中获得的新环境信息实时优化路径并进行避障,主要包括基于群体智能的规划算法和基于采样的智能规划算法两类.

3.1 基于群体智能规划算法

基于群体智能的规划算法,是运用群体智能优化算法,通过群体中个体间的协作和竞争来寻找最优路径,包括基于蚁群算法、粒子群算法、遗传算法及神经网络的路径规划算法等.

3.1.1 基于蚁群算法的路径规划

1)算法原理简介:蚁群算法(Ant Colony Optimization,ACO)[47]由意大利学者Dorigol在1992年提出,在AGV路径规划及避障中,该算法通过设置最短路程作为目标函数,运用蚂蚁寻找食物时的信息素沉淀和信息素蒸发规则,逐步搜索出最优路径.

该算法首先要计算“蚂蚁”(移动物体)在任意两节点间转移的可能性,如式(11)所示:

(11)

“蚂蚁”选择转移期望较高的节点后,进行信息素浓度的迭代,如式(12)所示:

(12)

由公式(12)得,计算每段路径的信息素浓度增加量需要累加每只“蚂蚁”其对所经节点间路径的信息素贡献取决于其信息素常数及路径长度,如公式(13)所示:

(13)

2)算法优缺点分析:本质上,蚁群算法实际上是对路径规划及避障过程中涉及参数的权重进行了优化,由于逻辑严谨、计算便捷而沿用至今[48].作为一种基于信息素的启式算法,蚁群算法可以轻松应对各种参数众多且复杂的路径评估模型.这一点在E.Alhenawi等人2023年的最新研究中得到完美体现[49],他们通过应用一些考虑到路径安全倾斜角的约束来保证所选登山路径的安全性,生成的大小可变的数据集用于在运行时间、加速、效率和成本方面评估所提出的算法,而实验结果表明并行ACO算法显着(P<0.05)优于多种传统顺序计算的规划算法.随着物流服务规模不断扩大,在本地部署算法已经不足以满足大型物流中转中心的AGV调度需求.这就需要云计算部署以集中化、资源池化的方式来应对海量的路径数据.此外,蚁群算法仍不能避免受困于局部最优解和搜索停滞问题.

3)算法改进措施:为了优化蚁群算法云端部署,研究者们进行了大量研究.Sumathi M等人[50]使用HLB混合复杂均衡算法来控制蚁群算法上云后,其平均等待时间 (AWT)、平均执行时间 (AET)、平均响应时间 (ART)、跨度、吞吐量分析、周转时间和 LB 时间都得到不同程度的优化.聂秀珍等人[51]在蚁群算法的基础上引入了探索性步长算法,可以根据当前搜索状态动态调整搜索步长,进一步提高其搜索效率和接索精度.程娟[52]在蚁群算法中加入了方向性引导以及动态优化后,进行对比实验发现改进蚁群算法较基本蚁群算法及空间最短距离算法,得到最优路径的结果更加准确,同时改进蚁群算法的迭代次数有所减少.

3.1.2 基于粒子群算法的路径规划

1)算法原理简介:粒子群算法由Eberhart于1995年提出,通常以粒子的位置和速度来代表问题的解,通过不断更新粒子的速度和位置来搜索最优解[53].很多AGV领域研究者将AGV所在的位置视为粒子位置,将粒子速度看作是代表每个节点之间的距离,通过更新粒子速度和位置,逐步搜索最优路径,以实现路径规划及避障的目标.原始粒子群算法的速度和位置迭代方法分别如(14)和公式(15)所示:

(14)

(15)

其中,c1,c2为加速常数,用于调节学习最大步长;γ1,γ2两个随机函数,取值范围[0,1],以增加搜索随机性;w惯性权重,非负数,调节对解空间的搜索范围;pbestid,gbestd分别为个体最优速度解和群体最优速度解;v,x分别为车辆速度和位置.

粒子群算法在AGV路径规划中的具体工作流程如下.首先,在粒子群算法中,每个解被表示为一个粒子,粒子的位置代表解空间中的一个候选解.在多AGV路径规划问题中,可以将每个粒子看作一个候选解,即一组任务的完成顺序.每个粒子的位置是一个长度为N的序列,表示每辆AGV要执行的任务顺序.然后,通过适应度函数评估每个粒子的路径长度和时间窗约束是否满足.在多AGV路径规划问题中,适应度函数可以用来评估每个粒子的路径长度和时间窗约束是否满足.最后,通过更新粒子的速度和位置,逐步优化解的质量.在多AGV路径规划问题中,通过更新粒子的速度和位置,可以逐步优化每辆AGV执行任务的时间和顺序,从而找到最优解或达到迭代次数.

需要注意的是,在实际应用中,还需要考虑其他约束条件,如车辆数量、载重量约束、可运载品种约束、运行路线约束、工作时间约束等.这些约束条件可以通过对粒子的速度和位置进行限制来实现.综上所述,粒子群算法可以应用于AGV路径规划中,通过将每个解表示为一个粒子,逐步优化每辆AGV执行任务的时间和顺序,从而找到最优解或达到迭代次数.

2)算法优缺点分析:相比于其他启发式算法,粒子群算法的优点在于简单易懂、易于实现以及不易陷入局部极小值,因此在AGV路径规划及避障中具有一定的应用前景.但是,该算法收敛速度比较慢,且处理离散问题仍不能完全规避局部最优解.

3)算法改进措施:秦昌礼等人[54]对粒子群优化算法进行改进,结合鸽子启发优化算法的快速收敛能力,提出一种基于改进粒子群优化和鸽子启发优化算法的两阶段混合优化算法进行全局路径规划.与传统的粒子群优化算法相比,新方法可以有效避免陷入局部最优.全局最优路径长度缩短约3.8%,减少路径规划时间.彭慕蓉等人[55]采用线性递减惯性权重改进的粒子群算法设计控制方案,最后提出时间乘误差绝对值积分准则与误差占比相结合的变化适应度函数,有效地提高了粒子群算法的收敛速度.Q.Zhao等人[56]提出了一种受人类决策和尖点突变理论启发的两阶段多群粒子群优化算法(TMPSO),该算法采用多群方法,在整个迭代过程中先后采用无约束全局优化TMPSO和约束全局优化cTMPSO的两阶段搜索策略,在第2阶段所有子群合并为一个大的群,从而进一步细化全局最佳粒子,以增强局部搜索能力.

3.1.3 基于遗传算法的路径规划

1)算法原理简介:遗传算法最早是由John Holland于20世纪70年代提出,是一种基于自然进化和遗传学原理设计的优化搜索算法,通过模拟自然的进化和遗传过程,通过选择、交叉和变异等操作,产生下一代潜在解或优化解,逐步优化最终的结果[57].在AGV路径规划及避障中,可以将AGV移动路径看作染色体,将每条路径的每个节点看作基因,通过实现遗传算法的基本操作来逐步优化并生成最优路径.

遗传算法的理论基础是图式定理.该定理可以决定下一代潜在解及优化解的规模,可以表达为公式(16):

(16)

其中,m(H,t)为在t代群体中存在图式H的串的个数;f(H)为在t代群体中包含图式H的串的平均适应值;f为t代群体中所有串的平均适应值;l为串的长度;Pc为交换概率;Pm为变异概率.

2)算法优缺点分析:与其他优化算法相比较,遗传算法具有无需求解梯度信息、并行性、全局优化能力和搜索范围大等优势.但是,遗传算法中存在一些关键参数,如种群大小、交叉概率、变异概率等,这些参数的选择对算法的性能影响很大,需要经验或进行大量试验来确定最佳参数配置,耗费更多的计算资源和时间.

3)算法改进措施:遗传算法性能强大,但计算成本高,因此研究者对其的改进措施大多聚焦于计算速度提升和计算资源节约方面.Liu Y等人[58]提出一种多自适应遗传算法(MAGA),通过引入充电任务和可变速度来优化 AGV 的任务调度,同时也考虑到了 AGV 以最大限度地减少完工时间、使用的 AGV 数量和耗电量.经过对比实验表明,MAGA 是目前应用在AGV调度领域的遗传算法中效果最好的.W Zhou等人[59]针对物流仓储过道空间狭小导致的AGV冲突问题,在适应度函数中加入了拥塞系数,使AGV小车间的冲突现象减少了4.2%.为了进一步缩减遗传算法制定最优路径的速度.Fontes等人[60]制定了一个混合整数线性规划 (MILP) 模型,并提出了一种双目标多群体偏置随机密钥遗传算法 (mp-BRKGA).实验表明,通过求解所提出的 MILP 模型可以找到近似真实的Pareto前沿,并且mp-BRKGA可以找到均匀分布的Pareto 前沿,能够匹配出降低完工时间和能源消耗的最优路径.

3.1.4 神经网络法

1)算法原理简介:神经网络(Genetic Algorithm,简称GA)最早于1943年由心理学家W.S.McCulloch提出,是一类受人脑结构和功能启发的机器学习算法[61].神经网络通畅由多层互连节点(也称为神经元)组成,每个节点对其输入执行数学运算,并将结果传递给下一层,最后一层产生网络的输出,通常是基于输入数据的预测或分类.最基本的神经网络是前馈神经网络(Feedforward Neural Network),主要使用前向传播公式和反向传播公式实现模型训练.以下是这两个公式的基本形式:

对于具有L层的神经网络,其中第i层(l=1,2,…,L)表示网络中的每一层,输入层为第0层.在每一层中,每个神经元都有一个激活函数.令a[i]表示第i层的激活值,w[i]表示第i层的权重矩阵,b[i]表示第i层的偏差向量,a[i-1]表示第i-1层的激活值.则前向传播公式可以表示为:

(17)

其中,z[i]表示第i层的加权输入(加权和加上偏差项),g(_)表示激活函数.

反向传播算法用于根据损失函数来更新神经网络的权重和偏差,以实现网络的训练.在每一层中,通过利用链式法则来计算梯度.令L表示损失函数,该函数可以是均方误差(Mean Square Error)或交叉熵(Cross-entropy)等.对于第l层的权重矩阵w[i]和偏差项b[i],则反向传播公式可以表示为:

(18)

这些是神经网络中的基础公式,用于计算前向传播以获取预测结果,并通过反向传播来更新网络参数以最小化损失函数.实际上,神经网络的更复杂的变体和层级结构可能会引入其他公式和技巧,但这些基础公式构成了神经网络的核心.

神经网络通常用于广泛的应用,如图像识别、自然语言处理和预测分析.它们特别适合于涉及大量复杂数据的任务,例如高维输入或噪声数据[62].综上,神经网络可以基于工作场景一切参数对AGV的运输过程进行建模,以更加智能高效的方式实现路径规划及避障[63].具体来说,他们可以根据来自LiDAR或相机等传感器的数据进行训练,以学习当前环境状态和AGV最佳路径之间的映射;然后,使用神经网络实时生成一个路径计划,该计划考虑了环境的当前状态和任何潜在的障碍或危险.通过学习过去的经验并不断提高路径规划及避障结果的最优性,神经网络也可以用于优化AGV的路径规划及避障过程,提高计算效率[64],同时可以提高AGV和在其环境中工作的人类的安全性.

2)算法优缺点分析:总的来说,在AGV路径规划及避障中使用神经网络有可能显著提高自动化材料处理和运输系统的效率、可靠性和安全性,前提是需要花费大量时间成本提前构建并调校数据集训练模型.此外,神经网络在处理新环境的时候,需要额外的迁移学习方法来适应新的场景与任务,甚至需要对神经网络的架构和参数进行重新配置和调整.

3)算法改进措施:由于神经网络模型训练的必要性,所以改进措施通常着手于神经网络参数和训练数据集来源两方面.Wang等人[65]开发了一种新的AGV多状态调度算法 (MSSA),该算法在 FMS 中的 AGV 利用率和总处理制造跨度之间进行了良好的权衡.与经典的空闲调度策略相比,MSSA在每次计算中调度了更多的AGV和任务,使其优化目标更接近全局优化目标.Mozo等人[66]提出应用先进的深度神经网络来预测AGV轨迹误差,即使在5G网络中出现干扰,通过捕获 PLC-AGV 连接的数据包而不使用用户设备(AGV或PLC)中的任何传感器,这有助于解决方案的实时部署.此外,部分研究者利用神经网络的强大功能进一步推进了AGV的智能化升级,比如Budzan等人[67]对ResNet50和MobileNetV2等常用于手势识别的算法进行优化修改,使用迁移学习方法进行二次训练,得到一种简单有效的卷积神经网络(CNN)来赋予AGV小车快速识别人类手势并执行手势命令的功能,测试成功率在96%以上.

3.2 基于采样的智能规划算法

使用基于采样的规划算法进行路径规划及避障包括通过随机采样点并将它们连接起来形成图来构建环境的路线图,随后搜索该图,以找到从起点到目标点的最佳路径,同时避开障碍物[68].该类算法在采样点和连接点以形成图的方式上有所不同,并且根据特定的环境和任务要求,它们各有优缺点[69].使用基于采样的规划算法实现路径规划及避障可能很复杂,尤其是对于障碍物较多的大型环境.然而,它可以为AGV在动态和不确定环境中规划路径提供一种高效有效的方法.当前常见的基于采样的规划算法有快速探索随机树和概率路线图算法.

3.2.1 快速搜索随机树算法

1)算法原理简介:快速探索随机树(Rapidly-exploring Random Tree,简称RRT)于2017由Steven M.LaValle等人提出,该算法通过随机采样环境中的点并朝着目标点构建树状图实现路径规划及避障[70],其具体流程如图6所示.

图6 快速探索随机树算法流程图Fig.6 Flow chart of Rapidly-exploring Random Tree

RRT算法的关键思想是通过不断生长的树结构来探索搜索空间,即通过随机采样新的点,并将其连接到最近的节点来扩展树,借此可以快速探索大型搜索空间,并找到有效的路径.在该算法使用过程中,最重要的是为算法选择适当的参数,如步长和迭代次数,以平衡环境的探索和开发,并确保算法根据特定的环境和任务要求进行适当的调整[71].

2)算法优缺点分析: RRT算法适用于在动态和杂乱环境中帮助AGV实现路径规划及避障,因为其树状随机采样的机制利于处理高维状态空间,并且可以快速实时探索大型和复杂的环境.但也正因为其随机性,该算法在不同时间处理同一环境、同一设备乃至同一任务都会得到不同结果.

3)算法改进措施:尽管已经具备较强的实用性,RRT仍可以通过各种修改进行扩展,以提高其性能,例如RRT*,它优化路径以获得最低成本;或者RRT Connect,它分别从起点和目标点出发生成两棵树,在地图中互相寻找直至连接成最终路径[72].为了控制其随机性,J Guo等人[73]提出了一种名为UPPHE的数据驱动方法,即反馈快速探索随机树星算法 (FRRT*),具有数据驱动的风险网络和反馈模块, 可以利用从态势数据中提取的信息来约束随机树的生长,并进行有偏调整,从而提高规划效率.仿真实验验证了风险网络指导规划的有效性,以及反馈模块带来的效率提升.H Wang等人[74]提出一种基于矢量化地图和动态约束实现的改进RRT*(Rapidly-Exploring Random Tree Star)算法,用于解决基于铰接结构和漂移环境条件的地下智能车辆路径规划及避障问题.C Zammit等人[75]建议未来的研究者尝试将启发式函数融入当前RRT算法中,以约束其随机探索的范围.他们将现有主要AGV算法代入相同的场景中进行测试,并使用相同的性能指标进行分析后发现A*算法生成相对于 RRT 算法更短的路径,是因为A*算法只探索路径生成所需的部分空间,而 RRT 算法均匀地探索整个空间.

3.2.2 概率路图法

1)算法原理简介:概率路图(Probabilistic Road Map,简称PRM)最早于1996年由Smith R等人提出,主要通过对环境中的随机点进行采样进而构建概率路图,随后使用启发式函数搜索连接采样点以形成路线图,从而实现移动机器人的路径规划及避障[76],其较为通用的启发式函数由式(19)所示:

(19)

其中,rf(c)为局部区域规划器连接点c时失败的概率;n(c)是试图连接c的总次数;f(c)是失败的次数,如果c与n连接失败,那么c和n的连接失败次数都要加一;w(c)为采样点权重系数.

2)算法优缺点分析:与之前的RRT算法类似,PRM算法可以在复杂的动态环境中帮助AGV实行路径规划及避障.然而,它需要进行大量的采样和连接,生成大量冗余采样点,占用大量计算资源.

3)算法改进措施:改进PRM算法最重要的是为算法选择适当的参数,例如样本数量和连接算法,以确保算法针对特定环境和任务要求进行适当调整,避免采样点冗余.林俊志等人[77]对全局路径规划PRM进行改进,引入椭圆约束,减少了82.7%的冗余节点,提高了规划效率.韩超等人[78]主要对一种模拟光照节点模型的PRM路径规划及避障优化算法进行研究,采用模拟光照方法,将每个节点视为光源,在未照亮的区域生成随机节点,直至光照区域能将起始点和目标点连通,生成无向有权图的边,让采样节点数为1000个的PRM算法的平均规划时间降低了88.38%.Li Qiongqiong等人[79]采用了双向增量的碰撞检测方法,并优化了碰撞检测调用次数,提高了路线图的构建效率.PRM还可以通过各种细节优化以提高其性能,例如延迟冲突检查直到实际需要最终路径的Lazy PRM,或者借助新型启发式函数优化路径以获得最小成本的PRM*[80].由上述研究可得,PRM算法在采样点数量控制方面仍然有较大的改进潜力.

4 混合算法

由于物流仓储环境与业务流程的复杂性,单一的路径规划算法往往难以满足实际应用场景的需求.因此,将优势各异的规划算法巧妙融合成为AGV路径规划及避障研究的趋势.Vikas等人[81]融合改进的双曲引力搜索算法MGSA和动态窗口法DWA,提出一种新型混合路径规划及避障算法MGSA-DWA.MGSA引入混沌因子,在近邻环境中进行混沌搜索对人工势场法进行改进,有助于帮助AGV躲避运行过程中出现的动态障碍.MGSA与传统的DWA方法结合后,在路径长度与导航速度方面都有显著提升.冯莉等人[82]则通过改进双向迪杰斯特拉算法,实现节点排序,配合A*算法的避障功能,使得路径移动距离平均下降14.74%,转向次数平均减少8%,移动时间平均减少13.41%.魏宏源[83]提出的综合粒子群算法则是兼具蚁群算法的正反馈与粒子群的多样性,快速地将多种参数引入路径评估之中,大大提高了AGV的寻址效率.马新国等人[84]则提出了一种名为RRT-Dijkstra融合算法,即在得到RRT算法规划出的一条可行路径后,向周围扩展可行区域,将可行区域栅格化,通过Dijkstra算法找出可行区域中的最短路线,优化RRT算法得出的路线.该融合算法较传统RRT算法路径缩短了19.25%,拐点减少了84.21%,迭代次数减少了71.91%.Liang等[85]针对规划效率低和成本高问题,提出一种遗传算法GA和蚁群优化算法ACOA相结合的混合算法,实验结果表明,该混合算法能够获得机器人最优路径,节省时间和成本,具有较高的鲁棒性.冯浩然等人[86]则将改进A*算法与动态窗口算法进行融合,规划出一条具有实时性的最优路径.李超[87]以提高智能仓储多AGV时间和能量利用率为总体优化目标,提出了一种结合多染色体组改进遗传算法的动态任务链调度模型,实现了对充电资源的均匀分配与区域拥挤度预测等功能库,在不改变硬件配置的情况下,改进调度相对于传统调度能够提升10%以上饱和货物处理效率,帮助企业实现降本增效.

由于AGV在物流仓储需要频繁运货,出取货次序也成为了AGV路径规划及避障的重要参数.对此,李伟民等人[88]提出一种 PRM 算法与蚁群算法相结合的融合算法,即先利用 PRM 算法进行 AGV 路径规划及避障,再利用蚁群算法决策出取货顺序,生成总的路径.他们将 10 次的PRM 蚁群融合算法的平均值与原始PRM算法进行比较,在路径长度方面缩短了5.4%,运算时间也缩短了62%.

综上所述,混合算法可以融合各类规划算法的优势实现特定的改进需求,如规划路径的准确性、路径距离以及规划路径时长等.此外,混合算法还具有良好的收敛性和效率高的特点,有利于避免陷入局部最优,提高规划路径的质量.更重要的是,混合算法不会因为AGV群体规模过大而变得难以使用.但是在选择AGV路径规划与避障算法时,仍然要以环境模型与运行条件为主要参考指标,选择满足应用需求的算法,不必盲目追求使用混合算法,以免资源浪费.

5 AGV路径规划及避障算法分析与发展趋势

5.1 对比分析

本文根据AGV路径规划及避障算法的原理,将常见的主流AGV路径规划及避障算法分为局部避障算法、基于几何模型的规划算法及智能规划算法三大类,并对主流AGV路径规划及避障算法的原理、优缺点及研究进展进行了详细介绍,如表1所示.

表1 主流AGV路径规划及避障算法汇总表Table 1 Summary of mainstream AGV path planning and obstacle avoidance algorithms

局部避障算法大多较为传统、成熟,计算方式简单,收敛速度快,且需要输入环境中障碍物的详细信息.例如,人工势场法所添加的人工势场是针对环境中潜在障碍物的;动态窗口法本质上是对AGV下一跳可能涉及的区域进行障碍物预警探测;Bug算法更是需要对路径周边的障碍物进行边界追踪操作,从而安全避障.由此可见,局部避障算法势必赋予环境参数较高的权重,适合局部问题较多的环境.但是,受限于算法结构,该类算法并不适用于参数更加复杂的高维空间,且规避局部最优的能力有限.

基于几何模型的规划算法,顾名思义,即将路径环境进行几何重构,形成环境简化模型,一定程度上具有更强的鲁棒性与应对特殊环境的能力,主要包括栅格法和Voronoi图法等.栅格法主要是基于离散的思想将二维环境地图等额分割一系列小方格,从而简化每一节点下一跳路径选择的方式.值得一提的是,向量直方图法是根据障碍物密度构建用于划分栅格的极坐标系的.Voronoi图法的收敛速度算不上优越,但是由于简化了工作环境,对环境适应性更强,且可以有效解决局部最优问题,可以对路径进行针对性优化,以更小的代价获得更优的路径.

相对于上述两类较为传统的路径规划算法,智能规划算法更为复杂的结构、更为丰富的参数赋予了其更为强大的学习能力.群智能算法应用于路径规划,具有较好的适应性,可适用于不同的应用场景,具有较好的收敛速度,但是容易出现局部优化问题;遗传算法克服了这一缺陷,但是其交叉和变异操作需要大量的计算,在降低算法收敛速度的同时实现最佳性能;结构更加复杂的神经网络需要逐步优化模型参数,因此通常需要集成其他智能算法来提高性能.

5.2 发展趋势

随着人工智能、机器学习和深度学习等技术的不断发展,AGV路径规划及避障算法也将不断演化和升级.未来的AGV系统将更加智能、敏捷和自适应,能够更好地适应复杂多变的环境和场景.未来AGV路径规划及避障算法的研究将更加关注以下几个方面:

1)强化学习方法的广泛应用.强化学习方法能够使AGV系统实现更高水平的自主决策和行为,从而更加适应不确定性和变化性的环境;

2)感知与控制的融合.将传感器感知和控制策略融合起来,实现更加全面、准确和实时的环境感知和控制决策,以达到AGV更高的路径规划及避障效果;

3)多智能体的协同合作.多智能体系统能够实现多AGV之间的协同与合作,从而进一步提高系统的效率和鲁棒性;

4)特定应用场景的需求.AGV的应用场景将逐渐扩展,从工业领域扩展到物流、医疗、仓储、航天、智能家居等领域,不同的应用领域和场景将为AGV路径规划及避障提出新的挑战.

值得一提的是,人工智能、机器学习等技术的不断发展也会带来新的挑战,如机器安全性、隐私保护、伦理道德等问题需要相关领域的专家、学者和决策者一起协作解决.

6 结束语

AGV路径规划及避障算法一直是机器人领域的研究热点和难点问题,本文所涉及的各种研究方法和技术手段也是学术界和工业界关注的焦点.在未来,随着自动化技术的推进和人工智能的普及,AGV的应用场景将会更加广泛,因此对于路径规划及避障算法的研究和优化也将变得更为重要.相信在广大研究人员的共同努力下,AGV路径规划及避障算法的研究将会取得更加丰硕的成果,为智能制造、自动化仓储等领域的发展注入新的动力.