摘要

摘 要：针对自动导引小车（AGV）在仓储物流搬运系统中的路径冲突问题，提出了一种基于时空冲突约束的 A*算法。首先，在拓扑栅格地图的基础上加入时间轴建立时空地图模型，再针对时空地图的特点和冲突约束条件重新设计 A*算法的子节点扩展规则和节点评估函数。利用改进后的 A*算法按照优先级顺序为各个 AGV 规划路径，规划完成一条路径后，用݉ܽݎ݇表记录其在时空地图中节点信息，再利用改进后的 A*算法结合݉ܽݎ݇表进行新路径的搜索。通过仿真实验证明了该算法能够有效避免碰撞及死锁，并能够综合考虑等待和更换路径两种冲突解决策略的时间花费，获得时间花费较少的路径。

0 引言

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

路径冲突是指同一时段多台AGV在行驶过程中路线出现交叉或重叠，主要可分为路口冲突、追赶冲突和相向冲突[2]。路径冲突一旦处理不当，就会出现AGV碰撞或死锁问题，严重影响到多AGV系统的工作效率。一般而言，解决AGV的路径冲突的方法可分为两类：（1）全局规划方法，也即静态路径规划，该类方法主要是应用数学规划方法为AGV在地图中提前规划好无冲突路径[3-4]。这种方法能够为系统规划出全局最优路径，但是AGV运行在一个高度动态的环境中，并不总能在规划的时间到达指定的位置，而且随着AGV数量的增加必将出现路径冲突。（2）局部规划方法，此类方法AGV在行驶过程中根据系统实时状态确定其行驶路径，因此也称为动态规划策略。如：Tanaka等[5-10]为了避免AGV的路径冲突和死锁，根据路网的实时状态动态调整AGV的路径；于赫年等[11]提出多步前瞻的算法来避免冲突，AGV每行驶一步都根据系统的实时状态，规划出接下来前 K 步的路径。动态路径规划能够及时应对AGV之间的碰撞冲突，但无法得到全局最优路径。

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

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

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

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

a 拓扑栅格地图

b 时空地图

图 1 地图模型及路径显示

在拓扑栅格地图模型中可以采用二维矩阵来记录每个节点的状态，但却无法记录每个节点的具体占用时间。而多AGV路径规划时，需要综合考虑各节点的具体占用时间来规划出最优路径，故本文在拓扑栅格地图的基础上增加时间轴，来建立时空地图模型,如图 1b 所示，