引言

在AGV系统的路径规划系统中，很多的AGV均是建立在全局路径规划之中，在全局规划中常用的方法有Dijkstra算法、A*算、D*算法等，这些算法搜索效率低下，在AGV遇见障碍物时，多选用停车等待策略，这种方案不具备灵活性，使整个规划系统的效率低。在局部路径规划中，常用的方法有人工势场法、随机搜索树法、蚁群算法等，多数的局部规划方法容易陷入“局部最小”的困境中，无法规划出节点间的最优局部路径。为了使AGV更加智能化，必须将全局规划和局部规划进行融合规划，可以在全局路径的指引下，局部规划实际路径。但是受困于技术的瓶颈，目前整个市场中的路径规划技术均不够成熟。针对以上的问题，本文分别对全局规划方法JPS算法和局部规划方法DWA算法进行针对性优化，并将优化的JPS算法和优化的DWA算法进行融合规划，研发出高效、稳定的路径规划技术，并在实践中对其进行验证。

1. 改进的JPS算法

全局路径规划方法，跳点搜索法（Jump Point Search. 简称JPS）是基于已知的地图模型信息定义一个评估代价函数，并采用该评估函数按照跳跃搜索规则进行节点间路径搜索，与其他全局规划算法相比，JPS算法的路径搜索相率远远高于其他路径搜索算法。JPS算法的评估启发函数定义如下：

式中：f(n)是JPS算法中节点的总评估启发函数，为g(n)起始节点和目标节点之间的真实代价函数，为h(n)当前节点和目标节点之间的代价评估函数（启发式函数）。

1.1 跳跃搜索规则优化

传统的跳跃规则是从当前节点进行对角线跳跃搜索时，进行直线跳跃搜索，当遇到可跳跃节点时，返回直线可跳跃节点，当前节点的对角线跳跃搜索结束。直线方向搜索时，当遇到可跳跃节点，变返回可跳跃节点，因而导致返回节点之后的可跳跃节点无法被搜索。

为了保证更多的可跳跃节点被搜索到，因此对直线和对角线的规则进行优化：

（1）对角线方向跳跃搜索时，一直遇到障碍物、地图边界或者受迫跳跃节点才停止对角线方向搜索，并返回对角线方向上的受迫跳跃节点。

（2）在当前节点的直线搜索时，搜索直线方向的所有可跳跃节点和受迫跳跃节点，遇到障碍物、地图边界停止搜索，并将所有受迫跳跃节点加入列表中，选出最优节点。

（3）另外在最优节点评估中，将转折节点的数量作为评估路径主要依据函数，转折节点数目越少，路径的直线段距离越长，规划出的路径用时更少。

1.2 改进评估函数

评估启发函数f(n)将直接决定着路径规划的关键因素，其中评估函数h(n)是决定着最终规划的路径。假设当前节点到目标节点的真实代价为H(n)，若h(n)< H(n)时遍历搜索节点数目较多，算法运算效率低，但是能确保得到最优路径；若h(n)> H(n)时，遍历搜索节点数目少，算法运行效率高，但是无法得到最优解；当h(n)=H(n)时恰好得到最优路径。

2. 改进的DWA算法

局部路径规划方法，动态窗口法（Dynamic Window Algorithm. 简称DWA）是速度矢量空间约束内对速度组（ν，ω）进行多组采样，其中ν表示AGV直线行走速度，ω表示AGV转向时的旋转速度。根据速度组（ν，ω）在速度空间中的采样结果，模拟AGV在速度空间内一定时间间隔后的预测运动轨迹，并依据最优目标函数评估运动轨迹，从运动轨迹中选取最优轨迹并进行速度驱动。

2.1 DWA实现局部路径规划

DWA实现主要包括三个过程：建立AGV运动学模型、速度矢量空间采样和评估函数。

2.1.1 建立AGV运动学模型

运动学模型是将机器的运动轨迹按照一定的时间间隔T分割成一段一段的直线段（ν=0，ω）或者圆弧段（ν，ω），所以为了获知AGV的运动模型，就必须获知AGV的线速度ν和角速度ω，建立AGV运动学模型。

2.1.2 速度矢量空间采样

在已经获知AGV的运动模型之后，就可以在二维速度矢量空间（ν，ω）中进行多组速度采样，从而可以推算出AGV的运动轨迹，然后通过评估函数来评价轨迹的优劣。速度矢量空间V_R中是AGV的可能矢量速度集V_P、AGV许可矢量速度集V_A和动态速度集V_D三者的交集，即V_R=V_P∩V_A∩V_D。

2.1.3 运动轨迹的评估函数

采用评估函数对可行轨迹进行优劣评估，并从中选取最优轨迹作为最优路径。评估函数主要包括目标导向、安全避碰和快速行驶三个子评估函数通过对速度矢量空间逐个的预期轨迹进行评估，得到最优的路径轨迹，并获取最优速度的控制指令。

2.2 DWA算法评估函数优化

DWA算法的评估主要是从目标导向、安全避碰和快速行驶三个子评估函数方面考量：

（1）安全避障行为模糊推理，预测轨迹和障碍物之间的距离变量d采用模糊化描述，定义其中d的变化范围为[0.5m,2.5m]，距离d的迷糊描述：近距l(d=0.5m)、中距m(d=1.5m)和远距n(d=2.5m)，大于2.5m的信息均按照n处理，隶属度函数图2和图3所示。经过安全避碰计算得到的权值系数组合记为（α1，β1，γ1），其中每个子评估函数系数的设定沿根据函数的重要程度和阈值范围。

（2）目标导向行为模糊推理，目标导向主要取决于AGV和目标节点的距离d_g、方位角Dε，方位角越小和距离越远，均不利于AGV的目标导向行驶，AGV与目标节点之间的距离d_g、AGV行驶的正方向和目标节点之间的方位角Dε，方位角Dε的阈值范围是[-180°，180°]，模糊语言描述为{正+（P+），正（P），零（Z），负（N），负-（N-）}，如图4所示。模糊的输出变量后，对其模糊规则推理之后，再对进行重心法去模糊化计算得到精确的权值系数组合（α2，β2，γ2）。

（3）权值融合行为模糊推理，权值组合主要是制定规则，将安全避碰行为和目标导向行为二者融合，能够获取更加适应环境的权值系数组合。设定AGV与障碍物之间的距离d_min、AGV和障碍物之间的距离d_g作为模糊输入变量，将目标导向权值的融合系数作为输出变量，融合系数γ3的模糊语言描述为{非常大(HC)，大(DC)，中(ZC)，小(XC)，非常小(JC)}，相应的隶属度函数如图,5所示。

2.3 DWA算法仿真实验验证

采用优化的DWA算法在相同的地图模型上，进行起始节点和目标节点之间进行路径规划，局部路径规划结果如图6所示。当AGV遇见障碍物时，能够降低速度并增大目标导向系数，以便能够采集更大方位角内的速度样本，可以预测更多的行驶轨迹。优化DWA算法，在随机地图模型中进行路径规划时，能够根据路径的信息（障碍物的情况）实时改变权值系数组合（α，β，γ）的值，在遇到障碍物时，安全避碰的权值β变大，行驶速度权值γ相应变小，使AGV能够减速避开障碍物。在未遇到障碍物时，安全避碰的权值β变小，行驶速度权值γ变大，使AGV能够快速向目标节点行驶。在AGV驶离目标节点时，目标导向系数α增大，速度权值系数γ减小，使AGV慢速转向目标节点，当AGV正向目标节点时，目标导向系数α会相应减小，速度权值系数γ增大，使AGV快速驶向目标节点。

在改进的DWA算法进行路径规划的过程中，权值系数组合（α，β，γ）的数值是实时变化，在改进DWA算法规划路径过程中，对规划的数据采用时间间隔1s对（α，β，γ）的值进行采集统计整理，此次规划的耗时为20s，利用matlab中自带模糊工具箱以时间周期T=1s对权值系数组合（α，β，γ）进行数据收集，收集的数据整理结果如图7所示。

(a)传统DWA算法路径搜索结果	(b)优化DWA算法路径搜索结果

在随机地图模型中进行路径规划时，能够根据路径的信息（障碍物的情况）实时改变权值系数组合（α，β，γ）的值，在遇到障碍物时，安全避碰的权值β变大，行驶速度权值γ相应变小，使AGV能够减速避开障碍物。在未遇到障碍物时，安全避碰的权值β变小，行驶速度权值γ变大，使AGV能够快速向目标节点行驶。

3. 融合JPS和DWA规划方法及验证

融合规划方法主要研究将全局和局部规划方法进行融合统一，采用优化的JPS算法进行全局路径规划，融合DWA算法进行局部安全避障，从而可以保证路径规划的最优性。

基于优化JPS算法和优化DWA算法的融合路径规划方法的详细步骤：

（1）利用激光扫描仪扫描工作车间，建立全局变量的栅格地图模型；

（2）利用优化的JPS算法在已知的地图模型上进行全局路径规划，规划出起始节点P0至目标节点Pn的最优全局路径；

（3）提取全局规划得到最优路径的关键节点（即跳跃节点），将关键节点作为局部路径规划中的子目标节点；

（4）依次对子目标节点进行处理，利用优化局部规划DWA算法依次规划出子目标节点之间的局部最优路径；

（5）判断当前的子目标节点是否为最终的目标节点，若不是：重复执行步骤四，将下一个子目标节点作为局部规划的新目标节点，规划出相应的局部路径；若是：则表明AGV顺利到达目标节点，路径规划结束。

4. 结论

本文分别从全局规划、局部规划和融合规划三个方面研究路径规划技术，并根据路径规划技术的不足之处进行优化改进，使AGV路径规划系统更加高效、智能。

（1）对AGV的全局路径规划JPS算法的跳跃搜索的规则和最优路径的评估函数进行优化，可以搜索得到转折点较少的最优路径。

（2）对AGV的局部路径规划DWA算法中，通过对环境变量的信息进行模糊推理，建立模糊规则库，通过环境变量信息，按照模糊规则库推理得到精确的模糊变量值，实时更改权值系数组合（α，β，γ）的值，通过实时地更改权值系数使优化的DWA算法能够使用于各种复杂的工作环境。

（3）对全局规划和局部规划进行整合，通过将全局的最优节点作为局部的子目标节点，使AGV能够在全局路径的指引下，沿着局部规划的路径行驶至目标节点。

参考文献：

1. [1] 韩腾, 樊瑜瑾, 李浙昆,等. 基于PLC控制的AGV制动系统研究[J]. 机电一体化, 2013, 19(05):44-45.
2. [2] 王皖君, 张为公. 自动导引车导引技术研究现状与发展趋势[J]. 传感器与微系统, 2009, 28(12):5-7.
3. [3] 李进, 陈无畏, 李碧春,等. 自动导引车视觉导航的路径识别和跟踪控制[J]. 农业机械学报, 2008, 39(02):20-24.
4. [4] 卢冬华. 计算机控制自动导向小车(AGV)的设计与实现[D]. 上海交通大学, 2006.
5. [5] Hart P E, Nilsson N J, Raphael B. A formal basis for heuristic determination of minimum path cost[C]// Sequences, Subsequences, & Consequences. 1968.
6. [6] Brochardwyart F, Ajdari A, Leibler L, et al. Dynamics of stars and linear chains dissolved in a polymer melt[J]. Macromolecules, 1994, 27(03):803-808.