近年来，随着物流业的发展，普遍对物流的时效性和准确性提出越来越高的严苛要求。为缓解物流行业高成本和低时效问题，智能化仓库应运而生。自动化导引车（AGV,Automatic Guided Vehicle）作为智能化仓库必不可少的载体之一，在智能化立体仓库广泛应用，成为学者研究的热点问题。

随着物联网技术的不断发展，高效的调度管理和路径规划成为AGV研究热点和得到更广泛应用的难点。针对该问题，国内外学者做了大量研究，诸多成果在行业得到推广应用。房殿军等[1]依据电商行业仓储需求，提出自动化立体仓库中AGV群里静态路径规划方法及动态避障决策策略；徐镇华等[2]在考虑AGV运行时间窗的基础上提出两阶段AGV路径规划方法并建立模型，采用改进Dijkstra算法求解验证其方案有效可行；廉胤东等[3]提出在视觉引导条件下，建立多AGV系统模型，采用改进A*算法求解验证系统运作效率的提升；霍凯歌等[4]针对特定区域下，考虑集装箱码运作需求建立GV调度管理的混合整数模型，并采用GUROBI和遗传算法结合进行求解。此外，AGV系统避碰策略也得到广泛研究。Singh Y等[5]提出考虑安全距离的改进A*路径规划算法，提高系统效率有效改善冲突异常；泰应鹏等[6]考虑AGV动态运行的节点时间窗，建立多AGV避碰数学模型，采用A*算法求解模型，避免AGV碰撞异常。

多数针对AGV系统多集中在适应特定场景的路径规划采用单一避碰策略。本文考虑智能仓库物流运作复杂环境下，采用以二维空间描述仓库多AGV运作拓扑地图，用Logistic函数求解多AGV系统路径使用频次的负载因子，将该函数融入到改进A*算法求解以均衡地图各段路径负载，提高运作效率；提出并行避碰机制以解决多AGV运作环境下由于路径冲突、节点等待影响运作效率的问题。

研究对象为仓库复杂物流作业区域下的多AGV系统。仓库采用拓扑图法将仓库AGV运作环境抽象为特征节点和节边，即：52个特征节点，89个特征边，包含拣货、出入库、充电、搬运功能区。

图1所示，1～8节点：分拣区，堆垛机根据指令从货架取货至AGV;9～40节点：AGV搬运作业节点；41～48节点：出入库区；A～D节点：充电区。本文聚焦AGV路径规划和动态避障问题，逻辑框架图2所示。

图1 某智能仓库物流拓扑节点图  下载原图

Fig.1 A Warehouse logistics topology node diagram

图2 逻辑框架图  下载原图

Fig.2 Logic flow chart

对模型假设：AGV速度1 m/s；相邻节点：5 m;AGV节点转向时间2 s；障碍检测1次/s；检测半径5 m。

AGV任务来源：(1)搬运任务；(2)AGV自主充电和停靠；针对搬运任务，本文采用先到先服务原则。针对AGV充电和停靠作业，设定当电量低于20%时，优先执行充电，不接受搬运任务；在充电过程中，电量低于50%，继续充电任务；电量大于50%，执行搬运任务，AGV任务执行优先级规则如图3所示。

图3 AGV任务执行优先级  下载原图

Fig.3 AGV task execution priority

基于特征边负载因子的路径规划目标：(1)路径最短；(2)时间最短；目标的达成都无可避免路径繁忙程度不同，为平衡负载考虑为路径设置特征边的负载因子。该负载因子作为惩罚项作用于特征边长度，繁忙特征边，负载因子越大，同样环境下增大特征边长度。采用Logistic函数描述对i特征边的负载因子φi:

式中：ni为特征边i通过AG车频次，N为所有特征边AGV总频次。仓库拓扑图中特征边长度权值[7]:

基于时间窗的多AGV路径规划在路径规划问题中，A*启发式算法描述为：f(n)=g(n)+h(n)(3)式中，f(n)：起始节点经过节点n到目标节点的距离代价评估，g(n)描述起始节点行驶至目前节点的实际距离；h(n)描述目前节点行驶至目标节点的距离代价评估。算法思想：AGV从起始节点起算法不断搜索当前节点至目标节点的最小距离h(n)min，以此选择AGV小车路径的下个节点，已达到求解目标函数f(n)min。多AGV系统在运行过程中，此时需对A*算法进行改进，引入不确定时间ts改进A*算法：f(n,ts)=g(n,ts)+h(n,te)(4)式中：g(n,ts)描述起始节点s到节点n的实际时间；h(n,te)描述从节点n到目标节点e的时间预估。

定义AGV起始节点s、当前节点e、目标节点i坐标分别为(sx,sy),(nx,ny),(ex,ey)。当AGV节点s出发，此时g(s,ts)=0，相邻i,j两节点时间代价估计：Q(wij(t))，则当前任一特征节点i到目标节点e

可描述为[8]:

设定转弯时间T=2 s，通过规划路径和两节点的相对位置，确定AGV在节点i是否需要转弯，在理想状态下，两相邻特征节点时间间隔Tij=g(j,ts)=g(i,ts)，可得：

A*算法维护两个列表：表Open List和Close List，算法索引过程：

(1）起始节点s处f(j,ts)=0，并记录AGV起始节点ts，此时g(s,ts)=0，将特征节点s添加进Close List;

(2）节点s可达的特征节点加入Open List中，将起始节点从Open List中删去，加入到Close List。

(3）将Open List表中各特征节点中f(i,ts)取最小值加入到Close List[8];

(4）若Close List表中包含终止特征节点，则算法停止搜索；若表不含终止特征节点，则返回（2）。

多AGV路径规划，采用改进A*算法执行AGV路径规划，A*算法迭代流程如图4所示。

分别指派1#AGV和2#AGV完成任务A和B。任务A指派1#AGV：特征节点27→特征节点22；任务B指派2#AGV：特征节点13→36。

图4 多AGV路径规划迭代流程图  下载原图

Fig.4 Iterative flow chart of multi AGV path planning

图5 某智能仓库物流拓扑节点图  下载原图

Fig.5 A Warehouse logistics topology node diagram

调用改进A*算法分别对1-2#AGV路径规划如上图5所示。1-2#AGV时间窗如下：

    下载原表

A和B在29节点出现交叉冲突。假设任务A优先级高于B，同时采用改进A*进行路径规划：

    下载原表

由表2所示：任务A和B执行时间窗不再冲突，实例验证改进A*算法能对多AGV系统进行路径规划。

此外，当AGV和任务足够多时，特征边“繁忙”不一，Logistic函数描述负载因子均衡化仓库特征边路径负载，对优化多AGV系统路径。如随机给定仓库500个任务序列，分别应用改进A*算法求解考虑Logistic函数描述负载因子下和不考虑负载因子的最优解，统计每条特征边负载，即AGV通过频次，如图6所示。

如图6所示，Logistic函数引入A*算法能有效均衡特征边负载。然而当多AGV系统足够复杂时，上述模型多出过多理想化假设，实际运行不可避免出现AGV系统出现等待、碰撞等路径冲突。

图6 有无Logistic函数对比图  下载原图

Fig.6 The comparison with or without Logistic function

图7 AGV碰撞类型  下载原图

Fig.7 AGV collision types

常见的冲突，如图7所示：（a）相对冲突；（b）节点占用冲突；（c）交叉冲突；（d）货架占用冲突[9]。

针对以上存在四种碰撞类型，为建立AGV碰撞模型，设定以下参数：

(1）描述n#AGV的路径规划中，特征节点m的ID编码；

(2）处于特征节点m的n#AGV上下相邻节点描述：-1、+1;

(3）描述n#AGV到特征节点m的时间代价；

结合以上参数，建立任两AGV冲突类型检测模型：

(1）若满足（7）同时满足约束条件(8)，则任两AGV在特征边(y(x),y(x)+1)发生相对冲突：

式中：µ，冲突检测系数，为保证模型检测准确性和实用性，根据实际运作系统，设置系数常数。

(2）若满足（7）同时满足约束条件(9)，则任两AGV在特征边(y(x),y(x)+1)发生交叉冲突：

(3）若满足（10）同时满足条件(11)，则任两AGV在特征边(y(x),y(x)+1)发生交叉冲突：

(4）若满足（10）同时满足条件(12)，则任两AGV在特征边(y(x),y(x)+1)发生货架占用冲突：

针对仓库多AGV系统，当AGV冲突时，让优先级低的AGV等待。显然传统的等待策略大幅度降低系统的运行的效率，换句话说，通过牺牲系统的效率解决AGV碰撞问题。

多AGV系统的冲突解决策略对于智能仓库的安全性和高效性运行至关重要，采取避障策略是关键，基于此，文中对传统等待避障策略改进优化，提出并行动态策略。根据碰撞类型，提出解决避障措施[10]:

(1）等待策略：即传统避障策略，不再赘述；

(2）更改路径规划策略：当任两AGV路径冲突时，任务优先级较高AGV执行原路径，另一AGV在删除物流拓扑图冲突的特征节点和特征边，重新进行路径规划，执行路径规划次优解[11];

(3）任务重新指派策略：当任两AGV路径冲突时，任务优先级较高AGV执行原路径，另一AGV关闭任务，该任务优先指派给未发生冲突且距离该AGV最近的AGV执行该次搬运任务。

上述3种策略中，考虑应用的普适性，采用等待和更改路径规划策略并行的自适应解决策略。

针对3.2提出的策略、更改路径规划策略以及两者并行混合动态策略进行算例验证。设定如下优先级递减任务，Case1:1#AGV执行优先级较高搬运任务w1，从特征节点17→特征节点19;Case2:2#AGV执行搬运任务w2，从特征节点26→特征节点02;Case3:3#AGV执行搬运任务w3，从特征节点21→特征节点40;Case4:3#AGV执行搬运任务w3，从特征节点07→特征节点29。

分别采用改进A*算法得出1-4#AGV路径规划，如图8所示。

图8 多AGV路径规划简图  下载原图

Fig.8 the Multi-AGV path-planning diagram

采用等待策略和更改路径规划策略结合动态混合策略下，采用改进A*算法[12]，对上述任务序列求解，不难得出仓库中AGV经过各特征节点和特征边的时间窗，如表3所示：

    下载原表

在采用等待策和更改路径规划策略并行的自适应解决策略，完成任务27 s；此外，当单独采用等待策略时，4#AGV任务路径w4：特征节点07→15→23→31→30→29→28,1-4#AGV完成任务需要37 s；单独采用更改路径规划策略时，2#AGV任务路径w2：特征节点17→25→26→27→19,1-4#AGV完成任务需要29 s。不难看出相比单独采用等待策和更改路径规划策略，采用两者并行的自适应解决策略更有优，效率更高。

本文针对智能仓库多AGV系统的路径规划和避障策略问题展开研究。首先，仓库采用拓扑地图法将仓库物理空间抽象为二维坐标模型的基础上，同时创造性的应用Logistic函数描述地图特征边负载，在考虑任务优先级的情况下采用改进A*算法对仓库多AGV系统进行路径规划；然后基于多AGV系统存在四种碰撞类型模型，提出等待策略与更改路径规划策略并行的动态策略，在保证安全性避免碰撞的基础上，对比传统等待策略或单独采用更改路径规划策略具有更客观的作业效率，具有现实指导实践意义。