紧致密集Auto Store系统AGV路径规划与避碰策略

王晓军，王 博，杨春霞，晋民杰，陈海波

1.太原科技大学 交通与物流学院，太原 030024

2.大连海亿丰悦科技有限公司，辽宁 大连 116033

Auto Store 是一种集货格与AGV 搬运小车于一体的新兴紧致密集型仓储系统[1]。与传统密集型仓储系统相比，该系统取消了巷道，将货格组合在一起，利用货格顶层的轨道实现AGV 小车的移动，其空间利用率达到90%以上，系统硬件结构如图1 所示。该仓储系统具有货格设计模块化、拓展性强、存储密度大、订单周转速度快等优点，因此，自2012 年在德国出现后，并迅速在欧洲市场上流行起来，但目前在我国还鲜少见到，相关学术研究也较少，在中国知网上检索关键词“Auto Store”，相应文献只有两篇[2-3]，且研究内容为货位优化及库存利用，与AGV调度相关研究尚未见到。

图1 Auto Store仓储系统三维图Fig.1 3D drawing of Auto Store storage system

Auto Store 系统硬件包括出入库作业台、AGV、可拓展立式货格和料箱4部分，货物均存于料箱中。料箱尺寸标准统一，每16 个为一垛，存放在立式货格内，料箱储存兼货架和堆放两种状态。因此，与穿梭式货架、自动化立体仓库等传统密集型仓储系统相比，Auto Store 系统AGV 调度较为复杂。以出库作业流程为例，AGV接到指令后，需要行驶到指定货格顶层，如果所需料箱在货格底层，需先将上层料箱一一抓取出来存放在周围空余货格内，直至指定料箱位于最顶层，随后抓取并运送至出库作业台。分析料箱出入库流程，可知该系统AGV调度存在以下难点：

（1）为提取货格中低层料箱，会出现大量短途挪库作业；（2）AGV都在顶层移动，同时进行出入库作业时，冲突较多；（3）因货格模块化设计，在特殊地形或仓储空间中，会出现结构不规整的情况，易出现死角。因此，对AGV进行优化调度，是保证Auto Store系统高效运行的基础和核心环节。

从研究内容上，AGV 调度包括初始路径规划和行驶过程中的冲突管理。对单AGV 调度，学者研究重点在于对传统算法如A*算法[4]、Dijkstra 算法[5]、遗传算法[6]、人工势场法[7]等进行改进和优化，以提高搜索效率。多AGV调度在单AGV基础上进行，但主要关注点是AGV之间的冲突。多AGV同时运行时，容易出现因两个及以上AGV占用相同路径节点而导致路径死锁的现象。为避免死锁，国内外学者进行了相关研究，根据研究思路可分为以下两大类。

第一类是全局规划法，即通过算法求出无冲突的AGV 路径方案，此方法建模难度高，算法复杂，搜索效率偏低，且对于AGV数量较多的系统，容易产生无可行解。魏宏源等[8]基于混合蚁群粒子群算法规划多AGV路径，利用信息素的特点避免AGV冲突的产生，但该算法在小环境、多AGV 的情况下会产生没有可行解的情况。Miyamoto等[9]研究有容量AGV系统的调度和无冲突路由问题，建立整数规划模型，提出局部/随机搜索方法来解决AGV路径规划问题。

第二类统称离线-在线两阶段法，离线阶段规划初始路径，此时允许轻微的死锁现象产生；在线阶段指在实际运行中，通过预测，对将要发生冲突的AGV进行路线二次规划，以此避免死锁[10]。与第一类方法相比，第二类方法灵活度高、适应性强，为复杂系统广泛使用。

王鹤南[11]针对人机混合环境下多AGV 系统，通过Dijkstra算法给出AGV初步运行方案，再利用遗传算法对冲突路径进行二次规划。高新浩等[12]基于时间窗改进了两阶段动态调度算法，搭建多AGV动态调度系统，大幅度降低系统死锁现象出现的频率。张政[13]改进Dijkstra 算法，考虑转向对AGV 的影响，规划多AGV 路径，并分析冲突类型和解决策略。于赫年等[14]对仓储式多AGV 系统进行路径规划及仿真，首先对引入动态机制对静态算法进行改进，其次提出一种具备多步前瞻性的主动避障算法，优化路径并提前避开交通拥堵路段，减少冲突可能性和重新寻路代价。也有部分学者对“离线-在线”中某阶段进行重点研究，如曹小华等[15]对冲突进行预测，建立避碰决策。

从前文分析中可知，Auto Store系统具有短途挪库作业多、顶层AGV 冲突多、货架结构性角落多等特点，很难一次性求得无冲突AGV路径规划方案，因此，本文采用离线-在线两阶段AGV 调度方法进行研究。然而现有研究成果中，AGV路径规划与任务调度相关度高，通过已安排的任务顺序进行时间窗计算，以此检测路径是否存在冲突，对于“货到人”仓储系统研究较少，无法适应Auto Store系统的要求。

综上，本文研究了一种改进的“离线-在线”两阶段AGV 调度方法：离线阶段，在寻优区域划分、路径代价函数、转弯系数等方面对传统A*算法进行改进，在保证搜索效率的同时获得冲突较少的初始路径方案；在线阶段，根据Auto Store 结构特点，有针对性地给出冲突解决策略。最后利用Flexsim 仿真验证本文方法的有效性。

1 Auto Store作业流程及仓储建模

1.1 入库作业流程

入库作业分为三个阶段。

第一阶段：库订单到达至入库任务分配确认。当入库订单信息到达，仓储管理系统对订单进行预处理。确认订单与库内商品的信息是否一致，检索库内现有商品数量，并根据补货数量安排空箱。确认入库订单信息无误并安排商品存储料箱后，仓储管理系统将产生入库任务，传递给AGV任务执行系统。

第二阶段：AGV 搬运料箱至入库口。AGV 执行系统接收仓储管理系统所发出的入库作业任务，将任务加入待执行任务序列，并根据任务序列依次执行任务。AGV 执行系统每接收一个当前任务，将重新检索订单商品及附近可用AGV的位置。只有在系统存在空闲状态AGV 时，才会进行AGV 的调用，将任务分配给具体执行AGV 并更新AGV 状态为忙碌。确认订单商品位置及任务执行AGV后，AGV执行系统进行初步的路径规划，AGV根据规划移动至订单商品存储货位，若目标商品料箱上次堆叠有其他料箱，AGV 先将上层料箱进行移库，搬运至附近可用货位存储并更新商品位置信息，直至目标商品料箱处于顶层，AGV将目标料箱抓取并搬运至入库口放下，由人工进行商品入库作业。

第三阶段：补货完毕，AGV 将料箱摆放至货格中。根据看板系统的入库信息作业完毕后，任务执行系统搜索系统中最深可用货格，确认料箱存储位置，调用AGV抓起料箱，进行料箱存储回库的搬运工作。待AGV 搬运料箱存储完毕，任务执行系统更新AGV 工作状态为空闲，AGV再次可被调用，并更新商品存储的数量信息与位置信息。至此，入库作业完毕。入库作业流程图如图2所示。

图2 入库作业流程图Fig.2 Flow chart of warehousing operation

1.2 出库作业流程

出库作业流程同样分为三个阶段：（1）出库订单到达至产生出库作业任务；（2）AGV任务执行系统获取任务，确定调用AGV，将出库商品料箱搬运至出库口进行人工拣选；（3）出库商品料箱返回仓储货位。

出库作业很多操作与入库作业相反，受篇幅所限，不再详述。具体出库作业流程见图3。

图3 出库作业流程图Fig.3 Flow chart of outbound operation

1.3 仓储系统环境建模

AGV路径规划之前需对系统环境建模。建模常用的方法有可视图法、栅格图法和拓扑图法等。

可视图法通过获取AGV 的移动坐标位置来判断AGV是否进入障碍区域或环境外部。优点是可以较好地描述环境中的边界和障碍物，执行性较强，但缺点是难以对不规则形状进行描述，并且随着障碍物数量的增加，算法复杂度上升。

栅格图将环境中的空间用矩形进行分解，障碍空间为黑色，通行空间为白色，矩形单元格越小，对环境中的元素描述越详细。单元格一般以一个AGV 大小为准，可表示行进的路线。其缺点是无法表示出单元格之间的联系关系，即AGV 行进中的转向。此外对不规则边缘的描述能力也较弱。

拓扑图将每一个可行进位置视为一个点，点与点之间的连线表示为点之间的位移代价或权重，拓扑图在计算机中的存储较为方便，占用内存空间少，信息搜索速度快。

综合以上分析，本文采用拓扑图建模，原因有二：一是Auto Store系统货格之间的距离相同，采用连线方式描述货格之间的关系较为方便；二是由于Auto Store系统具有可拓展性，可能存在不规则仓储角落，拓扑图可进行详细描述。

考虑到在货格顶层，AGV 仅可以在上下左右方向移动，不能进行斜方向移动，因此使用曼哈顿距离来表示AGV行进距离。

2 改进双层A*算法求解AGV初始路径

2.1 A*算法改进思路

A*算法是一种启发式路径规划算法[16-17]，考虑到已走路径成本的情况下，加入启发式函数，使算法向着目标前进，减少算法对路径网络的搜索量，其公式表示为：

其中，f(n)表示从初始状态经由状态n到目标状态的代价估计，g(n)是在状态空间中从初始状态到状态n的实际代价，h(n)是从状态n到目标状态最佳路径估计代价，即可以控制算法搜索方向的启发式函数。

根据Auto Store系统特点，AGV路径规划需要面临两个问题：一是大量、短暂的短途AGV 挪库作业，二是拓展性结构导致有狭窄角落出现的情况。为提高搜索效率和搜索精度，本文在传统A*算法基础上，提出一种基于拓扑权重的双层A*算法，算法改进思路如下：

（1）对环境区域进行划分；（2）上层寻优过程中，将每个区域视为一个节点，搜索从含有起点的区域节点到含有终点的区域节点最短路径；（3）下层寻优在上层寻优结果内进行，能在较少的搜索环境内寻得详细路径，提高搜索效率。

改进的核心部分在于如何对区域进行划分，及算法函数的确定，将决定搜索性能。

2.2 环境区域划分

在拓扑图建模基础上，将环境地图分区。为使问题具有普适性，讨论存在非规则角落的情况。如图4 所示，每个点为一个货格，共布置97个货格。

图4 拓扑图区域划分Fig.4 Area division of topological graph

仓储规模和布置形式不同，分区方法并不唯一，但经过前期试算，给出以下原则：

（1）对规则区域，划分成数个正方形，如图4右边的6 块（区域2、3、4、6、7、8、9、10、11），正方形能使二次寻优过程中AGV 各方向行驶概率相同。本例子中，每个正方形区域包含9 个货格，能使上、下层搜索规模大致相当，如果是大规模仓储问题，可以适当扩大正方形区域的节点数。

（2）对非规则区域，首先按照规则区域划分，再进行判断，确定是否形成独立区域。如区域1包含了12个节点，如果分成“3+9”的形式，只包含3节点的区域内AGV行驶路径单一，分区失去意义，故将其合并。对区域5，AGV 能走环线，可将其认定为一个单独的区域。非规则区域的判断也不是唯一的，可根据具体情况确定。

综上，给定不规则布置的97 组货格共分为11 个区域。对规则区域和非规格区域的处理，可满足仓储系统可拓展的特点，可行性强。

2.3 考虑交通冲突的启发式函数

上层寻优过程中，将每个区域视为一个节点，搜索从含有起点的区域节点到含有终点的区域节点最短路径。

根据起、终点所在区域的相对位置，会出现以下情况：（1）AGV 起点与终点在同一区域或在相邻区域，区域间连线或不存在或唯一，直接转向下层寻优；（2）AGV 起点与终点在相隔区域，有多个途径区域可以选择，如图4中的1-2-3-7和1-2-6-7，此时需要选择交通冲突最小的路径。

为使AGV 路线避开交通繁忙的区域，减少交通冲突的可能，可设定AGV数量越多的区域，其进入代价越高。然而在特殊情况下，路径节点数多并不意味交通压力小，如图5 所示，（a）、（b）两个图1、2 区域中路径节点数相同，但可以看出，相较于区域1，区域2发生AGV死锁的情况可能性更高。

图5 相同路径节点举例Fig.5 Example of nodes with same path

因此，可以以区域内路径节点之间连线数的倒数作为区域进入代价指标之一，确定启发式函数h(n)如式（2）所示：

其中，na为i区域中现有AGV数量；wi为i区域中节点连线的个数；βi为AGV对节点连线的占有系数。

若一个区域内有p条节点连线，在该区域中至多可以同时容忍q辆AGV 进行作业，则β=p/q，通过β系数可以有效控制区域进入代价的大小，当该区域AGV数量饱和时，β确保AGV 不会因绕路转弯较多而驶入AGV饱和区域。

通过路径代价启发式函数，得到上层寻优所得区域路径为1-2-6-7，如图6所示。下层寻优在上层寻优结果内进行，能在较少的搜索环境内寻得详细路径，提高搜索效率。

图6 改进A*算法上层寻优结果Fig.6 Upper layer optimization of improved A* algorithm

2.4 考虑AGV转弯的代价函数

多数路径规划算法中，所求路径为理论距离最短路径，没有考虑到AGV 转向所消耗的能量及时间要高于直行。图7 中，A、B、C 三条路径长度一致，然而在实际运行中，A 路径转向次数最少，要优于B，更要优于C。近年，不少学者注意到了此问题，Qu 等[14]和于赫年等[14]均在路径规划时考虑了转弯约束。

图7 路径规划对比图Fig.7 Comparison of path planning

本文在A*算法的代价函数g(n)中考虑转弯代价，使路径寻优倾向于转弯数小的路径。

A*算法对下一节点进行搜索时，有AGV 当前位置节点(xn,yn)、父节点(xn-1,yn-1)及子节点(xn+1,yn+1)等信息，可利用节点信息对转弯进行判定。当(xn,yn)-(xn-1,yn-1)与(xn+1,yn+1)-(xn,yn)相等时，表示AGV 向下一节点移动时没有发生转向；当两者不相等时，表示AGV 在当前节点(xn,yn)发生转向。设1 为AGV 移动一个单元格的基础代价，k表示AGV的转弯代价系数，取值范围为0.1～0.2[19]，则实际代价函数g(n)为：

2.5 基于拓扑图权重的双层A*算法步骤

根据式（1）、（2）和（3），可得到基于拓扑权重的双层A*算法的函数。与传统A*算法相比，有以下优点：双层寻优能降低搜索量、提高搜索效率；基于区域AGV数量和路径节点的启发式函数能获得冲突较少的初始方案；转弯修正系数能进一步优化线路。

算法具体步骤如下：

步骤1建立OPEN LIST、CLOSE LIST 以及open list、close list列表用于存储区域节点、路径节点、起点与终点位置信息。

步骤2判断起点与终点所在区域相关关系，若两者在同一区域，跳转步骤8；若两者在相邻两个区域，转向步骤7；否则转向步骤3。

步骤3搜索OPEN LIST中F(n)的最小值，设其为当前节点，并将该节点从OPEN LIST 中删除，加入CLOSE LIST中。

步骤4对当前节点相邻节点进行搜索，若相邻节点不在OPEN LIST 中，将其加入OPEN LIST，将当前节点设置为它的父节点，并更新F(n)、G(n)与H(n)；若其已在CLOSE LIST中，不再处理。

步骤5判断沿当前节点到它的路径g(n)值是否更小，若更小，则将当前节点作为它的父节点，同时更新f(n)和g(n)。

步骤6重复步骤3 至步骤6，直至将终点所在的区域节点加入CLOSE LIST，并输出区域节点路线的最优路径，转向步骤7。

步骤7将区域节点所包含路径节点信息加入OPEN LIST列表。

步骤8对OPEN LIST、CLOSE LIST 列表中的数据进行步骤3至步骤5操作。

步骤9重复步骤3 至步骤5，直至将终点节点加入CLOSE LIST并输出最终路径。

3 AGV冲突检测及解决策略

由上章改进A*算法所得AGV 初始规划路径只是在给定环境下冲突较少的路径，并不能完全避免冲突。在实际运行过程中，避免冲突有两种思路：一是根据时间窗对AGV 路线进行调整，将同一时间占用同一节点的AGV 错开时间；二是设置AGV 优先级，当发生交通冲突时，根据优先级决定占用和避让的顺序。Auto Store 系统中，AGV 都在顶层作业，且挪库较多，时间窗调整易对后续作业产生影响，造成调度混乱，因此，本文采用第二种方法，首先分析系统所有冲突类型，其次给出基于AGV 位置信息的冲突检测方法，最后根据冲突类型给出对应解决策略。

3.1 AGV冲突类型分析

AGV在Auto Store货格顶层的网格中运行，如图4所示仓储系统中，冲突可以分成侧向、同向、对向三大类，再根据具体行驶方向细分，此细分是后续冲突检测的基础。

（1）侧向冲突。指交叉方向的两台AGV 同时预约同一个节点。根据它们通过交叉节点后的行驶方向，又可细分为以下几种情况：

①侧向-两直行冲突，指两台AGV通过交叉口后均直行，如图8所示，为方便后续描述，设为冲突1。

图8 侧向-两直行冲突（冲突1）Fig.8 Side-two direct conflict（Conflict 1）

②侧向-一直行一转弯冲突，指通过交叉口后，一台AGV直行，一台AGV转弯，根据转弯方向不同，可分为图9中（a）、（b）两种情况，设为冲突2、冲突3。

图9 侧向-一直行一转弯冲突Fig.9 Side-one direct one turn conflict

②侧向-两转弯，指通过交叉口后，两台AGV 均转弯，根据转弯方向不同，可分为图10中（a）、（b）、（c）三种情况，分别设为冲突4、5、6。

图10 侧向-两转弯冲突Fig.10 Side-two turn conflict

（2）同向冲突。指两台AGV 朝一个方向行驶所产生的冲突。当AGV速度一致时，不会产生赶超现象，所以该冲突产生的原因是前一台AGV在某货格处停下作业。此时，可将停下的AGV 转化为临时障碍物。该冲突设为冲突7，如图11所示。

图11 同向冲突（冲突7）Fig.11 Conflict in the same direction（Conflict 7）

（3）对向冲突。指同一方向的两台AGV 相向而行所产生的冲突，设为冲突8，如图12所示。

图12 相向冲突（冲突8）Fig.12 Conflict in the opposite direction（Conflict 8）

综上，分析AGV 行动路线，可将冲突分为3 大类8小类，覆盖全面。

3.2 基于AGV位置信息的冲突检测方法

根据AGV 路径节点的位置信息进行冲突的检测，即对每台AGV 当前路线中下一个路径节点进行搜索，若同一时刻两个AGV 的目标节点相同，则在该节点会出现冲突。根据AGV 位置参数，给出该冲突类型的判断规则。

（1）位置参数

将两台AGV分别记为A和B。以A为例，设当前节点位置坐标为(axn,ayn)，则父节点位置为(axn-1,ayn-1)、子节点位置为(axn+1,ayn+1)、二代子节点位置为(axn+2,ayn+2)。同理，确定B的当前节点、父节点、子节点、二代子节点坐标分别为(bxn,byn)、(bxn-1,byn-1)、(bxn+1,byn+1)、(bxn+2,byn+2)。将同一时间A 和B 的节点信息进行比对，则可以判断出是否存在冲突及冲突类型。

（2）判断规则

在判断之前，首先给出两个条件：

条件1 每个路径节点仅能被一台AGV占据。

条件2 (axn,ayn)≠(bxn,byn)，即当前两AGV 各占据一个不同的路径节点。

其次，判断是否产生冲突，用A、B两台AGV下一个节点坐标是否相同来表示，如某一时刻满足式（4），则会产生冲突。

再次，通过位置约束条件来判断冲突类型。

①对冲突1，式（5）表示两台AGV均直行，式（6）表示两AGV不为相向形式。

②对冲突2，式（7）表示A 直行，B 转向，式（8）表示B转向后与A在同一条网格线上且行驶方向一致。

③对冲突3，需满足式（7），同时还需满足式（9）表示B转向后与A在同一条网格线上但行驶方向相反。

④对冲突4，式（10）表示A、B 均需要转向，式（11）中，（11.1）表示转向后A、B子二代不在同一个点，（11.2）表示B 子二代不会占据A 节点位置即不是冲突5，（11.3）表示A子二代不会占据B节点位置即不是冲突6。

⑤对冲突5，满足式（10），同时满足式（12），即B子二代会占据A当前节点位置，但A子二代不会占据B当前节点位置。

⑥对于冲突6，满足式（10），同时满足式（13），表示子二代互相占据当前节点位置。

⑦对冲突7，首先满足（5），表示直线行驶，再满足（13）。

⑧对冲突8，设B为停止AGV，则满足式（14）：

3.3 两AGV冲突解决策略

传统多AGV冲突解决策略以等待为主[9]，即冲突的两台AGV 中，一辆AGV 提前停车让行，等待另一台AGV通过后再继续运行。为防止等待时间过长导致后续AGV 发生持续拥堵甚至系统死锁等问题[20]，本文在传统冲突解决策略的基础上，拓展了AGV 回退等待策略和AGV路线重新规划策略。针对各冲突类型确定的解决策略如下：

步骤1确定冲突类型。

步骤2对可以用时间换空间的冲突，选择等待策略：（1）对冲突1和冲突4，令A或B等待，另一先行；（2）对冲突2和冲突3，另直行车A先行，转弯车B等待；（3）对冲突5，转弯车A 先行，B 等待；若等待时间超过设定时间，转步骤5。

步骤3对互相锁死且无法用时间换空间的冲突，选择回退策略：对冲突6 和冲突8，A 先行，B 回退，直到A转弯为止；如B 回退不能进行或回退时间超过设定时间，转步骤5。

步骤4对存在AGV 停止或出现故障的冲突，如冲突7，先选择等待策略；如超过设定时间，转步骤5。

步骤5对等待或回退AGV重新规划路线。

3.4 多AGV冲突解决策略

以上两AGV 冲突分析基于一个假设，即两车之间的避让不会对第三辆AGV 产生影响。若在发生冲突时，其中上述AGV 运行路线还有AGV 在运行，冲突解决策略会对后续AGV产生影响，在这种情况下，不仅需要考虑当前冲突AGV 的冲突解决，还需要考虑冲突解决策略对后续AGV的影响。

如图8 所示两AGV 直行冲突中，无论哪辆AGV 停车避让均可。然而在图13所示多车交通冲突中，AGV2采取停车避碰对AGV 系统所产生的等待时间较少，若AGV2 优先通过，则AGV1、3、4 均需要停车避让，增加了系统总等待时间。在此情况下，仅采用AGV 优先级避碰的方法，显然不能使AGV 系统的避碰等待时间最短，需要考虑到在冲突区周围的AGV 状态，以及采用不同避碰策略及避碰车辆选择对冲突区域AGV 的整体影响。

图13 多AGV交通冲突示意图Fig.13 Traffic conflict diagram of multiple AGVS

针对多AGV 冲突问题，本文在初始路径规划环境地图划分的基础上，提出一种基于贪心算法的区域避碰决策算法。

设n为区域内AGV总数，X表示为区域内AGV所采取的避碰决策集合，目标函数C=minϕ(X)为总决策代价最小。

其中，避碰决策xi：

对于区域中的n个AGV 进行避碰决策，若采用遍历AGV 每个决策的方法进行避碰决策寻优，则问题求解规模为4n。随着AGV数量增加，问题的规模将会成为指数爆炸。

贪心算法的思想是将问题分解为不同阶段的小问题，每阶段问题都选择该阶段的最优解。首先要确定对AGV执行决策选择的顺序，在确定的AGV执行决策选择的顺序下，对每个AGV进行决策，一共有n!种排序，随着AGV数量增多，问题规模的增加是可控的。

不同决策的代价为该AGV等待时间或重新规划时间，若AGV 不采用避碰策略，则代价为0。通过对不同AGV决策的遍历，得到不同的决策代价，选择代价最小的方案。

4 基于Flexsim的AGV路径规划与避碰仿真

4.1 仿真模型与拓扑图设计

采用Flexsim模型对Auto Store仓储系统进行了建模与仿真，验证本章中所提出的改进A*算法与冲突解决策略。根据出入库作业流程分析，确定模型元素对应表，见表1。

表1 Flexsim模型元素对应表Table 1 Corresponding table of Flexsim model elements

设出入库作业台的处理器选择操作员进行出入库作业，处理时间为5 s，AGV在下降通道的纵向运行时间设置为5 s，装载时间根据不同货品频率大小分别设置，其平均时间为10 s且AGV水平移动速度恒定。

建立出入库仿真模型如图14 所示，模型中顶层节点网络即为AGV仓储拓扑图，将货架进行隐藏后，可清晰地看到AGV路网。

图14 出入库仿真模型建模Fig.14 Inbound and outbound simulation model

对AGV地图的区域划分可以通过对路径节点的标签设计来实现，按照区域划分法，将10×10 的地图划分为9个区域，见图15。

图15 AGV仓储地图区域划分Fig.15 Division of AGV warehouse map

在仿真模型中，路径节点的动态权重设计，需要靠节点的进入和离开触发进行设计，当AGV 首次进入区域的标签节点时，进行进入触发，将该区域AGV数量加1，并将上一区域AGV数量计数减1。当此区域AGV数量已达上限，则关闭节点所有边，该AGV在节点进行等待，直至AGV数量减少后，节点边开放。节点触发设置如图16所示。

图16 节点设置示意图Fig.16 Schematic diagram of node setting

4.2 改进A*算法的算法分析及性能评价

为验证改进A*算法的有效性，从算法分析和性能评价两部分进行。

（1）算法分析

通过简单算例分析A*算法的路径规划过程，并与标准A*算法进行比较。

首先讨论单AGV 无障碍路径规划工况。设AGV数量为1，生成5个仓储作业任务，任务属性及坐标依次为：入库（5，6）、出库（7，3）、出库（2，4）、入库（9，3）、出库（3，2）。用两种算法进行路径规划，记录AGV 行走路线，得到路径轨迹，详见图17、18。在此工况中，没有障碍物和其他AGV，所以是否进行环境分区无影响，但由于改进A*算法引入转弯代价系数，使得总路程转弯数减少了1个。

图17 标准A*算法路径示意图（单AGV无障碍工况）Fig.17 Path diagram of standard A* algorithm（single AGV-barrier free condition）

图18 改进A*算法路径示意图（单AGV无障碍工况）Fig.18 Path diagram of improved A* algorithm（single AGV -barrier free condition）

其次，讨论单AGV 且存在障碍路径规划工况。路网中存在停止不动的AGV，这对行动的AGV而言是路径障碍。为模拟此情况，在上述无障碍规划路径中增加三个静止障碍AGV，障碍坐标分别为（2，6）、（9，9）、（5，2）。标准A*算法和改进A*算法所得路径分别见图19、20。此工况中，改进A*算法倾向于避让存在障碍物的区域，如2号任务路线。此外，加入转向系数后，改进A*算法的转弯数更少。

图19 标准A*算法路径示意图（单AGV存在障碍工况）Fig.19 Path diagram of standard A* algorithm（single AGV-barrier condition）

图20 改进A*算法路径示意图Fig.20 Path diagram of improved A* algorithm（single AGV-barrier condition）

（2）性能评价

为进一步验证改进A*算法的有效性，设置不同工况下的多AGV路径规划试验。根据改进A*算法思路，从所得初始路径方案所包含冲突数验证算法的有效性，从算法搜索时间验证算法效率，并与标准A*算法进行对比。

以图19 所示存在静止障碍仓储模型为基础，分析AGV数量和作业任务数量对初始路径方案的影响。

首先设工作任务为30，出库和入库属性随机生成，AGV数量分别为2、3、4、5辆，算法对比结果见表2。当AGV 数量较少时，两种算法均能生产冲突数较少甚至没有冲突的初始路径方案，随着AGV数量增加，冲突数也随之增加。但改进A*算法能在进化时避开AGV 数量多的区域，因此，冲突数增长幅度较慢。在搜索效率方面，当工作任务量固定时，AGV数量变化对计算时间影响不大，但改进A*算法能小幅度提高搜索效率。

表2 AGV数量变化对初始方案的影响（工作任务=30）Table 2 Impact of AGV quantity change on initial scheme（task=30）

其次，设AGV 数量为5，作业任务数量分别设为30、40、50、60，出入库属性随机生成，对比结果见表3。该案例只在左右下角设置了一个出库平台和一个入库平台，使得大部分作业需要在图15 所示网格地图中的下半部分进行，随着工作任务增加，冲突数增长，但改进A*算法冲突数整体要少于标准A*算法。在搜索效率上，计算时间与作业量正相关，但改进A*算法能小幅度提高搜索效率。

表3 作业任务数量变化对初始方案的影响（AGV=5）Table 3 Impact of job task quantity change on initial scheme（AGV=5）

4.3 AGV冲突解决策略仿真验证

生成包含冲突的初始路径方案后，还需在后续运行过程中解决相应冲突。利用图14所述10×10仓储模型，随机产生50 个任务，出入库属性随机，设AGV 数量分别为2、3、4、5。当AGV 行驶过程中如遇到冲突分别执行两种冲突解决策略，一是系统自带优先级策略，二是本文所提改进策略。使用仿真软件试验器功能，对发生冲突后的AGV等待时间进行统计，见表4。

表4 不同策略下的AGV冲突等待时间Table 4 Waiting time of AGV conflict under different policies

当AGV 数量较少时，系统会自动生成无冲突路径方案，所以AGV冲突等待时间为0。AGV数量增加时，冲突数增加，相应的冲突等待时间也在增加，然而本文提出的贪心算法决策集合考虑到冲突解决策略对后续AGV的影响，因此，冲突时间增长速度较慢。

4.4 离线-在线两阶段AGV优化调度方法验证

在4.2 节和4.3 节，分别验证了改进A*算法和改进冲突解决策略的有效性。本节将在仓储规模增大的情况下，进行两阶段联合仿真，评价目标为所有作业完成时间。作为比较，确定标准方法对应为标准A*算法和优先级冲突解决策略。

设仓储地图规模为70×70，每一个仓储单元为一个坐标节点，四个出入库作业台的位置分别为A1（0，0）、A2（0，70）、A3（70，0）、A4（70，70），AGV 空载移动速度为1 m/s，负载行驶速度为0.8 m/s。忽略仓储的纵向高度，仅考虑AGV在水平面的位移距离，且网格中任意两点之间的距离使用曼哈顿距离表示。实验的任务数据以solomon 标准数据集中的R102 数据集作为基础实验数据，并在此基础上随机增加任务作业属性。分别生成20、30、50 个作业任务，AGV 分别为2、3、4、5。计算结果见表5～7。

表5 工作任务为20时的数据对比Table 5 Data comparison when task is 20

表6 工作任务为30时的数据对比Table 6 Data comparison when task is 30

从表5～表7中可以看出，在任务数固定时，AGV数量越多，任务完成时间越短，但改进算法总体作业时间要小于标准算法作业时间，提高程度从10.95%到19.18%不等。同时，对固定任务数，随着AGV 增加，作业时间减少幅度降低的原因是订单的生成需要时间，AGV空闲时间增多。

表7 工作任务为50时的数据对比Table 7 Data comparison when task is 50

5 结束语

Auto Store是一种新型紧致密集仓储系统，其高效运行离不开AGV 初始路径规划及其后续的冲突解决策略。针对该系统运行特点，本文提出了一种基于改进A*算法的路径规划及冲突解决策略方法，主要结论如下：

（1）本文给出的改进两阶段AGV 路径规划法将路径规划与后续冲突解决分开，灵活性强，适合于Auto Store密集仓储系统。

（2）初始路径规划阶段，本文给出的基于动态拓扑图权重的双层改进A*算法，尽可能避开多AGV 区域，减少了AGV 冲突发生的可能，有效减少了算法路径节点的搜索量。仿真实例模拟了无障碍路径规划、静止障碍路径规划、多AGV 多任务、不同仓储规模等工况，结果表明本文所给改进A*算法能得到冲突数较少的初始路径，同时，搜索效率较标准A*算法有小幅度提高。

（3）交通冲突解决阶段，在对冲突类型分类基础上，根据AGV 位置信息，给出冲突预测方案，简单有效；对于两AGV 冲突，拓展了AGV 回退等待策略和AGV 路线重新规划策略；对于多AGV冲突，提出一种基于贪心算法的区域避碰决策算法。仿真结果表明，对同一初始路径方案，本文改进策略能使AGV等待时间降低，提高作业效率。

（4）离线-在线两阶段联合仿真表明，本文所给改进方法能缩短整体作业完成时间，且随着AGV 数量及任务量增多，优化幅度得到提高。