基于改进A＊算法的AGV调度研究

冯鲁波

（四川大学计算机学院，成都610065）

0 引言

自动导引运输车（automated guided vehicle，AGV）是一种智能运输设备。AGV是目前无人工厂中的重要组成部分，在自动化流水线中可以取代人工完成搬运的任务。随着制造业的发展和人工成本的提高，自动化流水线也需要相应的AGV调度系统来满足日益增长的任务需求。基于以上背景，对多AGV路径规划算法的优化提出了更高要求[1]。

Rajotia等[2]提出了基于半动态时间窗约束的路径规划算法，经过实际验证后，证明该策略可以有效降低AGV运行过程中的拥堵概率，提高系统的运行效率。Fan[3]设计了一种基于动态串联回路的AGV路径设计方法，针对于降低AGV运行回路并建立数学模型，可以有效防止AGV冲突。梁承姬[4]提出了一种无冲突的AGV路径规划方法，通过计算每一段路径上的时间窗实现冲突规避，从而给出多AGV的无冲突路径规划。泰应鹏等[5]通过时间窗与A*算法的结合，提出了一种改进的A*算法，规划好的路径会通过计算时间窗进行避障。

本文通过设置拥堵阈值，改进传统A*算法的启发函数；并减少转弯次数和约束转向角度，以减少运行时间；设计基于时间窗的规避算法以解决冲突问题，分析多AGV的冲突问题以及常见的冲突类型，预测和规避可能发生的冲突，最终获得全局最优路径。

1 静态路径规划

1.1 传统A*算法

A*算法是一种启发式路径规划算法，通过建立合适的启发函数，对周围的环境进行求解，获得启发信息，利用这些信息选择最优的目标，从而搜索到最优路径[6]。这种启发式求解不需要遍历整个地图，因此时间复杂度低，广泛应用于游戏地图寻路以及AGV路径规划领域[7]。

其中g(x)表示起点到当前节点x的最短路径成本，h(x)表示当前节点x到终点最短路径成本的预估值。

传统A*算法流程如图1所示。

1.2 改进A*算法

针对工厂环境特点和AGV的运行特征，A*算法需要满足如下约束条件：

（1）路径规划中避免过多转向。

（2）避开车流量较大的节点和路段，尽量避免与其他AGV发生冲突。

约束（1）是为了降低时间成本，AGV转向时需要经历减速、转向、加速的过程，会浪费一定时间；约束（2）可以避免部分AGV采用同一部分路径导致路段拥挤，通过调控路径的交通流量，可以降低多AGV冲突的可能性。

图1 A*算法流程

为了实现上述目标，对A*算法做出如下改进：

（1）为了避免转向过多，需要确定路径之间的角度关系，尽量减少AGV路径的转向次数。路径之间的角度计算：

式中：θ为两路径之间的夹角，x1、y1为前一段路径的起点坐标，x2、y2为前一段路径的终点坐标，后一段路径的起点坐标，x3、y3为后一段路径的终点坐标。

cosθ有以下3种情况：①cosθ>0方向基本相同，夹角在0°到90°之间；②cosθ=0正交，相互垂直；③cosθ<0方向基本相反，夹角在90°到180°之间。

在确定路径之间夹角之后，为了避免AGV选择转角过大的路径，修改启发函数h(x)，增加启发权重1-cosθ，转角小的路径会被优先选择。

（2）对于避免拥堵和冲突规避，引入路径的拥堵系数ω和时间窗算法，时间窗会在第2.3小节详细说明。为了对路径的拥堵情况进行定量监控，同时避免算法时间复杂度过高，计算每条路径在接下来要经过的AGV总数，在启发函数中引入拥堵系数来表示路径的拥堵情况，实现AGV对较拥堵路段的规避，拥堵系数计算如所示。

通过式（2）可以求出路径ab的拥堵系数

式中：wab为路径ab段的拥堵系数，lab为路径ab段的长度，nab为该时间段内通过路径ab的AGV总数，k为拥堵权重系数，路径ab的距离权重dab。

当路径ab没有AGV通过时，nab=0，则路段的拥堵系数wab=0，对启发函数没有任何影响；有多辆AGV通过时，拥堵系数随AGV数量增加，距离权重dab相应增加，通过需要的时间越长，这条路径被选择的概率会更小。

2 基于时间窗的冲突避免策略

2.1 时间窗模型

时间窗是用来记录地图中所有AGV的运行状态的模型，时间窗的横坐标表示时间段，纵坐标表示资源，即节点和路径，通过横纵坐标可以描述资源在一段时间内的占用情况[8-9]。以下是AGV运动过程的几种变速情况以及时间窗计算方法：

（1）直行通过节点或路径。从AGV到达节点边缘到AGV完全离开节点，此时AGV完全不会减速，可以按照匀速直线运动计算，通过下式计算：

式中，L为节点宽度或路径长度，v为AGV经过路口时的速度，tin为AGV进入节点的时间，tout为AGV离开节点的时间。

（2）在节点处转向。AGV在节点转向时，会先减速至转向速度，以转向速度通过节点，之后加速至直行速度。使用下式计算：

（3）启动加速及停止减速。AGV由静止状态启动，匀加速至直行速度v，假设加速度a在加速过程中保持不变，时间窗满足：

（4）等待。AGV在规避或异常时的时间窗分布满足：

式中，td为AGV等待时间。

在计算出每台AGV时间窗后，可以描述地图上所有资源在时间轴的占用情况。通过寻找各AGV的时间窗的重叠位置，即两台AGV在同一时间段需要占用同一段路径或节点，从而确定冲突节点、路径和AGV，根据冲突的类型进行相应的调整，进行时间窗的重计算，从而解决拥堵和冲突问题。同时，运行中的AGV的时间窗信息可以为后加入的AGV路径规划提供参考，避免拥堵。

2.2 冲突类型

在工厂环境中，节点和路径资源是有限的，当多辆AGV在工厂中运行时，会有很大的可能性在同一时间占用同一资源，而资源同时只能被一辆AGV占用，此时就会发生冲突。根据冲突位置和AGV的运行状态，可以分为以下几种冲突类型：相向冲突、转向冲突、路径冲突等。

（1）相向冲突。多辆AGV在可双向行驶的路径上相向行驶发生冲突，在没有外力干预的情况下无法自发解锁，需要有AGV前往相邻路径避让或后退。

图2相向冲突

（2）转向冲突。不同路径的多辆AGV在很短的时间内前往相同的节点，并且其路径互相被占用，这样就会产生节点冲突，需要为这些AGV规划避让策略，避免同时占用同一节点。

图3转向冲突

（3）路径冲突。AGV在同一条路径上，且方向相反，必须有AGV退让才可以解决冲突。

图4路径冲突

（4）工作点冲突。一辆AGV在工作点进行装卸操作时，另一辆AGV需要通过该点。由于AGV装卸操作需要一段时间，因此另一辆AGV的路径会受阻，需要进行规避或等待。

图5工作点冲突

在A*算法规划完路径后，计算每台AGV的时间窗，检查地图中运行的AGV的时间窗是否有冲突，根据时间窗的重叠情况判断冲突类型，然后进行冲突的规避，流程如图6所示。

图6冲突规避流程

2.3 冲突解决方式

监测到AGV冲突后，根据冲突类型给出规避策略：

（1）相向冲突。首先计算两台车的优先级，优先级低的AGV避让。其次寻找空闲路径，令AGV前往空闲路径规避。重新计算时间窗，检查是否有冲突，若无冲突，则按新路径执行；若有冲突，重新寻找路径。

（2）转向冲突。首先判断路径暂时不会被占用的AGV，令其按原路运行，另一台AGV暂时等待。前一台AGV离开冲突节点后，暂停的AGV继续运行。

（3）路径冲突。首先两台AGV暂停，分别检查两台AGV是否有可以后退规避的路径。令可以后退规避的AGV后退，直到另一台AGV离开冲突路径。若两台AGV都可以避让，计算任务优先级，优先级低的AGV进行避让。

（4）工作点冲突。对于这种工作点占用问题，可以选择原地等待和重新规划路径两种方式。首先查询占用工作点的时间窗，估计等待时间。然后锁住工作点，为等待的AGV重新规划一条路径，并计算时间窗。比较两种方式的时间成本，选择成本较低的方案。

3 仿真实验

3.1 静态路径规划仿真

为验证改进A*算法的有效性，分别对传统A*算法、蚁群算法和改进A*算法进行实验对比。

实验使用1000×1000的栅格图进行仿真，预设AGV平均速度10 m/s，在地图中可通行位置随机产生起点和终点，并进行路径搜索，重复200次，最终实验结果如表1所示。

表1 3种不同算法路径规划表现

通过表1可以看出，改进的A*算法相比于传统A*算法和蚁群算法，路径长度分别缩短了6.5%和1.7%，效果不明显；但是AGV运行耗时分别减少了17.6%和12.5%，由于避免了部分冲突，有效缩短了AGV的运行时间。同时，路径的拐点分别减少25%和33.3%，避免了AGV运行过程中的频繁转向。

3.2 冲突避免实验

针对时间窗的避碰策略进行测试，分别测试10台、20台、30台AGV同时在地图中运行时的规避能力，实验结果如表2所示。

由仿真实验可以看出，在30台AGV运行的情况下，基于时间窗的避碰策略相对于停止-等待法可以节约19.8%的等待时间，且随着AGV数量的增加，其性能较为稳定，可以满足实际需要。随着任务数量的增加，规避算法的性能在正常范围内波动，保持稳定。

表2不同AGV数量下算法规避性能

图7 不同任务数量下规避性能

4 结语

本文对A*算法的多AGV优化进行了研究，加入了拥堵系数和时间窗模型。使用拥堵系数改进A*算法的启发函数，避免经过拥挤的路段；通过对转角的约束，减少了AGV的转弯次数，减少了时间消耗。使用时间窗模型进行路径冲突的监测，并根据冲突类型给出解决策略。最后对提出的算法进行了模拟测试，验证了算法的有效性。

使用拥堵系数和时间窗模型可以有效减少多AGV调度过程中的冲突问题，提高了系统的运行效率，对多AGV系统的调度问题有很好的指导意义。