本发明涉及导航和控制，具体设计一种面向突发障碍的多agv调度冲突消解方法。
背景技术：
1、自动引导车(automated guided vehicle,agv)作为一种高度智能化的运载工具，已经成为现在工业无人车间自动化产、港口运输、智能物流领域的关键设备之一，并且其应用场景也在不断拓展。例如，亚马逊公司引入kiva机器人系统，将订单拣选的时间缩短了近1/4，大大提升看物流运作的效率。由此可见，仓库、工程正在经历自动化的转型升级，由传统的“人管人”模式转变为“系统调度”的自动化模式。
2、以无人工厂为例，agv调度问题可以具体描述为：在封闭的车间场景中，在特定的时间周期内，物料需要被按时按量的送至不同的机床进行加工。无人车间内的所有agv都由统一的调度系统进行控制，系统根据机床发出的物料请求进行agv任务分配，系统规划出来的路径必须满足无阻塞冲突、无死锁的要求。目前关于agv调度优化算法具体可以分为精确方法(如分支定界法、枚举法、整数规划法)、近似方法(如近似方法、启发式算法)以及基于人工智能的新方法三类。基于时间窗的多agv调度算法是目前常用的调度算法之一，传统的时间窗算法的主要思想是将agv小车的各个路段加上时间标志，其他小车在该时间段中不能驶入该路段从而避免小车之间冲突的情况。
3、由于在agv工作的大部分场景中其路径区间为单行双向路径，在进行多agv任务路径规划时，经常会出现各路径之间相互冲突的情况。
4、例如，专利号为cn202210260353的发明中提出了一种基于时间窗的多agv实时调度的路径优化方法，对于路口冲突采用停等的策略，对于相向冲突则寻找最近的避障点进行停等操作，相应的时间窗需要加上前往避障点的时间以及在避障点停留的时间。这种方法无法避免回路产生的情况，冲突消解后该agv可能会和其他的路线继续产生冲突回到避障点继续等待，这种来回往返的情况会造成小车电量的消耗并且无法解决随机冲突，灵活性差。并且在实际的机床作业中，会遇到多种突发情况，专利号为cn202210260353的发明局限于静态调度的优化，无法处理随机障碍物。专利号为cn202210260354.2的发明基于图结构更多面向于港口等大型车辆应用场景，通过考虑车辆长度、宽度和速度确定时间安全阈值并预测冲突，但是该发明无法处理突发情况和死锁问题并且该发明针对于大型车辆，应用场景受限，相较而言本发明更具有普适性。
5、刘春在论文《大规模agv的改进时间窗路径规划*》中提出了动态时间窗算法，首先立足于单路路径规划算法找到最优路径，当路径与路径之间发生冲突的时候舍弃当前的冲突节点对该节点的父节点进行路径的重新规划。这种方法的不足在于利用父节点重新规划路线后，无法保证新路线不存在新的冲突节点，若新路线仍然存在冲突则需要一直重复调用路径规划算法，导致系统效率降低，无法避免多次重复调用而且无法有效避免局部避障后的死锁问题。
技术实现思路
1、为解决上述问题，本发明公开了一种面向突发障碍的多agv调度冲突消解方法，通过优化静态调度和动态调度两大阶段，能够减少静态预规划路径中的冗余回路，提前利用twia算法减少全局冲突，提升静态线路规划的逻辑性；优化后的动态调度策略能够处理仿真过程中的突发情况(随机障碍物、车辆故障)，同时局部预防死锁机制以及任务重处理机制能够预防不确定情况下的死循环问题和提升任务的成功率。
2、步骤1、建立车间调度信息。根据生产实体、物流实体、环境、作业、车间规则与约束条件、随机障碍物等建立车间调度信息数据库；
3、步骤2、调度系统接收请求和静态路径规划。调度系统接收来自加工设备的运输请求并放入任务队列通过时间窗无冲突优化路径算法twia(time-window conflict-freeimproved route algorithm)预先规划全局静态路径；
4、步骤3、分配任务和小车运行。将预先规划全局静态路径。放入执行路线队列中，查询空闲小车队列，并为其分配一个空闲agv小车；
5、步骤4、突发障碍检测。循环检测运行小车队列中各agv小车状态，判断小车是否遇到突发障碍而导致无法正常行进，若小车状态异常则执行步骤5，否则执行步骤10；
6、步骤5、突发障碍的动态调度策略。判断障碍物类型，若前方为固定障碍物执行步骤6，若前方的障碍物为非固定障碍物且在下一调度周期内离开则执行步骤7。
7、步骤6、重新规划路径。对于无法直接解决的固定障碍物冲突问题，尝试重新规划路径，若存在新路径则执行步骤2继续运行小车，否则执行步骤10。
8、步骤7、局部预防死锁机制。对于非固定障碍物，采取回退避障策略解决局部冲突，为防止回退过程中与其他小车发生连锁冲突从而导致死循环，局部预防死锁机制增添了回退次数的统计，若回退已经累计3次则执行步骤8。
9、步骤8、任务重处理机制。根据任务类型重新处理该小车的任务，若可以安排新任务以缓解局部冲突则执行步骤2，否则执行步骤9。
10、步骤9、终止agv，中止其任务。终止该agv，并设置为固定障碍物，其所在坐标设为不可达并重新处理该小车承担的任务。
11、步骤10、循环执行步骤2-9，直到所有agv小车调度结束。
12、进一步地，步骤2中时间窗无冲突优化路径算法(twia)的具体实现过程包括：
13、步骤2-1、接收调度任务。对于一个运输任务请求，为其进行初始的最短路径规划和每个路径节点添加时间窗标记；
14、步骤2-2、全局路径冲突消解。对初始的带有时间标记的最短路径的每个节点与其它正在执行的路径进行冲突检查，如果存在冲突，则对新规划的初始路径进行避障处理，直到得到无冲突的路径；
15、步骤2-3、基于多步预测的回路检查。对全局无冲突路径，逐个遍历路径中每个节点ri，其中i＝1,2,…,k，检查其是否在路径中再次出现，若出现则存在回路，转下一步。
16、步骤2-4、优化路径并修改时间窗。计算回路中再次出现该节点ri的路径长度l，并将回路中的所有节点设为节点ri，即在原节点停等l/v秒。
17、步骤2-5、重复步骤2-3和2-4直到没有回路为止，得到优化后的预先规划全局静态路径及其时间窗；
18、步骤2-6、再次检查预先规划全局静态路径是否存在冲突。若无冲突，则转到步骤5；若存在冲突，则转步骤2-2。
19、进一步地，步骤8中任务重处理机制具体实现过程包括：
20、步骤8-1、判断小车是否行驶在返程途中暂时被中止，若在返程途中执行步骤8-2，不在返程途中执行步骤8-3；
21、步骤8-2、判断是否为送货任务，若小车是在送货任务的返程途中遇突发冲突暂时被中止视该送货任务成功被执行；若小车实在取货任务的返程途中暂时被中止，设置该agv小车为固定障碍物并终止其运行，标记其所在节点位置nagv1，更新地图信息map，视该取货任务失败并重置相应机床状态。
22、步骤8-3、判断是否为取货任务，若小车是在取货任务的去程途中遇突发冲突且暂时被中止，则将该小车所承担的任务重新放回任务池，等待新的小车接收该任务。若小车是在送货任务的去程途中遇突发冲突暂时被中止，则执行8-4；
23、步骤8-4、由于小车是在送货任务的去程途中遇突发冲突暂时被中止，响应其他机床的送货请求，修改目的地。
24、本发明有益效果是：
25、第一，本发明提出一种面向突发障碍的多agv调度冲突消解方法，在静态调度阶段，利用时间窗无冲突优化路径算法twia算法预先规划全局路径，能够提前消减全局冲突，降低局部避障的复杂性；同时，能够判断预规划路径中的冗余回路，避免多步之后小车回到原地停等的情况，提升静态线路规划的逻辑性、合理性；从节约能源的角度出发，通过对无效路线的效减，可以有效降低小车电量消耗、延长工作时间。
26、第二，本发明提出的一种面向突发障碍的多agv调度冲突消解方法，在动态调度阶段，通过优化后的动态调度策略能够模拟真实情况下的仿真，处理仿真过程中的突发情况(随机障碍物、车辆故障)，对于非固定障碍物，局部预防死锁机制能够缓解回退过程中与其他小车发生连锁冲突而导致的死循环问题。
27、第三，本发明提出的面向突发障碍的多agv调度冲突消解方法，从任务成功率的角度：传统的时间窗算法是一种理想化的策略无法处理随机障碍物，动态时间窗算法在能够处理随机障碍物但忽视了局部避障后小车死锁所导致的任务失败问题。本发明中的任务重处理机制能够重新分配堵塞小车的运输任务，改变目标机床以缓解布局堵塞问题并提升任务的成功率。
1.一种面向突发障碍的多agv调度冲突消解方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的一种面向突发障碍的多agv调度冲突消解方法，其特征在于，所述的步骤2中时间窗无冲突优化路径算法(twia)的具体实现过程包括：
3.根据权利要求1所述的一种面向突发障碍的多agv调度冲突消解方法，其特征在于，所述的步骤5中突发障碍的动态调度策略具体实现过程包括：
4.根据权利要求1所述的一种面向突发障碍的多agv调度冲突消解方法，其特征在于，所述的步骤8中任务重处理机制具体实现过程包括：
