一种基于动态任务分配的双车协同作业路径规划方法及系统

摘要: 本发明涉及多车协同路径规划,尤其涉及一种基于动态任务分配的双车协同作业路径规划方法及系统。背景技术:1、目前,在智能仓储双车搬运场景中,两辆搬运车辆通常搭载海鸥...
一种基于动态任务分配的双车协同作业路径规划方法及系统

本发明涉及多车协同路径规划,尤其涉及一种基于动态任务分配的双车协同作业路径规划方法及系统。

背景技术:

1、目前,在智能仓储双车搬运场景中,两辆搬运车辆通常搭载海鸥派开发板作为车载控制单元,并通过can总线共享任务队列、实时位置和速度状态,仓储任务随订单变化而动态到达,双车需要不断更新任务执行顺序、行驶路径和路段占用时间。在现有技术中,通常采用基于距离最短或先到先得的任务分配策略,先确定每辆车的任务序列,再分别调用局部路径规划算法生成路径;当检测到路径重叠或交叉时,再通过减速等待、局部绕行或固定优先级规则进行冲突处理。任务队列和路径时间窗的更新多由主控车或上位机按固定周期执行,双车之间交换的信息以位置、速度和当前任务编号为主,对已规划时间窗的一致性和动态维护较为有限。这种先分配后规划、冲突后处理的思路,在任务到达频率较低或双车共享路段较少时尚可维持运行,但在高优先级任务动态插入时,难以保证两车任务序列与时间窗的全局一致。

2、例如,当高优先级任务突然插入时,现有方法往往只对新任务进行局部重排,例如选择距离取货点较近的车辆执行,或者将该任务直接插入某一车辆任务队列的空闲位置,并未同步调整两车已经占用的路径时间窗。在窄道、交叉口等共享路段上,两车原有时间窗往往存在交叉或接近安全间隔的占用关系;如果被插入任务改变了其中一辆车进入和离开共享路段的时间,另一辆车仍按原时间窗行驶,就会产生时间窗重叠,进而形成交叉冲突。更严重的是,在相向窄道中,若两车因时间窗重叠而各自等待对方释放路段,可能形成a等待b、b等待a的对称等待结构,使系统进入死锁状态。此外,can总线消息延迟、定位误差和速度波动会造成两车对同一路段占用时刻的判断不一致,进一步增加冲突误判和任务延误的风险。由于现有技术没有对两车现有任务序列和已规划路径时间窗进行联合重规划,当发生单车任务重分配时,已占用时间窗无法同步修正,容易导致双车死锁和交叉冲突,并造成全局延误上升。

3、因此,亟需一种在智能仓储双车通过can共享动态任务队列的场景下,当高优先级任务插入时,能够对两车现有任务序列和已规划路径时间窗进行联合重规划的方法,以在满足任务优先级和车辆运动学约束的前提下,最小化全局延误,并有效消解因单车重分配引起的交叉冲突和死锁风险,提高双车协同作业的可靠性和抗死锁能力。

技术实现思路

1、针对上述存在的技术不足,本发明的目的是提出一种基于动态任务分配的双车协同作业路径规划方法及系统,旨在解决现有技术中高优先级任务插入时仅按距离或先到先得重排、未同步调整两车已占用路径时间窗,容易产生双车死锁和交叉冲突的问题,尤其是在智能仓储双车通过can共享动态任务队列条件下,无法在满足任务优先级和车辆运动学约束下实现最小化全局延误的任务重分配与路径冲突消解的技术问题。

2、为解决上述技术问题,本发明采用如下技术方案:本发明提供一种基于动态任务分配的双车协同作业路径规划方法及系统。

3、所述一种基于动态任务分配的双车协同作业路径规划方法及系统包括:

4、步骤s10:获取双车仓库协同作业数据,基于所述双车仓库协同作业数据,采用双车时钟同步与速度剖面建模机制执行时空模型构建任务,输出双车一致性时空模型;

5、步骤s20:基于所述双车一致性时空模型,采用任务紧急触发评估机制执行高优先级插入任务检测任务,输出联合重规划触发信号;

6、步骤s30:基于所述联合重规划触发信号,采用优先级竞价与冲突势反馈机制执行双车任务重分配任务,输出双车重分配任务序列;

7、步骤s40:基于所述双车重分配任务序列,采用分布式时间窗联合优化机制执行路径时间窗联合生成与冲突检测任务,输出联合优化时间窗;

8、步骤s50:基于所述联合优化时间窗,采用时空让行与死锁预防机制执行冲突消解任务,输出可执行时空轨迹。

9、优选地,步骤s10中,获取双车仓库协同作业数据,基于所述双车仓库协同作业数据,采用双车时钟同步与速度剖面建模机制执行时空模型构建任务,输出双车一致性时空模型的步骤,具体包括:

10、步骤s101:获取仓库拓扑数据、双车运动状态数据、任务数据和can总线交互数据,并将获取的数据组合为所述双车仓库协同作业数据;

11、步骤s102:基于所述双车仓库协同作业数据,通过can同步报文确定双车时钟偏移和传输延迟,并按照仓库路段长度、最大速度和车辆运动学约束生成双车速度剖面,得到统一时间基准下的双车运动与路段占用数据;

12、步骤s103:基于所述双车运动与路段占用数据,按照车辆通过各路段的进入时刻和离开时刻构建路径时间窗,并以基础安全时距、can总线消息延迟补偿及定位与速度波动补偿之和确定动态安全时距,将所述路径时间窗、动态安全时距和任务状态关联,得到所述双车一致性时空模型。

13、优选地,步骤s20中,基于所述双车一致性时空模型,采用任务紧急触发评估机制执行高优先级插入任务检测任务,输出联合重规划触发信号的步骤,具体包括:

14、步骤s201:从所述双车一致性时空模型中提取新任务优先级、新任务截止期、当前时刻、最大优先级和预设截止期参考范围,得到任务紧急度参数集;

15、步骤s202:从所述双车一致性时空模型中提取动态安全时距,确定两车当前路径中与新任务可行路径具有共享关系的窄道和交叉口路段集合,检测所述路段集合内满足所述动态安全时距的可插入空闲时间窗口,并按照各路段的冲突敏感度对所述可插入空闲时间窗口的长度进行加权求和,得到可插入时隙总长度;

16、步骤s203:基于所述任务紧急度参数集和所述可插入时隙总长度,将新任务优先级与最大优先级的比值、新任务剩余期限相对于所述预设截止期参考范围的紧迫程度以及所述可插入时隙总长度相对于预设最大空闲时隙总长度的不足程度进行加权求和,得到任务紧急触发指标;当所述任务紧急触发指标达到预设紧急触发阈值,或者新任务取货节点或放货节点与两车当前已规划路径节点存在时空交叉风险时,冻结当前任务执行版本并生成所述联合重规划触发信号。

17、优选地,步骤s202中,从所述双车一致性时空模型中提取动态安全时距,确定两车当前路径中与新任务可行路径具有共享关系的窄道和交叉口路段集合,检测所述路段集合内满足所述动态安全时距的可插入空闲时间窗口,并按照各路段的冲突敏感度对所述可插入空闲时间窗口的长度进行加权求和,得到可插入时隙总长度的步骤,具体包括:在各路段上对双车当前时间窗进行排序,将相邻时间窗的间隔长度大于车辆通过对应路段所需时间与所述动态安全时距之和的时间窗口确定为所述可插入空闲时间窗口,并按照下式确定所述可插入时隙总长度:

18、snew=e∈eshareωelavail,e

19、其中,snew为所述可插入时隙总长度,eshare为所述窄道和交叉口路段集合,e为所述窄道和交叉口路段集合中的路段,ωe为路段e的冲突敏感度权重,lavail,e为路段e上的所述可插入空闲时间窗口的长度。

20、优选地,步骤s30中,基于所述联合重规划触发信号,采用优先级竞价与冲突势反馈机制执行双车任务重分配任务,输出双车重分配任务序列的步骤,具体包括:

21、步骤s301:响应于所述联合重规划触发信号,将新任务和受影响的既有任务加入拍卖池,分别根据任务插入后的行驶距离增量、加权延误增量、时间窗冲突势和死锁势确定两车对各任务的竞价成本,得到双车竞价成本集;

22、步骤s302:基于所述双车竞价成本集,通过can总线交换两车的竞价成本和最新时间窗;当同一任务的竞价成本差值小于预设仲裁阈值时,根据对方最新时间窗更新所述时间窗冲突势和死锁势,得到修正竞价成本集;

23、步骤s303:基于所述修正竞价成本集,将任务分配给修正后竞价成本最小的车辆;当任务插入造成的既有任务加权延误超过预设可容忍延误时,将对应既有任务重新加入所述拍卖池进行竞价,直至任务分配稳定或达到预设最大迭代次数,得到所述双车重分配任务序列。

24、优选地,步骤s40中,基于所述双车重分配任务序列,采用分布式时间窗联合优化机制执行路径时间窗联合生成与冲突检测任务,输出联合优化时间窗的步骤,具体包括:

25、步骤s401:基于所述双车重分配任务序列,以累计行驶时间、到目标节点的启发式估计时间和被另一车辆占用的冲突代价之和作为节点代价,通过时空搜索分别生成双车候选路径和候选时间窗,得到双车候选路径时间窗集;

26、步骤s402:基于所述双车候选路径时间窗集,以双车时间窗相对于计划完成时间的偏离量和路段占用冲突量的加权和为联合优化目标,在车辆运动学约束、时间窗安全间隔约束和相邻路段时间窗顺序约束下,通过分布式增广拉格朗日迭代交换共享路段时间窗与乘子并更新共享路段全局参考时间窗,得到收敛时间窗集;

27、步骤s403:基于所述收敛时间窗集,检测双车在共享路段和交叉口的时间窗重叠;当双车共享路段时间窗之差小于预设收敛阈值或达到预设最大迭代次数时结束迭代,并将通过所述时间窗重叠检测的收敛时间窗集确定为所述联合优化时间窗。

28、优选地,步骤s50中,基于所述联合优化时间窗,采用时空让行与死锁预防机制执行冲突消解任务,输出可执行时空轨迹的步骤,具体包括:

29、步骤s501:从所述联合优化时间窗中提取存在时间窗重叠的冲突路段或交叉口,基于资源等待图检测双车对称等待结构,并对所述冲突路段或交叉口中的两车分别确定当前任务优先级倒数、让行加权延误增量和停车能耗增量,得到让行决策参数集;

30、步骤s502:基于所述让行决策参数集,按照下式确定让行车辆:

31、kyield=argmink∈{a,b}ω1pk,inv+ω2δek+ω3estop,k

32、其中,kyield为让行车辆编号,k为车辆编号,a和b为两车的车辆编号,argmin为取使括号内加权和最小的车辆编号的运算,ω1、ω2和ω3为预设权重系数,pk,inv为车辆k当前执行任务的优先级倒数,δek为车辆k的让行加权延误增量,estop,k为车辆k在当前位置或缓冲区停车的能耗增量;

33、步骤s503:基于所述让行车辆,在其路径上的可达缓冲区节点中选择等待时间与距冲突区域距离的加权和最小的节点作为等待节点;当绕行产生的加权延误增量小于在所述等待节点等待产生的加权延误增量时执行绕行,否则在所述等待节点等待;按照规划进入时间与基于当前速度及剩余距离估计的进入时间之差确定时间偏差,当所述时间偏差超过预设偏差触发阈值时,根据所述时间偏差以及实际速度与规划速度之差生成限幅速度指令,形成所述可执行时空轨迹。

34、本发明还提供一种基于动态任务分配的双车协同作业路径规划系统,包括:

35、时空模型构建模块,用于获取双车仓库协同作业数据,基于所述双车仓库协同作业数据,采用双车时钟同步与速度剖面建模机制执行时空模型构建任务,输出双车一致性时空模型;

36、高优先级插入任务检测模块,用于基于所述双车一致性时空模型,采用任务紧急触发评估机制执行高优先级插入任务检测任务,输出联合重规划触发信号;

37、双车任务重分配模块,用于基于所述联合重规划触发信号,采用优先级竞价与冲突势反馈机制执行双车任务重分配任务,输出双车重分配任务序列;

38、路径时间窗联合优化模块,用于基于所述双车重分配任务序列,采用分布式时间窗联合优化机制执行路径时间窗联合生成与冲突检测任务,输出联合优化时间窗;

39、冲突消解模块,用于基于所述联合优化时间窗,采用时空让行与死锁预防机制执行冲突消解任务,输出可执行时空轨迹。

40、本发明还提供一种基于动态任务分配的双车协同作业路径规划设备,所述基于动态任务分配的双车协同作业路径规划设备包括:存储器、处理器及存储在所述存储器上并可在所述处理器上运行的基于动态任务分配的双车协同作业路径规划程序,所述基于动态任务分配的双车协同作业路径规划程序被所述处理器执行时实现上述方法。

41、本发明还提供一种计算机程序产品,所述计算机程序产品包括基于动态任务分配的双车协同作业路径规划程序,所述基于动态任务分配的双车协同作业路径规划程序被处理器执行时实现上述方法。

42、本发明的有益效果在于:

43、通过双车时钟同步与速度剖面建模机制统一两车时间基准,并利用动态安全时距将路径时间窗与任务状态关联,形成双车一致性时空模型,使高优先级插入任务检测能够基于同一时空参照识别共享路段的可插入空闲时窗,从而减少因时钟偏移和速度波动导致的时间窗误判,提高联合重规划触发的准确性。

44、采用优先级竞价与冲突势反馈机制对双车任务进行重分配,在竞价成本中同时计入时间窗冲突势和死锁势,并通过can总线交换竞价成本与最新时间窗进行修正,使任务分配结果能够反映两车对共享路段占用的相互影响,避免仅按距离或先到先得分配造成的局部最优,从而降低后续路径时间窗联合优化阶段的冲突密度。

45、通过分布式时间窗联合优化机制对双车候选路径时间窗进行迭代交换与全局参考更新,并在冲突消解阶段基于资源等待图检测对称等待结构,结合让行决策参数选择等待节点或绕行,使两车在共享窄道和交叉口的时间窗重叠得到主动消解,从而减少因单车重分配引起的交叉冲突和死锁风险,提升双车协同作业的全局延误控制能力。