多自动导引车路径规划的时空冲突约束A*算法

李 鑫，廖凯文，陈 薇，张晓庆

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

0 引言

随着电商、快递和新能源等新兴产业的高速发展，大幅带动了仓储自动导引小车(Automated Guided Vehicle, AGV)的全面需求，为智能仓储系统的研发与应用注入了全新的活力。对于任务规模化、货架密集型的仓储作业环境，路径规划算法对提升智能仓储系统整体性能、降低各方面运营成本和提高企业利润等都起到了关键的作用，而如何解决AGV之间的路径冲突，一直是多AGV路径规划的关键问题之一[1]。

路径冲突指同一时段多台AGV在行驶过程中，路线出现交叉或重叠的现象，主要分为路口冲突、追赶冲突和相向冲突[2]。路径冲突处理不当会出现AGV碰撞或死锁，严重影响多AGV系统的工作效率。一般而言，解决AGV路径冲突的方法分为两类：

(1)全局规划方法 即静态路径规划，该方法应能够用数学规划为AGV在地图中提前规划好无冲突路径[3-4]。虽然如此，但是由于AGV运行在一个高度动态的环境中，并不总能在规划的时间到达指定的位置，随着AGV数量的增加，必将出现路径冲突。

(2)局部规划方法 该类方法的AGV在行驶过程中根据系统实时状态确定其行驶路径，因此也称动态规划策略。例如，文献[5-10]为了避免AGV的路径冲突和死锁，根据路网的实时状态动态调整AGV的路径；于赫年等[11]提出多步前瞻算法来避免冲突，AGV每行驶一步都根据系统的实时状态规划接下来前K步的路径。动态路径规划能够及时应对AGV之间的碰撞冲突，但无法得到全局最优路径。

综合考虑上述两种方法的优缺点，很多学者提出两阶段路径规划策略，即离线阶段采用全局路径规划，在线阶段根据冲突类型进行局部调整。例如，王佳溶等[12]和泰应鹏等[13]采用基于时间窗的两阶段控制算法，第一阶段为各AGV规划全局最优路径，第二阶段计算各AGV的节点时间窗，根据时间窗重叠情况侦测路径冲突，并通过更换路径和等待的策略来解决冲突；为进一步减轻动态阶段规划的负担，贺丽娜等和[14]和乔岩等[15]在离线阶段将Dijkstra算法和时间窗原理相结合，顺序规划各个AGV的无碰撞路径，该方法大大降低了动态阶段出现冲突的几率，从而简化在线阶段复杂的路径调整过程。上述两阶段路径规划策略在解决冲突时，均未综合考虑等待和路径更换两种方法的代价，因此规划出来的不一定是最优路径。

为了在保证路径无冲突的基础上规划出用时更少的路径，本文提出一种基于时空冲突约束的A*算法。该方法将冲突检测与规避融入节点搜索过程中来实现无冲突的路径规划，并通过综合评价规避后的子节点代价找出用时最少的路径。多AGV路径规划过程即利用改进后的A*算法，按照优先级顺序为各个AGV规划路径，规划完成一条路径时，用mark表记录其在时空地图中的节点信息，再利用改进后的A*算法结合mark表搜索新路径。

1 多AGV路径规划时空地图模型

本文基于仓储物流的应用背景进行研究。因为在仓储物流中需要将货物运输到指定地点，所以在环境中需要通过设置与位置信息相互关联的节点来为AGV指明装载点或卸载点；同时，在进行多AGV路径规划时需要计算各个节点准确的占用时间，采用栅格表征节点的大小比较合适。鉴于此，本文在栅格地图的基础上进行拓扑建模，将关键栅格拓扑为路径节点，普通栅格拓扑为维持连接性的边，构建拓扑栅格地图，如图1所示。

拓扑栅格地图模型可以采用二维矩阵记录每个节点的状态，但是无法记录每个节点的具体占用时间，而多AGV路径规划时，需要综合考虑各节点的具体占用时间来规划最优路径，因此本文在拓扑栅格地图的基础上增加时间轴来建立时空地图模型，如图1b所示。拓扑栅格地图中的路径节点s(x,y)对应时空坐标系中的节点s(x,y,tin,tout)，其中：x,y坐标表征路径节点的空间信息；tin，tout分别为进入和离开该节点的时刻。Δt为AGV移动一个节点栅格所需的时间，

(1)

式中：LC为车身长度；L为一个栅格的长度；v为AGV速度。ΔT为AGV移动两相邻节点所需的时间，

(2)

式中n为相邻节点的栅格数。通过时空栅格法建立工作环境模型后，利用二维元胞数组mark记录各节点的占用时间段集合，其中节点(x,y)的占用时间段集合

(3)

(4)

式中i为占用节点的AGV编号。同时，基于本文的应用场景，提出如下规定：

(1)每个栅格同一时刻只允许一辆AGV占用，且AGV在边上均可双向行驶。

(2)每辆AGV一次只能完成一个任务，接到调度指令时不能中途返回，且AGV保持匀速行驶。

(3)任意两个相邻节点间的路径均可容纳AGV车身，不存在一辆AGV同时占用两条路径的情况。

2 基于时空冲突约束的A*算法

2.1 基于时空冲突约束的子节点扩展

传统的A*算法在拓扑栅格地图采用四子节点扩展方法，如图2a所示；本文针对时空地图的特点，设计新的子节点扩展方式，如图2b所示。其中P1，P2，P3，P4表示以父节点P0为中心扩展的4个子节点，其实质是拓扑栅格地图上扩展的4个子节点在时空地图上的位置。在多AGV路径规划过程中会因多个AGV竞争同一节点、路段而导致冲突、死锁等问题。多AGV的碰撞冲突分为节点冲突(如图3a)、相向冲突(如图3b)和追击冲突，本文假定AGV的行驶速度不变，因此不考虑多个速度不同的AGV在行驶中造成的追击冲突。

为了在解决路径冲突时能够综合考虑路径更换和等待的时间代价，本文将冲突检测与规避策略融入节点搜索过程，并结合mark表中的节点占用时间信息来约束子节点扩展，具体步骤如下：

步骤1在时空地图中通过父节点P0扩展4个子节点P1，P2，P3，P4。

步骤2根据4个子节点的x，y坐标得到对应节点已占用的时间段集合mark{x,y}，结合x，y坐标以及已占用的时间信息获得时空地图中已占用的节点。

步骤4判断是否潜在相向冲突。若该节点在时空地图中与已占用的时空节点不存在重叠，则检测是否存在相向冲突。如图4b所示，时空地图中父节点P0和其中一子节点P1形成的路径与其他AGV运行路径存在交叉，若扩展该节点，则可能与其他AGV存在相向冲突，因此P1不作为此次P0扩展的对象。

2.2 基于时空地图改进的节点估价函数

传统A*算法的估价函数

f(z)=g(z)+h(z)。

(5)

式中：g(z)为起始节点Ps到当前节点Px的实际代价；h(z)为当前节点Px到目标节点Pg的启发函数。传统栅格地图中，启发式函数多采用当前节点到目标节点的曼哈顿距离h(z)，

h(z)=|Px_x-Pg_x|+|Px_y-Pg_y|。

(6)

式中：Px_x，Px_y分别为当前节点Px的x，y坐标;Pg_x，Pg_y分别为目标点Pg的x，y坐标。

传统A*算法在出现距离相同的路径时会随机选取一条路径，不考虑路径的平滑度，然而选择平滑度高的路径能够降低控制难度。因此，本文在A*算法的实际代价值中加入拐点惩罚因子，并针对时空地图的特点，将实际代价值设定为实际用时g′(z)，即

(7)

式中：Ps_tout，Px_tout分别为离开起始节点和当前节点的时刻；tα为拐点惩罚因子；m为到当前节点时总的拐点次数。将启发函数设定为曼哈顿距离对应的时间花费h′(z)，

h′(z)=h(z)Δt。

(8)

综上所述，基于时空栅格的节点估价函数

f′(z)=g′(z)+h′(z)。

(9)

2.3 基于时空冲突约束A*算法的流程

A*算法的规划过程主要通过开集C和闭集O两个节点元素集合，以及相关节点的扩展与评价得到最终结果。表1所示为传统栅格地图的A*算法和本文所提算法具体流程的对比。

表1 两种算法主要流程的对比

3 基于时空冲突约束A*算法的多AGV路径 规划

3.1 多AGV静态路径规划过程

假设某一时刻有K辆小车需要规划路径，每个小车已经分配好任务，即给出起止点和优先级，按照优先级的顺序依次为各AGV规划路径。首先，在时空地图中为优先级最高的AGV规划最短路径；然后，根据优先级最高AGV的时间空间信息，为次优先级AGV规划出与最高优先级AGV无碰撞最短路径。重复上述过程，直到规划完所有AGV，具体步骤如下：

步骤1初始化路径表PATH={0}和节点占用时间记录表mark{X,Y}={0}。

步骤2将K个任务分配给K辆AGV，根据AGV所承载任务的优先级，从高到低对K辆AGV进行排序AGV(1)>AGV(2)>…AGV(k)…>AGV(K)，初始化预规划的AGV编号k=1

步骤3判断是否k≤K，是则执行步骤4，否则转步骤5。

步骤4利用基于时空冲突约束的A*算法结合mark表对AGV(k)进行路径规划，将所得路径节点存入PATH，并用路径节点坐标更新mark表，令k+1，转步骤3。

步骤5将规划好的路径表PATH中的节点信息分别发送给各对应的AGV，判断是否有新的任务请求，有则转步骤2，否则继续等待新的任务请求。

3.2 多AGV动态路径调整过程

在实际运行过程中，由于环境不稳定，会出现很多突发情况，例如避障传感器检测到前方移动障碍物而自动停车、断电停车等，导致AGV不能准确按照预先规划的时间到达和离开相应的节点，若未及时调整AGV的路径和运行时间，则会出现大量冲突而造成死锁。针对这种情况，本文设计一种动态路径调整策略，该策略包括两部分：

(1)mark表的更新。上位机调度系统根据AGV的实时状态更新mark表：①若调度系统发现有AGV断电停车，则将mark表中该栅格的占用时间置为无穷大；②调度系统根据AGV电机编码器信息获取其实时位置，对比mark表中的时间信息，若发现有延迟，则根据当前位置计算得到新的后续节点时间，更新mark表。

(2)若AGV在行驶过程中检测到即将进入的栅格被占用时，则以当前节点和时间作为起始节点信息，结合mark表规划出一条新的路径，并将新的路径信息发送给上位机调度系统。

3.3 多AGV路径规划算法评价指标

所有AGV到达终点的用时能够反映路径规划算法的优劣，故系统评价指标为

(10)

式中：T为所有AGV到达目标点的总体用时；n为AGV的数量；ti为第i号AGV到达目标点的时间，

ti=gi_tout-si_tin。

(11)

式中：i为AGV的编号；gi_tout为AGV到达目标点的时刻；si_tin为第i辆AGV从起始节点出发的时刻。

4 实验仿真

4.1 仿真平台

本文选用MATLAB 2015作为仿真工具，在仿真平台下开发图形用户界面(Graphical User Inter face, GUI)用于设置地图环境，并显示各AGV的路径规划结果，仿真界面如图5所示。为验证本文算法能够在保证无冲突、无死锁的情况下规划出总体用时较小的路径，设计了3个算例，3个算例中均设定栅格的每条边长L=2.4 m、AGV的速度v=0.5 m/s、AGV车身长LC=0.6 m，各算例目的如下：算例1验证基于时空冲突约束A*算法中估价函数的拐点惩罚因子能够使规划的路径更加平滑；算例2验证本文算法中的动态调整机制能够有效避免因AGV出现时间延迟和断电停车造成路径拥堵而导致的死锁问题；算例3验证基于时空冲突约束A*算法能够综合考虑等待和更换路径两种策略用时，获得总体用时较传统两阶段算法更小的路径。

4.2 算例仿真及结果分析

4.2.1 算例1

在一个横向通道数和纵向通道数均为30的栅格地图中，分别采用加入拐点惩罚因子和未加入拐点惩罚因子的时空冲突约束A*算法对20，40，60，80，100辆AGV进行路径规划，起点和终点任意设置，出发时刻设为[0,12 s]之间的随机数。两种方法规划得到路径的总拐点数和总用时分别如图6和图7所示。

图6和图7所示分别为不同数目AGV时，采用基于时空冲突约束A*算法和未加入拐点惩罚因子的时空冲突约束A*算法的路径总拐点、总用时。由图6可知，基于时空冲突约束A*算法因为在估价函数中加入了拐点惩罚因子，所以使系统规划出的路径拐点更少。由图7可见，加入拐点惩罚因子后规划出的路径总用时基本无变化，进一步说明基于冲突约束A*算法中加入拐点惩罚因子能够使系统规划出更优的路径，而且随着AGV数量的增加，这种优势更加明显。

4.2.2 算例2

算例1中的仿真结果表明，基于时空冲突约束A*算法中加入的拐点惩罚因子能在一定程度上减小时间花费，下面通过两个算例验证本文算法能够通过动态调整，在一定程度上避免道路拥堵导致的死锁。

(1)当AGVi按照预规划的路径行驶时，设置AGVi原规划路径上有一辆AGV出现时间延迟并造成拥堵，经过本文算法动态调整得到的结果如图8所示。图中两个大正方形分别表示AGVi的起、止节点，箭头所指为AGVi，白色小方块表示其他AGV，虚线为AGVi预规划的路径，实线为AGVi调整后的路线。AGVi行驶到箭头所指位置时检测到下一步要进入的栅格被占用，则以当前位置和时间为起始点，结合更新后的mark表进行路径规划。根据mark表中记录的信息，综合考虑等待和更换路径代价后，发现更换路径更节约时间，因此舍弃了等待的方式，在一定程度上避免了等待所导致的道路拥堵和死锁。

(2)当AGVi按照预规划好的路径行驶时，在其预规划好的路径上设置一辆AGV断电停车，得到的结果如图9所示。图中两个大正方形分别表示AGVi的起、止节点，箭头所指为AGVi，白色小方块表示断电停驶的AGV，虚线表示AGVi预规划的路径，实线表示AGVi调整后的路线。从图中结果可知，AGVi行驶到箭头所指位置时，接收到系统中存在其他AGV断电停车的告警，立即结合更新后的mark表规划出一条新的路径，避免了无限等待导致的死锁。

4.2.3 算例3

在一个横向通道数和纵向通道数均为30的栅格地图中，分别采用传统两阶段法和基于时空冲突约束A*算法对20，40，60，80，100辆AGV进行路径规划，起点和终点任意设置，出发时刻设为[0,12 s]之间的随机数。两种方法规划得到路径的总等待时间、总用时分别如图10和图11所示。

图10和图11所示分别为不同数量AGV时，采用传统两阶段控制策略算法和基于时空冲突约束A*算法规划得到的路径总等待时间和总用时。从图10可见，基于时空冲突约束A*算法因路径拥堵造成的等待时间较传统两阶段控制策略算法大大降低。由图11可见，基于冲突约束A*算法在避免冲突时，能够综合考虑等待和更换路径的时间代价，规划出总用时较传统两阶段控制策略算法更少的路径，而且随着AGV数量的增加，该方法的优势更加明显。

5 结束语

本文针对多AGV路径规划问题，提出一种基于时空冲突约束A*算法的多AGV路径规划方法。该算法通过将冲突约束条件加入路径搜索过程来避免AGV之间的节点冲突和路径冲突，从而规划出无冲突路径；同时，在路径搜索过程中加入等待子节点，通过综合考虑更换路径和等待用时来规划耗时最少的路径。最后，通过实验验证了所提算法能够在保证所有AGV所行路径无冲突、无死锁的情况下，获得耗时最少的路径。