一种考虑路径规划和扰动响应的车间集成动态调度方法

1.本发明属于车间生产调度应用领域，尤其涉及一种考虑路径规划和扰动响应的车间集成动态调度方法。


背景技术：

2.在使用多台agv送料的柔性生产车间中，容易产生agv间的冲突问题，同时也容易发生插单、设备故障等动态突发事件，这些都会打乱原有的调度方案，甚至影响整个制造系统的正常运行。因此，在制定调度方案时需要同时考虑agv的路径规划与冲突解决、动态扰动事件响应策略，进行多机床与多agv的动态集成调度，其调度结果也更贴合生产实际。
3.传统的柔性生产车间中机床与agv的集成调度主要是一种带agv运输时间的机床与agv静态集成调度问题，所集成的agv运输时间是静态环境与固定单一路径下的最短时间，没有考虑agv的路径选择、冲突解决以及系统中的紧急插单、设备故障等动态事件干扰问题。目前使用的方法主要有：智能优化算法与仿真方法。例如，saidi等在建立集成调度模型时考虑agv无冲突路径选择，提出一种两阶段蚁群算法求解作业车间机床与agv集成调度问题，其中第一阶段对运输任务分配agv，第二阶段为agv选择无冲突路径，并且研究了agv数量对最大完工时间的影响，但他们并未考虑车间中工件的多台可选加工机床情况，即每道工序的加工机床都是唯一的。贺长征等提出基于时间窗和dijkstra算法的混合遗传算法，为了将机床和agv调度集成考虑，设计了三链式编码结构及agv编码链的交叉、变异算子，同时在遗传算法的解码操作中将dijkstra算法与时间窗原理相结合，以精确地为任务小车规划出一条无碰撞无冲突的最短路径，但在agv路径规划中未考虑小车静止时的占用冲突问题。邓希等提出了基于时间表和a*(a-star)算法的混合遗传算法，首先采用三段式编码结构得到机床与agv的调度结果，其次由包含冲突解决策略的a*算法得到agv的路径规划结果，并将此结果集成至解码阶段最终得到每道工序的加工与运输的开始与结束时间，形成最终的调度方案。
4.仿真方法包括离散事件建模与仿真dems(discrete event modeling and simulation)、基于agent的建模与仿真abms(agent based modeling and simulation)。dems将真实系统抽象为系列事件，通过控制事件的发生顺序驱动仿真模型，由于其建模过程的快速性、准确性，已有许多学者使用该方法求解车间调度问题。例如，高珂婷针对混合流水车间调度问题，采用dems还原车间运行过程，并结合遗传算法优化了车间中的机床调度方案，缩小了系统运行时间。多agent技术是从人工智能领域发展出来的新方法，使用abms能良好地反映车间中的智能行为，abms被认为是最具仿真潜力、应用前景和实用价值的方法，在柔性作业车间集成调度问题上已得到良好应用。如komma等将柔性制造系统中的机床和agv调度问题制定为多agent系统，从而基于java智能体开发框架(java agent development framework,jade)实现了基于agent的车间仿真。erol等针对制造系统中的机床和agv调度问题提出了一种由管理agent、agv agent、任务agent和机床agent组成的多agent方法，这些agent在实时环境下工作，并利用彼此间的谈判机制生成可行时间表，但所
研究的机床不具备柔性。采用单一仿真方法虽能解决生产系统中的部分问题，但不能完全反映系统的所有特性，将dems、abms、sd中的两种及以上方法进行混合仿真，则能弥补单一仿真方法的不足，更完整地表述制造系统的特性和本质。rodrigue等则将dems结合abms的混合仿真方法应用于柔性作业车间中的生产调度问题，实现了工序任务在机床上的分配与排序，但并未考虑agv调度问题的影响。
5.综上，相关学者求解问题时存在的不足包括：(1)多数只解决了机床选择、agv选择以及工序任务在机床与agv上的排序问题中的部分问题，而考虑agv路径规划的集成调度优化问题的研究还较少，当实际工厂中存在多辆agv时，路径选择与冲突问题难以避免，不同路径选择以及冲突解决策略必然会造成不同的运输时间，从而影响调度结果。(2)大部分研究中很少考虑制造系统中插单、设备故障等动态突发事件的影响，系统中其他动态事件的产生也会扰乱原有生产调度计划。(3)单一的仿真方法不足以表述复杂的柔性生产车间agv与机床的运行过程，需要采用多种仿真的混合表述其运行本质。目前混合仿真在这一问题的研究还远不足。
6.为此，从实际情况考虑，柔性生产车间的生产调度更迫切需要考虑多agv无碰路径规划以及动态扰动事件响应的agv与机床集成调度方法。


技术实现要素：

7.当实际工厂中存在多辆agv时，路径选择与冲突问题难以避免，不同路径选择以及冲突解决策略必然会造成不同的运输时间，从而影响调度结果，同时，系统中其他动态事件的产生也会扰乱原有调度计划。为此，本发明提供一种考虑路径规划和扰动响应的车间集成动态调度方法。
8.本发明的一种考虑路径规划和扰动响应的车间集成动态调度方法，具体为：
9.a、基于agv agent与节点agent信息交互与决策的无碰路径规划。
10.当agv agent任务缓冲池中存在待执行搬运任务时，该任务被提交至路径规划模块，对比agv与搬运任务的当前节点位置信息后，执行路径规划，即在进入节点agent监测范围时，通过调用节点agent接口交互信息，初步决策出agv的下一行驶节点，并对其进行相向冲突与同一节点争夺冲突检测与解决，最终确定出一个无碰且距离最短的节点作为实际的下一行驶节点，agv向下一行驶节点行驶，并在行驶过程中进行追赶冲突检测与解决，重复以上过程，直至到达目标节点。
11.(1)基于节点agent与agv agent的交互作用规划agv的最短无碰路径。
12.1)节点拥挤度计算：
13.将系统中的每辆agv视为一个蚂蚁agent，携带一定的信息素λ进入路网；对agv的实时控制采用实时全局更新策略，根据每一时刻运输路网内所有agv的位置更新各节点的拥挤度；在t时刻，运输路网内任意节点(i,j)处的拥挤度如下：
[0014][0015]
式中，k为t时刻运输路网内节点到达agv集中的agv数量；m为t时刻运输路网内节点预到达agv集中的agv数量；n为t时刻运输路网内节点出发agv集中的agv数量；
分别为t时刻到达agv集中的第k辆、预到达agv集中的第m辆、出发agv集中的第n辆agv与节点间的直线距离；α、β、ε为重要程度系数，且α＞β＞ε。
[0016]
2)下一行驶节点选择：
[0017]
当agv到达新的节点位置(i,j)时，需要从众多节点中选择出下一行驶节点，反复选择，不断更新下一行驶节点直至到达目标节点位置，路径规划结束；设在节点(i,j)的下一行驶节点的集合为(i',j')＝{(i',j')|i'≠iorj'≠j}，其中表示第k辆agv；节点(i',j')处的拥挤度越高，agv在此处发生冲突与碰撞的可能性越大，需要规避过于拥挤的节点，因此，按照节点状况，可进一步从(i',j')中划分出发生碰撞可能性较低的节点形成的可行驶节点集合，记为allowedk；若说明没有合适的可行驶节点，停车等待；若则从中选择下一行驶节点。
[0018]
引入拥挤度阈值q划分allowedk，若τ
(i',j')
(t)＜q，则以(i',j')为下一行驶节点发生碰撞的可能性较小，不影响agv系统的正常运行，(i',j')∈allowedk；若τ
(i',j')
(t)≥q，则以(i',j')为下一行驶节点发生碰撞的可能性较大，会影响系统的正常运行，
[0019]
从allowedk中确定出的下一行驶节点需要满足发生碰撞可能性最小且路径最短两个条件，分别由待选节点的吸引程度和距离启发函数限制，吸引度即拥挤度阈值q与t时刻节点(i',j')处拥挤度τ
(i',j')
(t)的差值，吸引度计算公式如下：
[0020][0021]
路径最短需保证下一节点(i',j')与agv当前所在节点(i,j)以及目标点(e
x
,ey)两类距离的最短；因此，建立两类距离启发函数和分别表示agv当前所在节点(i,j)与下一节点(i',j')间的能见度和下一节点(i',j')与目标点(e
x
,ey)间的能见度，两类距离启发函数计算公式如下：
[0022][0023][0024]
故agv向可行驶节点集合中的各节点转移的转移概率为：
[0025][0026]
其中，σ、δ、γ为吸引度与两类能见度的重要程度系数。
[0027]
最终，选择节点转移概率最大的节点作为agv的下一行驶节点。
[0028]
(2)行驶过程中进行冲突检测与解决。
[0029]
1)常见碰撞与冲突类型
[0030]
agv在实际运行中的碰撞或死锁情况分为以下三种类型：
[0031]
①
相向冲突：同一时段两辆及以上数量的agv从不同节点向同一路段相向而行或行至某一节点的agv的下一行驶路段存在相向行驶agv或停靠agv的状况。
[0032]
②
同一节点争夺冲突：两辆及以上数量的agv从不同节点、路段上出发或在某一节点位置争夺同一节点的行驶权情况。
[0033]
③
追赶冲突：某一路段上同向行驶的两辆agv后者速度大于前者，或前者停在后者的必经之路上导致的同向追尾情况。
[0034]
2)冲突检测机制
[0035]
agv之间的冲突检测是通过节点agent与agv agent间的信息交互实现的，针对不同的冲突类型，设置不同的检测方法如下：
[0036]
①
相向冲突：agv在进入某一节点监测范围时，相应的agv agent由路径规划模块中的下一行驶节点决策子模块初步决策出自身的下一行驶节点，并将其提交至此刻到达的节点agent；再由节点agent遍历其预到达小车集与到达小车集，搜索其中是否存在本节点与该agv下一步行驶节点间路段上的在行驶小车，若存在，则该车必定为相向冲突小车。
[0037]
②
同一节点争夺冲突：agv在进入某一节点监测范围时，相应的agv agent由相向冲突检测与解决子模块确保下一行驶节点无相向冲突后，进入同一节点争夺冲突检测与解决子模块，该模块将agv信息提交至下一行驶节点agent，通过该节点agent遍历其预到达小车集与到达小车集，搜索其中是否存在与本车争夺同一节点行驶权的冲突小车，存在依据由式(6)～(7)确定。
[0038][0039][0040]
式中，为正在做同一节点争夺冲突判断的agv行至下一行驶节点的预到达时间；为冲突小车行至下一行驶节点的预到达时间；r为节点的监测半径；vm为冲突小车的行驶速度；表示冲突小车此时占据冲突节点，表示冲突小车此时停车。
[0041]
③
追赶冲突：主通过agv agent自身的距离监测模块实现，实时监控同一路段上同向行驶两车间距离。
[0042]
3)冲突解决机制
[0043]
①
相向冲突解决
[0044]
a、从可行节点集合中剔除具有相向冲突的初步决策出的下一行驶节点，若剔除后该集合为空，进入步骤e，否则继续从集合中优选转移概率最高的节点作为新的下一行驶节点，进入步骤b。
[0045]
b、根据式(8)判断本车采取换路行驶策略较于原地等待策略的时间损失，若不存在时间损失，则直接以新决策出的行驶节点为下一行驶节点，执行步骤d判断，否则进入步骤c。
[0046]
[0047]
式中：ttn为本车从当前位置到达替换节点的时间；ntg为本车经替换节点到达目标节点的最短时间；tto为本车从当前位置到达冲突节点的时间；otg为本车由冲突节点到达目标节点的最短时间；wt为停车等待时间。
[0048]
c、换路行驶存在时间损失，根据agv当前所在节点路况考虑原地停车、换边停车或强制换路策略，不同策略对应的路况依据如下：
[0049]
原地停车：agv agent调用当前所在节点agent的冲突小车一步预测接口，由其中封装函数预测冲突小车到达本节点后的下一步行驶节点，获得预测结果后，该agv继续判断若预测节点不在本车当前所在路段方向，则判定冲突小车行驶至本节点后不会与本车相撞，实行原地停车等待策略。
[0050]
换边停车：若预测节点在本车当前所在路段方向，判定冲突小车到达本车所在节点后相撞，则agv agent与当前所在节点agent交互此刻节点附近是否存在空闲路段，若存在，agv行驶至空闲路段停车等待，即换边停车。
[0051]
强制换路：以上情况均不满足时，则agv必须换路，以步骤a中决策出的节点为下一行驶节点。
[0052]
d、若agv换路了，则需要对新节点所在路段继续进行节点相向冲突检测，若依旧存在冲突，重复步骤a～c，否则agv向新节点行驶。
[0053]
e、当前小车无路可换亦不可停车等待时，必定碰撞，此种情况需与冲突小车进行交互，使其倒退让路，由本车占据冲突路段的行使权。
[0054]
②
同一节点争夺冲突解决
[0055]
同一节点争夺冲突由agv agent中的同一节点争夺冲突检测与解决模块识别与解除，检测到该类冲突后，封装在该模块中的冲突解决策略主要通过比较本车与冲突车间的优先级实现，优先级高者获得冲突节点的行驶权，级别低的则换路，若不存在可换节点则停车等待。
[0056]
其中，优先级通过以下步骤确定：
[0057]
a、此刻或在上一行驶节点处具有相向冲突情况者，为避免与相向冲突车碰撞，应具有更高的优先级别。
[0058]
b、比较发生冲突的各辆agv当前所在节点的拥挤度，拥挤度高者赋予更高的优先级别，以使其尽快驶离所在节点，降低节点拥挤程度。
[0059]
c、若当前所在节点拥挤度相同，则比较冲突节点对哪辆agv的吸引程度更高，高者获得更高的优先级别。
[0060]
③
追赶冲突解决
[0061]
当agv agent的距离监测模块检测到两车间距离小于安全距离时，追赶车则自行停车等待，当前方车行驶至两车间距离为安全距离时，追赶车才继续行驶。
[0062]
b、考虑扰动事件制定响应策略形成混合仿真模型。
[0063]
这里的扰动事件包括紧急插单、agv故障和机床故障。
[0064]
(1)紧急插单
[0065]
当紧急订单到达时，系统agent根据订单信息生成对应工件agent与工序agent并将其状态登记为紧急，据此，工件agent由生产过程子模型中的“订单进入”对象进入生产系统时，紧急工件被识别并被赋予最高优先级，使其优先协商；进入“协商”的合同网协商阶段
时，紧急工序agent在招标时将标书标识为紧急状态，agv与机床agent据此在计算投标内容时，将缓冲池中的所有未执行任务滞后，以最早开始搬运时间投标，中标后将紧急任务插入缓冲池中所有非紧急任务前方，使其被优先执行。
[0066]
(2)agv故障
[0067]
agv故障时，对故障agv任务缓冲池中的所有任务进行重协商；此时缓冲池中的任务有两种状态：正在搬运与等待搬运，其中正在搬运又分为空载、负载两种情况；故障发生时，处于空载搬运与等待搬运状态的任务只需将对应工件agent从生产过程子模型中的“等待与执行运输”模块中释放至“协商”中重协商搬运agv与加工机床即可，工件位置未发生变化；负载搬运状态下由于工件正跟随agv在路网中移动，当agv故障时，被携带的工件则滞留在此刻离agv最近的节点位置处，重协商时则以工件实际滞留位置计算距离信息。
[0068]
无论缓冲池中任务处于何种状态，“等待与执行运输”模块将其释放后，都要流入“判断agv故障”对象中，由该模块对需要重协商的工件分流，需要重协商的工件被返回至“协商”中重协商，否则流入加工模块中加工；此外，在所有任务重协商开始前，需将故障agv任务缓冲池清空，同时还需将所有重协商工件的加工任务从其加工机床的任务缓冲池中删除，而后，故障agv再以预估故障结束时间参与竞标。
[0069]
(3)机床故障
[0070]
机床故障时的响应策略为对故障机床任务缓冲池中的所有待执行任务进行重协商；此时缓冲池中的任务有四种状态：正在加工、缓冲站中等待加工、正在搬运、等待搬运；正在加工的工件不作重协商处理，等待故障结束时继续加工；缓冲站中等待加工与等待搬运状态下的任务则需分别从生产过程子模型的“加工缓冲”与“等待与执行运输”模块释放至“协商”中重协商搬运agv与加工机床；正在搬运状态下的任务则只需为其重协商加工机床即可，获得新的加工机床位置后，由签约agv的路径规划模块直接更改目的地为新位置即可。
[0071]
从“加工缓冲”与“等待与执行运输”模块释放出的工件，分别流入“判断agv故障”、“判断机床故障”对象中，由该模块对需要重协商的工件分流，需要重协商的工件被返回至“协商”中重协商，否则流入加工模块继续加工；同样地，在所有重协商任务开始前，需将故障机床任务缓冲池中所有待执行任务清空，同时还需将所有处于等待搬运阶段的重协商工件的搬运任务从其搬运agv的任务缓冲池中删除；而后，故障机床以预估故障结束时间参与竞标，若存在正在加工工件，则以故障结束后该工件的预估结束加工时间参与竞标。
[0072]
本发明的有益技术效果为：
[0073]
本发明在设备故障时，在重协商响应策略下，系统完工时间与鲁棒性均得到了提升。紧急插单策略响应下，紧急工件的完工时间均提前了，且整个系统的鲁棒性波动很小，平均仅产生5％的波动，说明系统响应扰动能力良好，证明了本章扰动事件响应策略的有效性。
附图说明
[0074]
图1为本发明无碰路径规划执行流程图。
[0075]
图2为本发明常见冲突类型图示。
[0076]
图3为相向冲突解决策略图示。
[0077]
图4为本发明考虑扰动响应的集成调度混合仿真模型。
具体实施方式
[0078]
下面结合附图和具体实施例对本发明做进一步详细说明。
[0079]
本发明的一种考虑路径规划和扰动响应的车间集成动态调度方法，具体为：
[0080]
a、基于agv agent与节点agent信息交互与决策的无碰路径规划，具体流程图如图1所示。
[0081]
当agv agent任务缓冲池中存在待执行搬运任务时，该任务被提交至路径规划模块，对比agv与搬运任务的当前节点位置信息后，执行路径规划，即在进入节点agent监测范围时，通过调用节点agent接口交互信息，初步决策出agv的下一行驶节点，并对其进行相向冲突与同一节点争夺冲突检测与解决，最终确定出一个无碰且距离最短的节点作为实际的下一行驶节点，agv向下一行驶节点行驶，并在行驶过程中进行追赶冲突检测与解决，重复以上过程，直至到达目标节点。
[0082]
1、基于节点agent与agv agent的交互作用规划agv的最短无碰路径。
[0083]
(1)节点agent与agv agent路径规划功能详述
[0084]
规划agv的无碰路径时，主要依靠节点agent与agv agent的信息交互完成决策，两类agent实现路径规划功能的相应模块的具体功能详述如下：
[0085]
节点agent
[0086]
每个节点agent具备以下知识与功能：
[0087]
1)与路网中所有非相邻节点的距离知识。
[0088]
2)与路网中所有相邻节点的距离知识以及该相邻节点是否可行驶知识。
[0089]
3)具有三类agv集合，用于统计与查询该节点附近的agv信息。即，预到达agv集：保存下一行驶节点为该节点的agv信息；出发agv集：保存上一行驶节点为该节点的agv信息；到达agv集：保存此刻占据该节点的agv信息。
[0090]
4)获得自身拥挤度接口：可实时获得本节点的拥挤程度。
[0091]
5)冲突agv一步预测接口：预测存在冲突情况的agv到达本节点后的下一步行驶节点。
[0092]
6)监测半径：保证agv进入节点监测范围时就执行判断，从而避免agv在路径交叉的点位置上碰撞或停车而造成本节点的不可行驶情况。
[0093]
agv agent
[0094]
执行路径规划时，由agv agent中的路径规划模块实现agv的无碰路径规划，路径规划模块包含以下几个子模块：
[0095]
1)下一行驶节点决策模块：当agv进入节点监测范围时，与节点agent交互，初步决策出该agv的下一行驶节点。
[0096]
2)相向冲突检测与解决模块：将1)中初步得到的下一行驶节点与本车当前所在节点作为检测对象，判断两节点间路段是否存在与本车有相向冲突的agv，并给出解决方案。
[0097]
3)同一节点争夺冲突检测与解决模块：判断此刻是否存在其他agv与本车争夺同一节点的行驶权，并给出解决方案。
[0098]
4)距离监测模块：在agv行驶过程中监测与控制同向行驶agv间的距离。
[0099]
(2)基于节点拥挤度的无碰路径规划
[0100]
1)节点拥挤度计算：
[0101]
参照蚂蚁觅食思想，将系统中的每辆agv视为一个蚂蚁agent，携带一定的信息素λ进入路网。传统蚁群算法采用启发函数η
ij
＝1/d
ij
表示两点间的能见度，以此实现节点感知到的信息素浓度随着与agv间距离的增加而降低。基于此，兰培真等提出节点拥挤度概念，实现对agv的实时控制采用实时全局更新策略，根据每一时刻运输路网内所有agv的位置更新各节点的拥挤度；在t时刻，运输路网内任意节点(i,j)处的拥挤度如下：
[0102][0103]
实质上，并非路网中的所有agv都会对某一节点的拥挤度造成影响，并且不同agv相对节点的不同行驶状态对拥挤程度的影响是不同的。故本发明在计算拥挤度时，只考虑节点附近的agv(计算节点与每一个相邻节点所形成的路段上的agv视为附近agv)。由前文可知这些agv信息存储在节点agent的三类agv集合中，易知，三类agv集对应agv相对节点的三种行驶状态。其中到达agv集中的agv由于此刻占据节点或在节点监测范围内，对节点造成的拥挤度是最大的；其次，预到达agv集中的agv正在向节点逐步靠近，也会对节点的拥挤度做出贡献；出发agv集中的agv正在逐步远离节点，对节点的拥挤度影响最低。故本发明在兰培真的基础上改进拥挤度计算公式如下：
[0104][0105]
式中，k为t时刻运输路网内节点到达agv集中的agv数量；m为t时刻运输路网内节点预到达agv集中的agv数量；n为t时刻运输路网内节点出发agv集中的agv数量；分别为t时刻到达agv集中的第k辆、预到达agv集中的第m辆、出发agv集中的第n辆agv与节点间的直线距离；α、β、ε为重要程度系数，且α＞β＞ε。
[0106]
2)下一行驶节点选择：
[0107]
当agv到达新的节点位置(i,j)时，需要从众多节点中选择出下一行驶节点，反复选择，不断更新下一行驶节点直至到达目标节点位置，路径规划结束；设在节点(i,j)的下一行驶节点的集合为(i',j')＝{(i',j')|i'≠iorj'≠j}，其中表示第k辆agv；节点(i',j')处的拥挤度越高，agv在此处发生冲突与碰撞的可能性越大，需要规避过于拥挤的节点，因此，按照节点状况，可进一步从(i',j')中划分出发生碰撞可能性较低的节点形成的可行驶节点集合，记为allowedk；若说明没有合适的可行驶节点，停车等待；若则从中选择下一行驶节点。
[0108]
引入拥挤度阈值q划分allowedk，若τ
(i',j')
(t)＜q，则以(i',j')为下一行驶节点发生碰撞的可能性较小，不影响agv系统的正常运行，(i',j')∈allowedk；若τ
(i',j')
(t)≥q，则以(i',j')为下一行驶节点发生碰撞的可能性较大，会影响系统的正常运行，
[0109]
从allowedk中确定出的下一行驶节点需要满足发生碰撞可能性最小且路径最短两个条件，分别由待选节点的吸引程度和距离启发函数限制，吸引度即拥挤度阈值q与t时
刻节点(i',j')处拥挤度τ
(i',j')
(t)的差值，吸引度计算公式如下：
[0110][0111]
路径最短需保证下一节点(i',j')与agv当前所在节点(i,j)以及目标点(e
x
,ey)两类距离的最短；因此，建立两类距离启发函数和分别表示agv当前所在节点(i,j)与下一节点(i',j')间的能见度和下一节点(i',j')与目标点(e
x
,ey)间的能见度，两类距离启发函数计算公式如下：
[0112][0113][0114]
故agv向可行驶节点集合中的各节点转移的转移概率为：
[0115][0116]
其中，σ、δ、γ为吸引度与两类能见度的重要程度系数。
[0117]
最终，选择节点转移概率最大的节点作为agv的下一行驶节点。
[0118]
2、行驶过程中进行冲突检测与解决。
[0119]
多agv路径规划与冲突解决是一个极其复杂的问题，根据节点拥挤程度实现的路径规划，只能尽可能地避免agv行驶到过于拥挤的节点，进而避免该节点处潜在的碰撞、拥塞、死锁情况。在实际行驶过程中，仍有很大可能发生上述冲突，需要继续在行驶过程中进行冲突检测与解决。
[0120]
1)常见碰撞与冲突类型
[0121]
agv在实际运行中的碰撞或死锁情况分为以下三种类型：
[0122]
①
相向冲突：如图2(a)～(c)所示，同一时段两辆及以上数量的agv从不同节点向同一路段相向而行或行至某一节点的agv的下一行驶路段存在相向行驶agv或停靠agv的状况。这是最严重的冲突类型，难以直接通过减速、制动等简单措施避免。
[0123]
②
同一节点争夺冲突：如图2(d)～(f)所示，两辆及以上数量的agv从不同节点、路段上出发或在某一节点位置争夺同一节点的行驶权情况。
[0124]
③
追赶冲突：如图2(g)～(h)所示，某一路段上同向行驶的两辆agv后者速度大于前者，或前者停在后者的必经之路上导致的同向追尾情况。
[0125]
2)冲突检测机制
[0126]
agv之间的冲突检测是通过节点agent与agv agent间的信息交互实现的，针对不同的冲突类型，设置不同的检测方法如下：
[0127]
①
相向冲突：agv在进入某一节点监测范围时，相应的agv agent由路径规划模块中的下一行驶节点决策子模块初步决策出自身的下一行驶节点，并将其提交至此刻到达的节点agent；再由节点agent遍历其预到达小车集与到达小车集，搜索其中是否存在本节点与该agv下一步行驶节点间路段上的在行驶小车，若存在，则该车必定为相向冲突小车。
[0128]
②
同一节点争夺冲突：agv在进入某一节点监测范围时，相应的agv agent由相向冲突检测与解决子模块确保下一行驶节点无相向冲突后，进入同一节点争夺冲突检测与解决子模块，该模块将agv信息提交至下一行驶节点agent，通过该节点agent遍历其预到达小车集与到达小车集，搜索其中是否存在与本车争夺同一节点行驶权的冲突小车，存在依据由式(6)～(7)确定。其中式(6)针对图2中(e)、(f)情况，式(7)针对情况(g)。
[0129][0130][0131]
式中，为正在做同一节点争夺冲突判断的agv行至下一行驶节点的预到达时间；为冲突小车行至下一行驶节点的预到达时间；r为节点的监测半径；vm为冲突小车的行驶速度；表示冲突小车此时占据冲突节点，表示冲突小车此时停车。
[0132]
③
追赶冲突：主通过agv agent自身的距离监测模块实现，实时监控同一路段上同向行驶两车间距离。
[0133]
3)冲突解决机制
[0134]
①
相向冲突解决
[0135]
相向冲突情况复杂，当agv agent通过相向冲突检测与解决模块识别到该类冲突后，封装在该模块中的相向冲突解决策略通过以下步骤进行冲突解除：
[0136]
a、从可行节点集合中剔除具有相向冲突的初步决策出的下一行驶节点，若剔除后该集合为空，进入步骤e，否则继续从集合中优选转移概率最高的节点作为新的下一行驶节点，进入步骤b。
[0137]
b、根据式(8)判断本车采取换路行驶策略较于原地等待策略的时间损失，若不存在时间损失，则直接以新决策出的行驶节点为下一行驶节点，执行步骤d判断，否则进入步骤c。
[0138][0139]
式中：ttn为本车从当前位置到达替换节点的时间；ntg为本车经替换节点到达目标节点的最短时间；tto为本车从当前位置到达冲突节点的时间；otg为本车由冲突节点到达目标节点的最短时间；wt为停车等待时间。
[0140]
c、换路行驶存在时间损失，根据agv当前所在节点路况考虑原地停车、换边停车或强制换路策略，不同策略对应的路况依据如下：
[0141]
原地停车：agv agent调用当前所在节点agent的冲突小车一步预测接口，由其中封装函数预测冲突小车到达本节点后的下一步行驶节点，获得预测结果后，该agv继续判断若预测节点不在本车当前所在路段方向，则判定冲突小车行驶至本节点后不会与本车相撞，实行原地停车等待策略，如图3(a)所示。
[0142]
换边停车：若预测节点在本车当前所在路段方向，判定冲突小车到达本车所在节点后相撞，则agv agent与当前所在节点agent交互此刻节点附近是否存在空闲路段，若存
在，agv行驶至空闲路段停车等待，即换边停车，如图3(b)所示。
[0143]
强制换路：以上情况均不满足时，则agv必须换路，以步骤a中决策出的节点为下一行驶节点，如图3(c)所示。
[0144]
d、若agv换路了，则需要对新节点所在路段继续进行节点相向冲突检测，若依旧存在冲突，重复步骤a～c，否则agv向新节点行驶。
[0145]
e、当前小车无路可换亦不可停车等待时，必定碰撞，此种情况需与冲突小车进行交互，使其倒退让路，由本车占据冲突路段的行使权，如图3(d)所示。
[0146]
②
同一节点争夺冲突解决
[0147]
同一节点争夺冲突由agv agent中的同一节点争夺冲突检测与解决模块识别与解除，检测到该类冲突后，封装在该模块中的冲突解决策略主要通过比较本车与冲突车间的优先级实现，优先级高者获得冲突节点的行驶权，级别低的则换路，若不存在可换节点则停车等待。
[0148]
其中，优先级通过以下步骤确定：
[0149]
a、此刻或在上一行驶节点处具有相向冲突情况者，为避免与相向冲突车碰撞，应具有更高的优先级别。
[0150]
b、比较发生冲突的各辆agv当前所在节点的拥挤度，拥挤度高者赋予更高的优先级别，以使其尽快驶离所在节点，降低节点拥挤程度。
[0151]
c、若当前所在节点拥挤度相同，则比较冲突节点对哪辆agv的吸引程度更高，高者获得更高的优先级别。
[0152]
③
追赶冲突解决
[0153]
当agv agent的距离监测模块检测到两车间距离小于安全距离时，追赶车则自行停车等待，当前方车行驶至两车间距离为安全距离时，追赶车才继续行驶。
[0154]
b、考虑扰动事件制定响应策略形成混合仿真模型。
[0155]
生产系统中常见的扰动事件包括紧急插单、agv故障、机床故障、agv碰撞等，其中agv碰撞情况已在路径规划中提出解决方案，这里对前三种情况分别制定响应策略，所形成的混合仿真模型主要执行流程如图4所示。详述如下：
[0156]
(1)紧急插单
[0157]
当紧急订单到达时，系统agent根据订单信息生成对应工件agent与工序agent并将其状态登记为紧急，据此，工件agent由生产过程子模型中的“订单进入”对象进入生产系统时，紧急工件被识别并被赋予最高优先级，使其优先协商；进入“协商”的合同网协商阶段时，紧急工序agent在招标时将标书标识为紧急状态，agv与机床agent据此在计算投标内容时，将缓冲池中的所有未执行任务滞后，以最早开始搬运时间(即正在执行任务的结束执行时间)投标，中标后将紧急任务插入缓冲池中所有非紧急任务前方，使其被优先执行。
[0158]
(2)agv故障
[0159]
agv故障时，对故障agv任务缓冲池中的所有任务进行重协商；此时缓冲池中的任务有两种状态：正在搬运与等待搬运，其中正在搬运又分为空载、负载两种情况；故障发生时，处于空载搬运与等待搬运状态的任务只需将对应工件agent从生产过程子模型中的“等待与执行运输”模块中释放至“协商”中重协商搬运agv与加工机床即可，工件位置未发生变化；负载搬运状态下由于工件正跟随agv在路网中移动，当agv故障时，被携带的工件则滞留
在此刻离agv最近的节点位置处，重协商时则以工件实际滞留位置计算距离信息。
[0160]
无论缓冲池中任务处于何种状态，“等待与执行运输”模块将其释放后，都要流入“判断agv故障”对象中，由该模块对需要重协商的工件分流，需要重协商的工件被返回至“协商”中重协商，否则流入加工模块中加工；此外，在所有任务重协商开始前，需将故障agv任务缓冲池清空，同时还需将所有重协商工件的加工任务从其加工机床的任务缓冲池中删除，而后，故障agv再以预估故障结束时间参与竞标。
[0161]
(3)机床故障
[0162]
机床故障时的响应策略为对故障机床任务缓冲池中的所有待执行任务进行重协商；此时缓冲池中的任务有四种状态：正在加工、缓冲站中等待加工、正在搬运、等待搬运；正在加工的工件不作重协商处理，等待故障结束时继续加工；缓冲站中等待加工与等待搬运状态下的任务则需分别从生产过程子模型的“加工缓冲”与“等待与执行运输”模块释放至“协商”中重协商搬运agv与加工机床；正在搬运状态下的任务则只需为其重协商加工机床即可，获得新的加工机床位置后，由签约agv的路径规划模块直接更改目的地为新位置即可。
[0163]
从“加工缓冲”与“等待与执行运输”模块释放出的工件，分别流入“判断agv故障”、“判断机床故障”对象中，由该模块对需要重协商的工件分流，需要重协商的工件被返回至“协商”中重协商，否则流入加工模块继续加工；同样地，在所有重协商任务开始前，需将故障机床任务缓冲池中所有待执行任务清空，同时还需将所有处于等待搬运阶段的重协商工件的搬运任务从其搬运agv的任务缓冲池中删除；而后，故障机床以预估故障结束时间参与竞标，若存在正在加工工件，则以故障结束后该工件的预估结束加工时间参与竞标。
[0164]
实施例：
[0165]
为了验证考虑路径规划的集成调度方法动态处理干扰事件的可行性和有效性，将本章节对三种常见扰动事件的响应策略进行测试，并与无响应策略情况对比，对比指标包括能说明整体调度执行结果的完工时间、系统抗击扰动能力的鲁棒性、以及agv避碰情况的碰撞次数。仿真运行时，三种场景下的agv故障、机床故障均出现在仿真时间的第30s时刻，故障设备为a0、m3，故障持续时间为10s，紧急插单出现在第10s，插单工件为基准数据中的第一个工件。对比结果如表1所示，其中鲁棒性计算公式为：：
[0166][0167]
式中，rm越小表示鲁棒性越好，sr表示实际调度方案，s
p
表示初始调度方案；cmax表示调度方案的最大完工时间。
[0168]
表1不同场景下动态事件响应能力对比
[0169]
[0170][0171]
从表1可以看出，设备故障时，在重协商响应策略下，系统完工时间与鲁棒性均得到了提升。紧急插单情况有两类完工时间，括号里的是紧急工件的完工时间，另一个则是系统中最后一个工件的完工时间，紧急插单策略响应下，紧急工件的完工时间均提前了，且整个系统的鲁棒性波动很小，平均仅产生5％的波动，说明系统响应扰动能力良好，证明了本章扰动事件响应策略的有效性。
[0172]
本发明针对考虑agv路径规划的机床与agv动态集成调度问题，提出了一种融合路径规划与扰动响应策略的混合仿真模型求解方法。首先提出了一种基于agv agent与节点agent交互的多agv无碰路径规划方法，包括agv基于节点拥挤度的路径选择，agv冲突预测与避碰策略制定，其次进行了路径规划与扰动响应策略下的集成调度混合仿真模型，针对扰动事件包括紧急插单、agv故障、机床故障、agv碰撞等设计了重协商响应策略，实现了基于混合仿真模型，融入无碰路径规划和扰动响应策略的柔性生产车间机床与agv的动态集成调度系统。最后，通过算例对方法进行了仿真验证并与其他算法对比，对比结果说明了本发明方法的有效性与优越性。

技术特征：
1.一种考虑路径规划和扰动响应的车间集成动态调度方法，其特征在于，具体为：a、基于agv agent与节点agent信息交互与决策的无碰路径规划；当agv agent任务缓冲池中存在待执行搬运任务时，该任务被提交至路径规划模块，对比agv与搬运任务的当前节点位置信息后，执行路径规划，即在进入节点agent监测范围时，通过调用节点agent接口交互信息，初步决策出agv的下一行驶节点，并对其进行相向冲突与同一节点争夺冲突检测与解决，最终确定出一个无碰且距离最短的节点作为实际的下一行驶节点，agv向下一行驶节点行驶，并在行驶过程中进行追赶冲突检测与解决，重复以上过程，直至到达目标节点；(1)基于节点agent与agv agent的交互作用规划agv的最短无碰路径；1)节点拥挤度计算：将系统中的每辆agv视为一个蚂蚁agent，携带一定的信息素λ进入路网；对agv的实时控制采用实时全局更新策略，根据每一时刻运输路网内所有agv的位置更新各节点的拥挤度；在t时刻，运输路网内任意节点(i,j)处的拥挤度如下：式中，k为t时刻运输路网内节点到达agv集中的agv数量；m为t时刻运输路网内节点预到达agv集中的agv数量；n为t时刻运输路网内节点出发agv集中的agv数量；分别为t时刻到达agv集中的第k辆、预到达agv集中的第m辆、出发agv集中的第n辆agv与节点间的直线距离；α、β、ε为重要程度系数，且α＞β＞ε；2)下一行驶节点选择：当agv到达新的节点位置(i,j)时，需要从众多节点中选择出下一行驶节点，反复选择，不断更新下一行驶节点直至到达目标节点位置，路径规划结束；设在节点(i,j)的下一行驶节点的集合为(i',j')＝{(i',j')|i'≠i or j'≠j}，其中表示第k辆agv；节点(i',j')处的拥挤度越高，agv在此处发生冲突与碰撞的可能性越大，需要规避过于拥挤的节点，因此，按照节点状况，可进一步从(i',j')中划分出发生碰撞可能性较低的节点形成的可行驶节点集合，记为allowed
k
；若说明没有合适的可行驶节点，停车等待；若则从中选择下一行驶节点；引入拥挤度阈值q划分allowed
k
，若τ
(i',j')
(t)＜q，则以(i',j')为下一行驶节点发生碰撞的可能性较小，不影响agv系统的正常运行，(i',j')∈allowed
k
；若τ
(i',j')
(t)≥q，则以(i',j')为下一行驶节点发生碰撞的可能性较大，会影响系统的正常运行，从allowed
k
中确定出的下一行驶节点需要满足发生碰撞可能性最小且路径最短两个条件，分别由待选节点的吸引程度和距离启发函数限制，吸引度即拥挤度阈值q与t时刻节点(i',j')处拥挤度τ
(i',j')
(t)的差值，吸引度计算公式如下：路径最短需保证下一节点(i',j')与agv当前所在节点(i,j)以及目标点(e
x
,e
y
)两类距离的最短；因此，建立两类距离启发函数和分别表示agv当前所在节点(i,j)与下
一节点(i',j')间的能见度和下一节点(i',j')与目标点(e
x
,e
y
)间的能见度，两类距离启发函数计算公式如下：函数计算公式如下：故agv向可行驶节点集合中的各节点转移的转移概率为：其中，σ、δ、γ为吸引度与两类能见度的重要程度系数；最终，选择节点转移概率最大的节点作为agv的下一行驶节点；(2)行驶过程中进行冲突检测与解决；1)常见碰撞与冲突类型agv在实际运行中的碰撞或死锁情况分为以下三种类型：
①
相向冲突：同一时段两辆及以上数量的agv从不同节点向同一路段相向而行或行至某一节点的agv的下一行驶路段存在相向行驶agv或停靠agv的状况；
②
同一节点争夺冲突：两辆及以上数量的agv从不同节点、路段上出发或在某一节点位置争夺同一节点的行驶权情况；
③
追赶冲突：某一路段上同向行驶的两辆agv后者速度大于前者，或前者停在后者的必经之路上导致的同向追尾情况；2)冲突检测机制agv之间的冲突检测是通过节点agent与agv agent间的信息交互实现的，针对不同的冲突类型，设置不同的检测方法如下：
①
相向冲突：agv在进入某一节点监测范围时，相应的agv agent由路径规划模块中的下一行驶节点决策子模块初步决策出自身的下一行驶节点，并将其提交至此刻到达的节点agent；再由节点agent遍历其预到达小车集与到达小车集，搜索其中是否存在本节点与该agv下一步行驶节点间路段上的在行驶小车，若存在，则该车必定为相向冲突小车；
②
同一节点争夺冲突：agv在进入某一节点监测范围时，相应的agv agent由相向冲突检测与解决子模块确保下一行驶节点无相向冲突后，进入同一节点争夺冲突检测与解决子模块，该模块将agv信息提交至下一行驶节点agent，通过该节点agent遍历其预到达小车集与到达小车集，搜索其中是否存在与本车争夺同一节点行驶权的冲突小车，存在依据由式(6)～(7)确定；(6)～(7)确定；
式中，为正在做同一节点争夺冲突判断的agv行至下一行驶节点的预到达时间；为冲突小车行至下一行驶节点的预到达时间；r为节点的监测半径；v
m
为冲突小车的行驶速度；表示冲突小车此时占据冲突节点，表示冲突小车此时停车；
③
追赶冲突：主通过agv agent自身的距离监测模块实现，实时监控同一路段上同向行驶两车间距离；3)冲突解决机制
①
相向冲突解决a、从可行节点集合中剔除具有相向冲突的初步决策出的下一行驶节点，若剔除后该集合为空，进入步骤e，否则继续从集合中优选转移概率最高的节点作为新的下一行驶节点，进入步骤b；b、根据式(8)判断本车采取换路行驶策略较于原地等待策略的时间损失，若不存在时间损失，则直接以新决策出的行驶节点为下一行驶节点，执行步骤d判断，否则进入步骤c；式中：ttn为本车从当前位置到达替换节点的时间；ntg为本车经替换节点到达目标节点的最短时间；tto为本车从当前位置到达冲突节点的时间；otg为本车由冲突节点到达目标节点的最短时间；wt为停车等待时间；c、换路行驶存在时间损失，根据agv当前所在节点路况考虑原地停车、换边停车或强制换路策略，不同策略对应的路况依据如下：原地停车：agv agent调用当前所在节点agent的冲突小车一步预测接口，由其中封装函数预测冲突小车到达本节点后的下一步行驶节点，获得预测结果后，该agv继续判断若预测节点不在本车当前所在路段方向，则判定冲突小车行驶至本节点后不会与本车相撞，实行原地停车等待策略；换边停车：若预测节点在本车当前所在路段方向，判定冲突小车到达本车所在节点后相撞，则agv agent与当前所在节点agent交互此刻节点附近是否存在空闲路段，若存在，agv行驶至空闲路段停车等待，即换边停车；强制换路：以上情况均不满足时，则agv必须换路，以步骤a中决策出的节点为下一行驶节点；d、若agv换路了，则需要对新节点所在路段继续进行节点相向冲突检测，若依旧存在冲突，重复步骤a～c，否则agv向新节点行驶；e、当前小车无路可换亦不可停车等待时，必定碰撞，此种情况需与冲突小车进行交互，使其倒退让路，由本车占据冲突路段的行使权；
②
同一节点争夺冲突解决同一节点争夺冲突由agv agent中的同一节点争夺冲突检测与解决模块识别与解除，检测到该类冲突后，封装在该模块中的冲突解决策略主要通过比较本车与冲突车间的优先级实现，优先级高者获得冲突节点的行驶权，级别低的则换路，若不存在可换节点则停车等待；其中，优先级通过以下步骤确定：a、此刻或在上一行驶节点处具有相向冲突情况者，为避免与相向冲突车碰撞，应具有
更高的优先级别；b、比较发生冲突的各辆agv当前所在节点的拥挤度，拥挤度高者赋予更高的优先级别，以使其尽快驶离所在节点，降低节点拥挤程度；c、若当前所在节点拥挤度相同，则比较冲突节点对哪辆agv的吸引程度更高，高者获得更高的优先级别；
③
追赶冲突解决当agv agent的距离监测模块检测到两车间距离小于安全距离时，追赶车则自行停车等待，当前方车行驶至两车间距离为安全距离时，追赶车才继续行驶；b、考虑扰动事件制定响应策略形成混合仿真模型；这里的扰动事件包括紧急插单、agv故障和机床故障；(1)紧急插单当紧急订单到达时，系统agent根据订单信息生成对应工件agent与工序agent并将其状态登记为紧急，据此，工件agent由生产过程子模型中的“订单进入”对象进入生产系统时，紧急工件被识别并被赋予最高优先级，使其优先协商；进入“协商”的合同网协商阶段时，紧急工序agent在招标时将标书标识为紧急状态，agv与机床agent据此在计算投标内容时，将缓冲池中的所有未执行任务滞后，以最早开始搬运时间投标，中标后将紧急任务插入缓冲池中所有非紧急任务前方，使其被优先执行；(2)agv故障agv故障时，对故障agv任务缓冲池中的所有任务进行重协商；此时缓冲池中的任务有两种状态：正在搬运与等待搬运，其中正在搬运又分为空载、负载两种情况；故障发生时，处于空载搬运与等待搬运状态的任务只需将对应工件agent从生产过程子模型中的“等待与执行运输”模块中释放至“协商”中重协商搬运agv与加工机床即可，工件位置未发生变化；负载搬运状态下由于工件正跟随agv在路网中移动，当agv故障时，被携带的工件则滞留在此刻离agv最近的节点位置处，重协商时则以工件实际滞留位置计算距离信息；无论缓冲池中任务处于何种状态，“等待与执行运输”模块将其释放后，都要流入“判断agv故障”对象中，由该模块对需要重协商的工件分流，需要重协商的工件被返回至“协商”中重协商，否则流入加工模块中加工；此外，在所有任务重协商开始前，需将故障agv任务缓冲池清空，同时还需将所有重协商工件的加工任务从其加工机床的任务缓冲池中删除，而后，故障agv再以预估故障结束时间参与竞标；(3)机床故障机床故障时的响应策略为对故障机床任务缓冲池中的所有待执行任务进行重协商；此时缓冲池中的任务有四种状态：正在加工、缓冲站中等待加工、正在搬运、等待搬运；正在加工的工件不作重协商处理，等待故障结束时继续加工；缓冲站中等待加工与等待搬运状态下的任务则需分别从生产过程子模型的“加工缓冲”与“等待与执行运输”模块释放至“协商”中重协商搬运agv与加工机床；正在搬运状态下的任务则只需为其重协商加工机床即可，获得新的加工机床位置后，由签约agv的路径规划模块直接更改目的地为新位置即可；从“加工缓冲”与“等待与执行运输”模块释放出的工件，分别流入“判断agv故障”、“判断机床故障”对象中，由该模块对需要重协商的工件分流，需要重协商的工件被返回至“协商”中重协商，否则流入加工模块继续加工；同样地，在所有重协商任务开始前，需将故障机
床任务缓冲池中所有待执行任务清空，同时还需将所有处于等待搬运阶段的重协商工件的搬运任务从其搬运agv的任务缓冲池中删除；而后，故障机床以预估故障结束时间参与竞标，若存在正在加工工件，则以故障结束后该工件的预估结束加工时间参与竞标。

技术总结
本发明公开了一种考虑路径规划和扰动响应的车间集成动态调度方法，具体为：首先，基于AGV Agent与节点Agent信息交互与决策的无碰路径规划，包括AGV基于节点拥挤度的路径选择以及行驶过程中的三类常见冲突的解决策略研究；其次，进行了路径规划与扰动响应策略下的集成调度混合仿真模型，针对扰动事件包括紧急插单、AGV故障和机床故障设计了重协商响应策略，实现了基于混合仿真模型，融入无碰路径规划和扰动响应策略的柔性生产车间机床与AGV的动态集成调度系统。本发明AGV间的碰撞次数被大幅降低，算法避碰性能良好；在设备故障和紧急插单时，整个系统的鲁棒性波动很小，系统响应扰动能力良好。应扰动能力良好。应扰动能力良好。


技术研发人员：付建林 张剑 郭沛佩 米雨阳 杨涵覃 谢家翔
受保护的技术使用者：西南交通大学
技术研发日：2023.06.06
技术公布日：2023/9/9