一种动态场景的多机器人任务编排方法及系统与流程

摘要: 本发明涉及机器人调度,特别涉及一种动态场景的多机器人任务编排方法及系统。背景技术:1、在多机器人协同作业的场景中,任务持续动态到达,系统需要实时将任务分配给合适...
一种动态场景的多机器人任务编排方法及系统与流程

本发明涉及机器人调度,特别涉及一种动态场景的多机器人任务编排方法及系统。

背景技术:

1、在多机器人协同作业的场景中,任务持续动态到达,系统需要实时将任务分配给合适的机器人并确定任务执行顺序。现有调度技术主要分为两类:一类是贪婪式的单任务分配方法,针对每一个新到达的任务,在当前可用机器人中选择距离最近的一台进行分配。该类方法实时性好但缺乏全局视角,仅考虑单个任务的局部最优,容易导致整体调度方案次优,当多个任务同时或连续到达时,可能出现“短视”分配,造成后续任务执行效率低下。另一类是静态批量优化方法,收集一定时间窗口内的所有任务,构建数学优化模型求解全局最优分配方案。该类方法理论上可接近全局最优,但计算复杂度高、求解时间长,难以满足实时调度需求,且当任务动态增加或机器人状态变化时,需要重新求解整个分配方案,导致调度震荡。

2、此外,实际生产环境中经常存在机器人动态上下线的情况。现有技术大多假设任务信息预先知晓或机器人状态固定,难以适应动态环境;全局优化方法随着任务和机器人数量的增加,计算复杂度呈指数增长,在大规模场景下难以实用。因此,如何在保证实时响应的同时降低系统总成本、减少调度震荡并适应动态环境,成为多机器人任务调度领域的关键问题。

技术实现思路

1、本发明目的是:提供一种动态场景的多机器人任务编排方法及系统,以解决现有技术中实时性与优化质量矛盾、调度震荡频繁、难以适应动态环境的问题。

2、本发明的技术方案是:一种动态场景的多机器人任务编排方法,包括:获取当前可用机器人的预分配任务队列及其对应的总路径成本;计算当前新任务插入各所述预分配任务队列的最小路径成本增量,基于各所述最小路径成本增量的升序排序筛选前n个当前可用机器人,构成候选机器人集合;计算所述新任务分别插入所述候选机器人集合中每个机器人的预分配任务队列可插入位置所对应的路径成本增量,并基于所述路径成本增量的升序排序筛选前m个可插入位置,构成候选插入位置集合;选取所述候选插入位置集合中的任意一个位置,执行新任务插入;基于新任务插入后的预分配任务队列执行邻域局部搜索优化,所述邻域局部搜索优化包括队列内任务重排、跨队列任务迁移和跨队列任务交换。

3、进一步地,还包括对所述预分配任务队列进行维护:当所述当前可用机器人完成当前任务后,状态变为空闲;当所述当前可用机器人处于空闲状态且其预分配任务队列非空时,从该机器人预分配任务队列的队首取出任务并开始执行该任务;当所述当前可用机器人下线时,将其预分配任务队列中的未执行任务转移至未分配任务集合,并清空该机器人的预分配任务队列;当所述当前可用机器人下线或其当前挂载任务数量达到预设容量上限时,状态变为不可用,不再给该机器人分配新任务。

4、进一步地,所述候选机器人集合的构成还包括:检查所述新任务目标位置是否处于机器人可达范围内,若处于不可达范围则剔除该机器人;所述候选插入位置集合的构成还包括:检查新任务插入各可插入位置的路径成本增量是否能够有效计算,若不能有效计算则剔除。

5、进一步地,当所述候选插入位置集合为空时,将该新任务加入未分配任务集合。

6、进一步地,还包括对所述未分配任务集合中的任务按照预设触发条件进行任务编排;所述预设触发条件包括新任务到达、有机器人上线、有机器人下线。

7、进一步地,所述总路径成本根据路径矩阵确定,为单个机器人预分配任务队列中所有任务对应的路径成本之和;所述路径矩阵基于地图信息预计算得到,用于记录地图中各目标位置之间的路径代价;所述路径成本增量为新任务插入后该新任务对应的机器人的总路径成本与未插入时该机器人的总路径成本之差。

8、进一步地,所述邻域局部搜索优化只接受能使系统总成本降低的邻域操作,所述系统总成本为各当前在线机器人对应的总路径成本之和。

9、进一步地,所述邻域局部搜索优化以迭代方式执行,每轮迭代按序尝试队列内任务重排、跨队列任务迁移和跨队列任务交换中的一项邻域操作,且每轮迭代最多执行一个能使系统总成本降低的改进操作;其中,队列内任务重排采用首次改善策略,找到第一个能使系统总成本降低的重排操作后执行并结束本轮;跨队列任务迁移和跨队列任务交换采用最优改善策略,在当前轮中分别搜索使系统总成本降幅最大的迁移操作或交换操作并执行。

10、进一步地,所述邻域局部搜索优化的终止条件包括以下至少一项:达到预设的最大搜索深度;评估预算扣减至小于或等于零。

11、一种动态场景的多机器人任务编排系统,包括:任务队列获取模块,用于获取当前可用机器人的预分配任务队列及其对应的总路径成本;任务插入模块,用于计算当前新任务插入各所述预分配任务队列的最小路径成本增量,基于各所述最小路径成本增量的升序排序筛选前n个当前可用机器人,构成候选机器人集合;计算所述新任务分别插入所述候选机器人集合中每个机器人的预分配任务队列可插入位置所对应的路径成本增量,并基于所述路径成本增量的升序排序筛选前m个可插入位置,构成候选插入位置集合;选取所述候选插入位置集合中的任意一个位置,执行新任务插入;优化模块,用于基于新任务插入后的预分配任务队列执行邻域局部搜索优化,所述邻域局部搜索优化包括队列内任务重排、跨队列任务迁移和跨队列任务交换。

12、与现有技术相比,本发明的优点是:

13、(1)通过增量插入和局部搜索结合的方法,避免每一个新任务都触发全局编排方案的重算,提高任务编排的实时性;同时通过多次邻域搜索持续优化编排方案质量,获取更优解。与传统贪婪式的单任务插入方法相比,本发明方法能更有效降低系统总成本,路径轨迹更清晰简洁。

14、(2)通过维护预分配任务队列,适应机器人上下线、任务动态增加等实时变化。

15、(3)通过双层筛选结构先选n个候选机器人再从中选m个候选插入位置,并随机确定最终插入位置,在保证贪心方向的同时引入随机性,为后续优化留下改进空间。

16、(4)通过核心参数候选机器人数量、候选插入位置数量、最大搜索深度、评估预算实现搜索精度与计算开销的调节,适配不同规模的多机器人系统。

1.一种动态场景的多机器人任务编排方法,其特征在于,包括:

2.根据权利要求1所述的多机器人任务编排方法,其特征在于,还包括对所述预分配任务队列进行维护:

3.根据权利要求1所述的多机器人任务编排方法,其特征在于,所述候选机器人集合的构成还包括:检查所述新任务目标位置是否处于机器人可达范围内,若处于不可达范围则剔除该机器人;

4.根据权利要求3所述的多机器人任务编排方法,其特征在于,当所述候选插入位置集合为空时,将该新任务加入未分配任务集合。

5.根据权利要求4所述的多机器人任务编排方法,其特征在于,还包括对所述未分配任务集合中的任务按照预设触发条件进行任务编排;

6.根据权利要求1所述的多机器人任务编排方法,其特征在于,所述总路径成本根据路径矩阵确定,为单个机器人预分配任务队列中所有任务对应的路径成本之和;

7.根据权利要求1所述的多机器人任务编排方法,其特征在于,所述邻域局部搜索优化只接受能使系统总成本降低的邻域操作,所述系统总成本为各当前在线机器人对应的总路径成本之和。

8.根据权利要求7所述的多机器人任务编排方法,其特征在于,所述邻域局部搜索优化以迭代方式执行,每轮迭代按序尝试队列内任务重排、跨队列任务迁移和跨队列任务交换中的一项邻域操作,且每轮迭代最多执行一个能使系统总成本降低的改进操作;

9.根据权利要求8所述的多机器人任务编排方法,其特征在于,所述邻域局部搜索优化的终止条件包括以下至少一项:

10.一种动态场景的多机器人任务编排系统,其特征在于,包括: