2025-01-22
分享到
本发明属于自动化仓储设备及其控制,具体涉及一种多四向穿梭车的路径规划方法。
1、四向穿梭车是一种具有环境信息感知、路径规划、行为控制和执行功能的仓储机器人。它通过使用多种不同类型的传感器来感知周围环境,包括识别障碍物、测量距离和位置等。根据环境信息,它可以进行路径规划,找到最优的搬运路径,并通过行为控制和执行功能将货物搬运到指定位置。
2、其中,路径规划技术是四向穿梭车研究领域的关键技术之一,是其完成任务的安全保障,是智能化程度的标志之一,同时也是人工智能与机器人学的一个重要的结合点和研究热点。自上世纪70年代起,路径规划问题就已经受到了国内外众多机构和学者的广泛关注,尤其是80年代以来,在人工智能、计算机科学、数学和机械工程等领域内的专家学者们的共同努力下,路经规划技术的研究在理论和实践方面都有了很大的提高。
3、近年来,四向穿梭车作为新兴的密集仓储设备,由于其具有自动化程度高、运载量大、能够适应高强度作业的特点,在物流业中有着庞大的市场与应用前景。但是随着物流业规模的持续扩大、包裹分拣任务的激增,参与工作的穿梭车数量也随之增加,有时需要几十台穿梭车同时工作。多四向穿梭车的路径规划是其在实际应用中的关键问题,不仅要考虑路径的效率,更要注重多四向穿梭车之间的碰撞和路径死锁问题。现有大部分研究主要考虑静态理想情况下的无碰撞路径规划,而针对动态环境提出的仿真算法(如蚁群算法、遗传算法等)计算复杂度高、收敛速度较慢;此外,现阶段大多数研究在解决问题过程中仅仅用任务的优先级来确定四向穿梭车的优先级,未考虑路径的死锁等其它因素,由此当四向穿梭车数量过多时,可能会造成路径堵塞。
1、本发明的目的是提供一种能够有效避免碰撞并减少路径死锁的多四向穿梭车的路径规划方法,其具体通过以下技术方案实现:
6、步骤4:求出每辆四向穿梭车分别和其它四向穿梭车形成的所有冲突库所序列并判断其类型;
7、步骤5:对路径死锁情况进行分类并检测所有路径中的死锁以及其类型,如果九游体育科技存在死锁,则进行步骤6,否则进行步骤7;
9、步骤7:综合考虑四向穿梭车的任务、载货、路径死锁情况,对所有四向穿梭车进行优先级排序;
10、步骤8:采用轮询方法在每轮申请中,为所有四向穿梭车动态申请若干数量的库所序列并根据步骤7中得到的优先级对申请进行处理,计算出每辆四向穿梭车可占用库所序列并结合着色petri网模型中变迁的使能条件,得到每辆穿梭车无碰撞路径,然后每隔一段时间进行下一轮,重复此步骤。
11、作为优选,步骤1中拓扑地图用三元组r,s,a描述,r和s为地图中的节点集合,各节点对应于实际环境中的标志物(如二维码),其中r中的节点表示站点(如工作站、充电站),s中的节点表示道路点,a为任意两个相邻节点间的有向弧(表示四向穿梭车可行驶的道路)集合;
12、所述步骤2中用八元组∑=p,t,f,k,w,m,d,c表示着色petri网模型;其中∑中的p={p0,p1,...,pn}为库所的集合,每个库所与拓扑地图中的每个节点一一对应;∑中的t={t0,t1,...,tm}为变迁的集合;∑中的f为连接库所与变迁的有向弧的集合,一个变迁及一对连接库所和变迁的有向弧表示拓扑地图中的有向弧;∑中的k为容量函数,代表库所和其托肯(库所中的资源,用来表示四向穿梭车)容量的映射函数,∑中每个库所的容量均为1,即k=[1],代表每个节点只能够容纳一辆四向穿梭车;∑中的w为权函数,代表有向弧与其权值的映射函数,∑中每条弧九游体育科技的权值为1,即w=[1],一次变迁的激发将使得一辆四向穿梭车从输入库所运动至输出库所;∑中的m为标识,表示各托肯分别在哪个库所中;∑中的d={d0,d1,...,dn},为颜色集,代表四向穿梭车集合,每辆四向穿梭车用唯一的颜色表示,将颜色为d的托肯简称为托肯d;∑中的c为着色映射,如果一个库所准许某辆四向穿梭车驶入,则对应库所和变迁的着色映射包含该四向穿梭车的颜色。
14、步骤3.1:定义库所的坐标pos=(x,y),{pos1,pos2,...,posn}表示着色petri网模型∑中的所有库所的坐标;定义每个变迁对应的实际路段的长度len,{len1,len2,...,lenm}表示着色petri网模型∑中所有变迁对应的实际路段的长度;
15、步骤3.2:定义a*算法的估价函数f(p)=g(p)+h(p),包括以下步骤:
16、步骤3.2.1:定义f(p)为从起始库所ps出发,经过库所p,最终到达终点库所pe的总代价;
19、其中g1(p)为路径长度,每次从父库所p0沿着变迁搜索下一个库所时,只需增加该变迁对应路径的长度,g1(p)=g1(p0)+len(tp0,p),起始库所ps处的函数值g1(ps)=0;
20、g2(p)考虑路径拥堵程度,库所p处的拥堵程度可以通过其它托肯路径库所序列中包含库所p的托肯的总数nc来衡量,g2(p)=g2(p0)+nc,起始库所ps处的函数值等于g2(ps)=0;
21、g3(p)考虑穿梭车转弯的影响,用z来表示转弯代价,如果到达库所p需要转弯则z=1,否则z=0,g3(p)=g3(p0)+z,起始库所ps处的函数值等于g3(ps)=0;根据实际运行环境,用α1、α2和α3对g1(p)、g2(p)和g3(p)进行归一化处理;
22、步骤3.3:用库所货物状态数组i=[i1,i2,...,in]表示着色petri网模型∑中每个库所的货物状态,若库所p有货物存放,则ip=1,反之ip=0;所述库所的货物信息通过仓库管理系统(wms)实时获取;
23、步骤3.4:定义两个辅助表open表和close表,并将起始库所添加到open表中;
24、步骤3.5:弹出open表中f(p)值最低的库所p作为当前库所,并将其加入close表中;
26、步骤3.6.1:对于库所p的任意一个后集库所pnext,如果当前托肯载货且pnext有货物存放即或者pnext已经在close表中,则省略pnext,否则执行步骤3.6.2;
27、步骤3.6.2:继续判断pnext是否在open表中,如果不在,则将pnext添加到open表中,把当前库所p作为pnext的父库所;如果pnext已经在open表中,且为从库所p到库所pnext的代价,则令且把pnext的父库所改成当前库所p,重新计算pnext的f(pnext)值并更新open表;
29、步骤3.7:重复步骤3.5和3.6,当终点库所pe添加进close表中或open表为空时,算法结束,从终点库所pe回溯,得到该托肯的路径库所序列。
31、步骤4.1:为各托肯的路径库所序列建立索引以表明库所序列中库所间的前后顺序,索引值小的为前,反之为后;
32、步骤4.2:求得颜色集d中任意的两个托肯di和dk之间形成的第一个冲突库所序列并判断其类型,包括以下子步骤:
33、步骤4.2.1:从托肯di的第一个路径库所p0开始,判断其是否在托肯dk的路径中,如果不在则继续判断后一个库所;如果在则将p0加入当前冲突库所序列ci→k中,并执行步骤4.2.2;
34、步骤4.2.2:继续判断托肯di路径中库所p0的后一个库所pnext,如果pnext不在dk路径中,则设置当前冲突库所序列ci→k为第一个冲突库所序列并定义ci→k为单冲突库所序列;如果pnext在dk路径中则执行步骤4.2.3;
35、步骤4.2.3:如果pnext为库所p0的后一个库所(前一个库所),则将pnext加入当前冲突库所序列ci→k中,继续判断后续库所并将其加入ci→k中直至库所不在dk路径中,定义ci→k为同向(相向)冲突库所序列并设为第一个冲突库所序列;
36、步骤4.3:求得颜色集d中任意的两个托肯di和dk之间形成的所有冲突库所序列:判断经过步骤4.2后托肯di的所有路径库所是否都判断完毕,如果是,则托肯di和托肯dk之间的所有冲突库所序列都已经求出,否则继续从最前的未判断过的库所开始执行步骤4.2,直至托肯di路径中的所有库所都判断完毕;
37、步骤4.4:重复步骤4.3,求得颜色集d中所有托肯两两之间形成的所有冲突库所序列。
39、步骤5.1:根据颜色集d中任意两托肯di和dk形成的相向冲突库所序列中的两端库所的类型将死锁分为以下两类:一端库所为托肯di的起始库所,另一端为托肯di的终点库所;一端库所为托肯di的起始库所(终点库所),另一端为托肯dk的起始库所(终点库所);
40、步骤5.2:根据颜色集d中任意两托肯di和dk形成的同向冲突库所序列中的两端库所的类型得到死锁类型为:一端库所为托肯di的起始库所,另一端为托肯di的终点库所;
41、步骤5.3:遍历步骤4中得到的颜色集d中所有托肯两两之间形成的所有冲突库所序列,检测是否出现上述三种死锁类型;如果有则进行步骤6,否则进行步骤7。
43、步骤6.1:确定需要重规划路径的托肯:优先重新规划路径上冲突库所序列数量多的托肯的路径,如果冲突库所序列数量一样则重新规划路径较长的托肯的路径;
44、步骤6.2:重规划托肯的路径:对需要重规划路径的托肯,获取在步骤4中的得到的此托肯和其他冲突托肯形成的所有冲突库所序列,再将冲突库所序列中的所有库所的输入变迁对应的实际长度len乘以二,然后再按照步骤3进行路径规划;
46、作为进一步优选,所述步骤7中托肯d的优先级计算方法为:pr(d)=
47、β1pr1(d)+β2pr2(d)+β3pr3(d)+β4pr4(d);其中pr1(d)考虑托肯执行任务的优先级,pr2(d)考虑托肯是否载货,pr3(d)考虑托肯路径的起点是否在和其它托肯形成的冲突库所序列中,如果在,提升此托肯优先级使其先通过冲突库所以避免路径死锁,pr3(d)=ns,ns为此托肯和其它托肯形成的所有冲突库所序列中包含此托肯起点的冲突库所序列的个数;pr4(d)考虑托肯路径的终点是否在和其它托肯形成的冲突库所序列中,如果在,降低此托肯优先级使其后通过冲突库所以避免路径死锁,pr4(d)=-ne,ne为此托肯和其它托肯形成的所有冲突库所序列中包含此托肯终点的冲突库所序列的个数;β1、β2、β3、β4为考虑实际情况时赋予的不同的权重系数。
49、步骤8.1:初始化时,先获得颜色集d中每一个托肯的当前库所,并将各个托肯当前库所的占用托肯设为该托肯;
50、步骤8.2:对于颜色集d中每个托肯,如果其对应的四向穿梭车还未到达该托肯的当前所在库所,则本轮不申请,等待下一轮开始时重复此步骤;如果已经到达,则执行步骤8.3;
51、步骤8.3:为托肯动态申请若干数量的库所序列:如果该托肯未与其它托肯形成冲突库所序列或者优先级低于其它冲突托肯,则申请该托肯路径库所序列中的在最后一个占用库所指向第一个未被占用过的库所方向上的所有未被占用过的库所;否则,求出在该托肯与其它更低优先级托肯形成的冲突集合中的且在该托肯路径上的最后一个库所pl,并申请该托肯路径中的库所pl以及pl前的所有未被占用过的库所,当pl已经被该托肯成功申请到后,在后续申请中则申请该托肯路径中的在最后一个占用库所指向第一个未被占用过的库所方向上的所有未被占用过的库所;
52、步骤8.4:按照优先级由低到高的顺序对颜色集d中托肯申请的库所序列进行调整:对于每一个托肯,按照其路径经过库所的顺序依次检查各库所的申请托肯集合;如果此托肯路径上的某个库所p被多个托肯同时申请,则该托肯退出库所p及库所p后的该托肯路径上的所有库所申请;
53、步骤8.5:将成功申请到各库所的托肯设置为该库所的占用托肯,遍历所有着色petri网模型中的变迁,如果其中某变迁t的输入库所在某托肯d的路径上,且托肯d为变迁t输出库所的占用托肯,则将无碰撞激发矩阵u中的托肯d激发变迁t的激发条件u(d,t)设置为1,即允许托肯d激发变迁t;
54、步骤8.6:变迁在满足使能条件(输入库所的托肯数量大于等于变迁输入弧的权重,输出库所托肯数量加上变迁输出弧的权重小于等于输出库所的容量)和激发条件u(d,t)=1后,着色petri网模型开始运行,托肯就通过变迁到达下一库所,并继续运行下去,直至不满足上述条件;
55、步骤8.7:然后每隔一段时间开启新一轮“申请-占用”以及着色petri网模型的运行,即每隔一段时间重复步骤8.2、8.3、8.4、8.5和8.6,每两轮间的时间间隔依据实际环境而定;
56、步骤8.8:实际的四向穿梭车可以沿着对应的托肯经过的库所序列开始运行,且四向穿梭车每经过一个库所到达后一库所后,就会解除对应托肯对前一个库所的占用。
57、一种电子设备,包括处理器和存储器,所述存储器用于存储计算机可执行程序,当所述计算机可执行程序被所述处理器执行时,所述处理器执行上述任意一种多四向穿梭车的路径规划方法。
58、一种计算机可读存储介质,所述计算机可读存储介质存储有计算机可执行程序,所述计算机可执行程序被处理器执行时,实现上述任意一种多四向穿梭车的路径规划方法。
60、本发明提供了一种多四向穿梭车的路径规划方法,该方法建立了环境的着色petri网模型,采用了考虑货位状态和路径拥堵程度等因素的改进a*算法,检测路径中死锁并给出了出现死锁后的重规划方法,减少了运行中出现死锁的概率;提出了多维度的优先级策略,将着色petri网模型自身的特性和动态的“申请-占用”算法相结合以实现碰撞避免;本发明能适应实时动态条件下的多穿梭车路径规划,能避免碰撞并有效减小出现路径死锁情况的概率。