基于冲突预测的多自动导引小车避碰决策优化
2020-09-10曹小华
曹小华,朱 孟
(武汉理工大学 物流工程学院,湖北 武汉 430063)
0 引言
在“中国制造2025”大背景下,我国的工业水平不断发展,智能制造进程不断推进,柔性装配流水线和自动化立体仓库全面进入高速发展阶段。由于在成本、效率、灵活性、可靠性等指标上具有优势,自动导引小车(Automated Guided Vehicle,AGV)在工业中的作用日益突出。
然而,AGV在工业上的应用也面临着一些问题,其中一个关键问题就是多AGV的路径冲突[1-2]。路径冲突指同一时段多台AGV的行驶路线出现交叉或重叠,主要分为路口冲突、追赶冲突和相向冲突[3]。路径冲突一旦处理不当,就会出现AGV碰撞或死锁问题,严重影响多AGV系统的工作效率。近年来,多AGV系统的路径冲突已经成为AGV研究的重点[4]。面对多AGV系统可能出现的路径冲突情况,一般做法是应用数学规划方法为AGV在地图中提前规划好无冲突路径[4-7],这种路径规划方法是非实时的静态路径规划,AGV在行驶过程中并不总能在规划的时间到达指定位置,而且随着AGV数量的增加,多台AGV之间的运行路线必将出现交叉和重叠。为了避免AGV路径冲突,前人根据路网的实时状态动态调整AGV的路径[8-14],然而动态路径规划不但增加了运算量,而且当多台AGV聚集在某一区域执行任务时,部分AGV必须绕开这片区域来避免路径冲突,从而增加AGV的额外运行时间,除此之外,在高密集型多AGV系统中可能会出现无法搜索到无冲突路径的情况。
针对上述现状,为了减少路径规划的计算量,本文采用非实时的静态路径规划算法,并通过冲突预测和避碰决策加以改进,AGV的最优路径在任务发布时就规划完毕且不再更改,面对路径冲突时将会采用停车或绕道的避碰策略来解除路径冲突。本文运用图论知识构建多AGV系统的工作地图,并基于顶点属性预测路径冲突。考虑到执行避碰决策对系统全局状态的影响,采用粒子群优化(Particle Swarm Optimization,PSO)算法优化避碰决策,并对PSO算法进行改进来改善优化效果。最后在VS2012平台上搭建上位机系统进行实验验证,结果表明改进的PSO算法具有较优的性能。
1 路径冲突分析与预测
在路径冲突问题上,相比于传统的重规划无冲突路径,文本所提方法注重已知路径下的避碰决策优化,即在路径冲突时不进行二次路径规划。在多路径类型的工作环境下,本文提出结合顶点属性和AGV位姿信息的冲突预测方法,通过预测多AGV系统未来的路径冲突状态来实现避碰决策的全局优化。
在本文研究的港口、物流仓储等环境下的多AGV系统中,AGV沿固定车道行驶,将车道的交叉点和卸货点作为图的顶点,车道作为连接两相邻顶点的边。AGV行驶的车道分为单向单车道、双向单车道、双向双车道3类。因为单向单车道和双向双车道可以看作为双向单车道的一种特殊情况,所以在处理路径冲突情况时只需要制定AGV在双向单车道上的行驶规则和避碰规则,即可解决多AGV系统中的路径冲突。
针对上述情况,本文提出一种基于图论的冲突预测方法,预测过程包括基于顶点属性快速搜索阶段、结合AGV位姿预测冲突阶段两个阶段。首先,基于图论的基本原理将某一时刻向某个顶点行驶的总AGV数量作为顶点的一个属性。显然,若某一时刻朝向某顶点的AGV数量大于等于2,则在该顶点处可能发生冲突,根据这一特点可以快速搜索到可能发生冲突的顶点,避免预测过程中的重复计算。然后,根据各个AGV的位姿信息进一步确定可能发生冲突的AGV。
(1)基于顶点属性的快速搜索阶段
建立二维数组M[A][B]表示顶点与AGV的关系。其中A为AGV的总数量,B为地图中顶点的总数量,M[i][j]=k表示当前时刻下j号顶点是i号AGV的第k个目标顶点。在冲突顶点的搜索过程中需要遍历数组M,将当前时刻具有相同目标顶点的AGV存储到一个一维数组中,表示可能存在冲突的顶点集合。搜索算法的伪代码如下:
算法1路径冲突顶点搜索算法伪代码。
1 /* 采用顶点属性法搜索冲突顶点*/
2 建立顶点属性矩阵M[A][B]
3 建立顶点冲突数组Conflict[B]
3 for b=0, b
4 Conflict[b]=0;