一种基于启发式策略的多AGV协同调度方法

本发明涉及agv协同调度，具体为一种基于启发式策略的多agv协同调度方法。

背景技术：

1、随着智能制造与柔性生产模式的快速发展，自动导引车已经广泛应用于柔性制造、智能仓储和自动化物流等场景，并逐渐成为现代制造系统中连接加工设备、仓储单元和装配单元的重要物流运输设备，相比传统人工搬运方式，agv系统能够有效降低人力成本，提高物料搬运效率，减少人为操作误差，并增强生产系统运行的连续性和稳定性，因此，多agv调度系统的性能将直接影响柔性制造系统的生产节拍、设备利用率和整体运行效率。

2、多agv协同调度问题涉及任务如何分配给车辆，还涉及车辆在共享路网中如何规划路径、如何避免冲突以及如何保持系统稳定运行等问题。在实际生产环境中，多辆agv同时运行时，容易在交叉路口、狭窄通道和共享路径区域发生资源竞争和路径冲突，严重时还可能形成车辆等待和系统阻塞。因此，如何在任务分配与路径规划之间建立有效的协同机制，是多agv调度研究中的重要问题。现有启发式算法在路径规划和任务分配中具有计算效率高、规则清晰和易于实现等优点，但传统方法难以充分考虑车辆运行过程中的路径代价、转弯代价、拥堵状态和冲突风险。此外，在多agv实际运行过程中，车辆并非仅占用单一路径节点。由于agv具有一定车体尺寸，并且运行过程中需要保持安全距离，其实际占用范围往往会覆盖多个路径节点或检测点。若调度系统仍采用单点占用方式进行冲突检测，容易低估车辆间的空间干涉关系，从而导致路径冲突、拥堵和死锁问题。同时，在柔性作业车间中还可能存在机器故障、车辆脱轨、任务动态变化等扰动工况，进一步增加了多agv协同调度的复杂性。

3、基于此，本发明提出一种基于启发式策略的多agv协同调度方法。该方法面向柔性作业车间环境，设计基于任务优先级和车辆响应代价的任务分配策略，结合引入转弯代价、死锁因子和未来路网拥挤代价的改进a*路径规划方法，并进一步构建基于agv车体尺寸和安全距离的冲突检测机制以及死锁恢复策略，实现任务分配、路径规划、冲突检测和死锁恢复之间的协同优化，从而提高多agv系统在复杂动态工况下的运行效率和稳定性。

技术实现思路

1、本发明提供了一种基于启发式策略的多agv协同调度方法，具备有效降低agv空驶距离、减少路径冲突和死锁发生的有益效果。

2、本发明提供如下技术方案：一种基于启发式策略的多agv协同调度方法，包括以下步骤：

3、s1、基于约束条件建立以最小化最大完工时间为优化目标的多agv协同调度数学模型；

4、s2、所述多agv协同调度数学模型基于代价规则选取可用工件集合与可用agv集合，并快速匹配最优执行组合并分配任务至agv处；

5、s3、引用多因素的改进a*算法，计算分配agv规划路径，输出当前点到目标节点的规划路径；

6、s4、基于所述规划路径中的实际物理尺寸冲突检测与死锁恢复优化调整规划路径，完成多agv协同调度。

7、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，所述基于代价规则进行任务分配的方法包括：

8、实时识别未加工完的可用工件集合与处于就绪状态的可用agv集合；

9、按优先级从可用工件集合中选取最紧迫工件与满足地图匹配的候选agv，生成运输任务；

10、计算候选agv执行该运输任务的综合代价；

11、选择综合代价最小的agv执行任务并更新系统状态。

12、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，所述综合代价的计算公式为：

13、

14、其中，为agv到达任务起点的距离代价；

15、为agv执行该任务时的路径风险代价；

16、和为权重系数；

17、其中，+=1。

18、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中：所述多因素包括基于综合代价确定路径规划起点和终点、未来路网拥堵系数、死锁因子和转弯惩罚系数；

19、所述多因素的改进a*的综合评价函数计算公式包括：

20、

21、其中，为从起点到当前路径节点的实际路径代价；

22、为当前候选路段的距离；

23、为当前候选路段的拥堵系数；

24、为转弯惩罚系数，为死锁因子，为候选子节点到目标节点的曼哈顿距离，为死锁因子权重。

25、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，还包括：

26、根据所述规划路径建立路径网络，所述路径网络包括若干个路径节点；

27、根据候选agv最长边和安全距离，为每个路径节点生成检测点集合；

28、当候选agv位于占用路径节点时，同时锁定该路径节点安全范围内的多个检测点，以防止候选agv实体间的空间干涉；

29、判定当前候选agv的下一路径节点是否存在被其他agv占用；

30、当被其他agv占用，检测是否死锁，执行死锁恢复。

31、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，所述死锁恢复的方法包括：

32、将触发检测的agv标记为第一agv，阻塞其路径的agv标记为第二agv；

33、以第二agv为起点，利用广度优先搜索寻找避让点，所述避让点满足不在第一agv路径上且不造成新阻塞的约束；

34、控制第二agv移动至所述避让点，释放路径供第一agv通行。

35、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中：所述死锁恢复的方法至少恢复一种死锁类型；

36、所述死锁类型包括环形死锁、带检测点的环形死锁、对向死锁、带检测点的对向死锁和空闲死锁。

37、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，所述约束条件包括：

38、同一工件的同一工序仅能分配给一台机器加工和一台agv运输；

39、同一时间段内一个节点或一条边仅能被一辆agv占用；

40、工件的加工开始时间不早于agv将其运抵机器的时间。

41、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，针对路径网络中的任一路径节点，计算所述未来路网拥堵系数的方法包括：

42、统计所有agv剩余规划路径节点出现的总次数，和所有agv剩余规划路径中涉及的路径节点总数；

43、计算路径节点的初始拥挤率；

44、当时，令=0.99，基于修正后的，计算路径节点的节点修正参数，计算公式为：

45、

46、最终确定该路段同理计算该路径上拓展节点的节点修正参数；

47、最终确定该路段的拥堵修正系数公式为：

48、

49、并将所述拥堵修正系数作为权重因子，融入路径规划的综合评价函数中，用于动态调整路径选择优先级，以规避高拥堵区域。

50、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，针对当前agv的规划路径中任意相邻节点对，计算其死锁因子的方法包括：

51、获取其他所有agv的剩余规划路径集合；

52、遍历各剩余路径，判断是否存在相邻节点对满足和，即其他agv在该路段上运行方向与当前agv相反；

53、统计满足上述条件的agv数量记为可能存在对向冲突风险的agv数；

54、设定死锁因子惩罚系数；

55、计算该节点对的死锁因子计算公式为：

56、。

57、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，针对当前agv规划路径中由父节点经路径节点u至路径节点v的两段连续路径，计算转弯系数，包括：

58、构建第一段路径的方向向量；

59、构建第二段路径的方向向量；

60、计算两向量的叉积；

61、根据叉积符号确定转弯方向并赋值转弯系数：

62、

63、并将所述转弯系数作为路径代价的附加项，融入改进a*算法的评价函数中，以抑制频繁转向行为，提升路径平滑性与运行效率。

64、作为本发明所述基于启发式策略的多agv协同调度方法的一种可选方案，其中，包括以下步骤：

65、根据所述路径节点集合与路径边集合的路径网络、agv集合件集合、机器集合和工件合集构建仿真运行环境；

66、在仿真过程中，控制agv按照包含启动加速度、匀速运行速度和目标节点前减速度的运动学参数运行，并实时更新agv的当前位置、运行状态、目标节点列表、剩余规划路径、节点占用状态和检测点占用状态；

67、在仿真结束后，记录各工件任务的完成时间，计算各工件完成时间的最大值作为系统的最大完工时间，并输出调度结果以验证调度方法的有效性。

68、本发明具备以下有益效果：

69、1、该基于启发式策略的多agv协同调度方法，通过基于任务优先级与车辆响应代价的任务分配策略，能够在考虑工件任务优先级、agv可用状态和车辆距离代价的基础上，实现工件与agv之间的快速匹配，同时，采用改进a*算法进行路径规划，在路径搜索过程中引入转弯代价、死锁因子和未来路网拥挤代价，使agv规划路径更加符合实际运行需求。

70、2、该基于启发式策略的多agv协同调度方法，基于agv车体尺寸和安全距离构建冲突检测机制，并针对环形死锁、带检测点的环形死锁、对向死锁、带检测点的对向死锁和空闲死锁设计死锁恢复策略。该方法规则清晰、实现复杂度低、实时性较强，能够有效降低agv空驶距离、减少路径冲突和死锁发生，提高多agv系统的运行效率和稳定性。