智能化仓库的AGV路径规划与紧急避障系统

孙兆臣,孙晓琴,杨文

智能化仓库的AGV路径规划与紧急避障系统

孙兆臣,孙晓琴,杨文

云南电网有限责任公司大理供电局, 云南 大理 671000

针对智能化仓库复杂的物流环境，对AGV运作要求越来愈高，本文给出考虑任务优先级的多AGV系统路径规划算法，并基于仓库复杂环境下AGV作业方式提出动态避障策略。以二维空间建立多AGV运作拓扑地图，采用改进A*算法求解单AGV最优路径，并应用Logistic函数描述多AGV系统路径使用频次的负载因子，减少多AGV系统阻塞路段以提高系统运作效率；同时提出两项同步并行避碰机制以解决多AGV运作环境下存在的四种碰撞类型，实验验证方案可行。

智能化仓库; 多AGV系统; 路径规划; 避障策略

近年来，随着物流业的发展，普遍对物流的时效性和准确性提出越来越高的严苛要求。为缓解物流行业高成本和低时效问题，智能化仓库应运而生。自动化导引车（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运作环境下由于路径冲突、节点等待影响运作效率的问题。

1 问题描述

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

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

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

图2 逻辑框架图

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

2 多AGV任务分配与路径规划

2.1 AGV任务执行优先级

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

图3 AGV任务执行优先级

2.2 多AGV路径规划

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

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

基于时间窗的多AGV路径规划在路径规划问题中，A*启发式算法描述为：()=()+() (3)

式中，()：起始节点经过节点到目标节点的距离代价评估，()描述起始节点行驶至目前节点的实际距离；()描述目前节点行驶至目标节点的距离代价评估。算法思想：AGV从起始节点起算法不断搜索当前节点至目标节点的最小距离()min，以此选择AGV小车路径的下个节点，已达到求解目标函数()min。多AGV系统在运行过程中，此时需对A*算法进行改进，引入不确定时间t改进A*算法：

(,t)=(,t)+(,t) (4)

式中：(,t)描述起始节点到节点的实际时间；(,t)描述从节点到目标节点的时间预估。

定义AGV起始节点、当前节点、目标节点坐标分别为(s,s)，(n,n)，(e,e)。当AGV节点出发，此时(,t)=0，相邻,两节点时间代价估计：(w())，则当前任一特征节点到目标节点可描述为[8]：

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

(,t)=(,t)+(w(t+))++(,t)=(,t)+(w(t))+(,t) (6)

A*算法维护两个列表：表OpenList和CloseList，算法索引过程：

（1）起始节点处(,t)=0，并记录AGV起始节点t，此时(,t)=0，将特征节点添加进CloseList；

（2）节点可达的特征节点加入OpenList中，将起始节点从OpenList中删去，加入到CloseList。

（3）将OpenList表中各特征节点中(,t)取最小值加入到CloseList[8]；

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

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

2.3 算例实施

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

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

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

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

表1 任务A和B单独路径规划

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

表2 任务A和B组合路径规划

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

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

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

图6 有无Logistic函数对比图

图7 AGV碰撞类型

3 多AGV避碰策略

3.1 冲突检测模型

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

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

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

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

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

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

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

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

3.2 并行避碰策略

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

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

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

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

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

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

3.3 避碰策略算例

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

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

图8 多AGV路径规划简图

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

表3 任务A和B组合路径规划

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

4 结论

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

[1] 房殿军,周涛.自动化立体仓库中智能AGV群体的静态路径规划与动态避障决策研究[J].物流技术,2017(6):177-185

[2] 徐镇华,马殷元.基于时间窗的改进两阶段AGV路径规划研究[J].测控技术,2018,37(6):145-149,154

[3] 廉胤东,谢巍.基于视觉引导多AGV系统的改进A*路径规划算法研究[J/OL].控制与决策.https://doi.org/10.13195/j.kzyjc.2019.1670

[4] 霍凯歌,张亚琦,胡志华.自动化集装箱码头多载AGV调度问题研究[J].大连理工大学学报,2016,56(3):244-251

[5] Singh Y, Sharma S, Sutton R,. A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents [J]. Ocean Engineering, 2018, 169:187-201

[6] 泰应鹏,邢科新,林叶贵,等.多AGV路径规划方法研究[J].计算机科学,2017,44(11A):84-87

[7] 李伟光,苏霞.基于改进A*算法的AGV路径规划[J].现代制造工程2015(10):33-36

[8] 张政.仓储系统AGV路径规划研究[D].北京:北京化工大学,2018

[9] 李婷.自动化仓库系统多AGV路径规划和避碰策略研究[D].哈尔滨:哈尔滨工业大学,2018

[10] Gao X, Jia Q, Sun H,. Research on Path Planning for 7-DOF Space Manipulator to Avoid Obstacle Based on A* Algorithm [J]. Sensor Letters, 2011,9(4):1515-1519

[11] Yuan RP, Dong TT, Li JT. Research on the Collision-Free Path Planning of Multi-AGVs System Based on Improved A-STAR Algorithm [J]. American Journal of Operations Research, 2016,6:442-449

[12] Liu CB, Tan J, Zhao HSPath Planning and Intelligent Scheduling of Multi-AGV Systems in Workshop [C]. Dalian China: Proceedings of the 36th Chinese Control Conference, 2017

AGV Path Planning and Emergency Obstacle Avoidance System in Intelligent Warehouse

SUN Zhao-chen, SUN Xiao-qin, YANG Wen

671000,

In view of the complex logistics environment of intelligent warehouse, higher requirements are placed on the operation of AGV. In this paper, the path-planning algorithm of multiple AGV systems considering task priority is given, and a dynamic obstacle avoidance strategy is proposed based on the AGV operation mode in the complex warehouse environment. The multi-AGV operation topology map is built in two-dimensional space, the single AGV optimal path is solved by improved A*algorithm, and the load factor of multi AGV system path usage frequency is described by logistic function to reduce the blocking road section of multi AGV system and improve the system operation efficiency. A parallel collision avoidance mechanism is proposed to solve the four collision types existing in the multi-AGV operating environment. The experimental verification scheme is feasible

intelligent warehouse; multi-AGV system; path planning; obstacle avoidance strategy

TH692.3

A

1000-2324(2021)03-0483-06

2020-05-27

2020-06-07

南方电网公司科技资助项目(YNKJXM20180007)

孙兆臣(1982-),男,本科,工程师,主要从事智能仓库建设. E-mail:sunzhaochen@163.com