1.一种考虑冲突规避的多AGV路径规划方法,其特征在于,包括:基于柔性工厂布局以及工件加工过程的多AGV任务分配、工序与机床分配问题,构建以最短完工时间为目标的调度模型;
对各加工工件的工序和机床进行匹配,并对工序和AGV进行编码,按照工序顺序,将工件一一分配给对应的机床和AGV,得到各AGV的任务列表;
基于所述AGV任务列表,采用A*算法分别对各AGV单独的路径进行规划,寻找各AGV规划方案的冲突并进行逐个规避,得到各AGV的初始路径种群;
以调度模型的完工时间作为适应度,采用遗传算法并引入增强精英策略,对初始路径种群进行求解,得到最短完工时间下的最优路径方案;
AGV规划方案的冲突规避包括:
占位冲突规避:若两辆AGV在同一时刻占据了同一位置,此时,A*算法判定为发生占位冲突,对其中一辆发生冲突的AGV设置限制,使其在每一次搜索临近点时都进行冲突检测,排除掉与限制条件时间位置相同的点,得到新路径;
若两个AGV路线发生重叠,冲突在重叠的每一个格栅都发生一次,A*算法只记录第一个位置重叠发生的时间和位置坐标,并解决冲突;
为规避AGV装载或卸货时,在终点位置发生冲突,将接件和送件的目的地区别设置,同时将机床临近不同的两个点规定为接件区和送件区;
边线冲突规避:若两辆AGV在某个时刻发生位置坐标交换,A*算法判定发生边线冲突,此时记录冲突的时刻和两辆AGV冲突前各自的位置坐标(t,L1,L2),并在检测到冲突后对其中一辆AGV施加限制,防止路线中出现t时刻在位置L1且t+1时刻向L2行驶的情况;
多车、多类型冲突规避:若发生两个及以上冲突同时发生的情况,A*算法任选两辆AGV解决其冲突;
机器占用和AGV等待冲突规避:在每个任务的送件过程结束时,判断上一工件的加工是否结束,如果没有结束,需要让AGV等待至加工结束;AGV等待的时间等于上一工件加工时间减去路上消耗的时间;若等待时间大于零,则要在下一次规划的路径前面插入等待时间。
2.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法,其特征在于,所述调度模型的建立基于以下假设:假设一:AGV在没有分配到任务时停在AGV各自的起始位置;
假设二:地图格栅由正方形小网格组成,机床的形状近似为正方形或者长方形的网格矩阵;
假设三:AGV的车身形状近似为一个半径为r的圆形,其中r小于格栅图网格边长,且大于边长的一半;
假设四:两辆AGV不能同时处在同一格栅内,也不能在处于相邻格栅的时候交换位置,否则都视为AGV发生碰撞;
假设五:AGV装载和卸载工件的时间记为一个单位时间,与AGV驶过一个网格用时相同;
假设六:AGV处在机床的装卸点时,不视为与机床碰撞;
假设七:每辆AGV一次只能装载一个工件;
假设八:AGV的运行速度是匀速的,是作为条件预设的;
假设九:不考虑AGV和机床的故障情况,二者都可持续正常工作;
假设十:AGV将工件运送到下一个机床之前,需要判断上一个工序是否加工完成,以及下一机床是否正在加工工件。
3.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法,其特征在于,所述调度模型的数学模型为:F=min(MS) (1);
MS=max(Ti‑T0) (2);
其中,公式(1)为目标函数;公式(2)定义完工时间为最后一辆AGV停止运行的时刻减去初始时刻;公式(3)‑(4)为限制条件,具体表示位置冲突和边线冲突两种情况都不允许发生;公式(5)表示机床同时只加工一个工件;公式(6)表示AGV一次只承载一个工件;公式(7)表示对AGV装载工件的时间约束;
MS表示完工时间;Ti表示第i辆AGV运行结束时刻;T0表示第一辆AGV起始时刻;Pi,t表示第i辆AGV在t时刻的位置;i,j表示AGV的编号;A表示AGV的编号集合;x,y表示工件的编号;
x x x,dr
Mm表示第m台机床在加工工件x的标志;Vi表示第i辆AGV在运输工件x的标志;ti 表示第ix x,pk辆AGV卸载工件x的时刻;tm表示第m台机床加工工件x花费的时间;tj 表示第j辆AGV装载工件x的时刻。
4.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法,其特征在于,AGV的任务列表的确定过程包括:编码前操作:编码前对机床和各工件的工序进行匹配;
编码:选用两组染色体作为最初种群,分别为工序染色体和AGV染色体;对于工序染色体,生成打乱顺序的公差为1的正整数数列,正整数表示工件编号,每个编号出现的次数与工序数相同,出现第几次则代表第几道工序;对于AGV染色体,正整数编码代表AGV编号;
解码:仿真染色体编码方案,计算完工时间。
5.根据权利要求4所述的一种考虑冲突规避的多AGV路径规划方法,其特征在于,编码前操作,用两个机床的曼哈顿距离除以AGV速度得到的行驶时间近似代表运送时间,将该时间与加工时间的和作为寻找下一个最佳机床的评判标准,寻优过程为:当 时,
若[dmanh(m,n)]min=dmanh(m,p),p∈J;
则
式中, 表示第m台机床正在加工工件x, 表示此时第m台机床没有对工件X进行加工,dmanh(m,n)表示机床m到机床n的曼哈顿距离,pm,x代表机床m的x轴坐标,J表示机床集合。
6.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法,其特征在于,AGV规划方案的冲突规避还包括:算法死锁的预防:当发生当前AGV路径被其他AGV封死、互相闪避和两AGV目的地相同的情况时,则判定为发生算法死锁,此时,将实际完工时间超过舍弃阈值的方案舍弃;舍弃阈值设置为:MSlim=3×MSavg,其中,MSlim为舍弃阈值,MSavg为第一代染色体完工时间的算数平均值。
7.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法,其特征在于,采用A*算法对各AGV进行路径规划时,还包括:路径规划时刻的统一:
每次进行路径规划时,将各AGV的起始时间统一,找到路线耗时最短的AGV,记录该路线长度为lmin,在其余AGV路线中找到一点使该点与起点之间的距离等于lmin,将该点命名为切割点并将路线在该点进行切割;此时只有切割前路线最短的AGV抵达终点,需要将任务列表的下一目的地传入;其余AGV的起点更新为切割点;
若有AGV返回仓库后,进入等待状态,在该已返回仓库的AGV路径中添加一段等待时间,随着时间的增加保持该AGV位置不变;等待时间的选取范围为:tw≥1.5×Lmap,其中,Lmap为地图的长。
8.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法,其特征在于,采用遗传算法并引入增强精英策略,对初始路径种群进行求解的过程包括:进化:以完工时间为适应度,在经典遗传算法的基础上,增加精英保留的过程,根据适应度从高到低将两代染色体排序,选择适应度相对高的前半部分保留进入下一代;
重复进化过程,直至达到预设的迭代次数,得到最小适应度;
输出最小适应度下的最优方案及最短完工时间。