面向多机器人环境中动态异构任务的细粒度动作分配与调度方法

Fine-grained Action Allocation and Scheduling Method for Dynamic Heterogeneous Tasks in Multi-robot Environments

在多机器人环境中,具有不同能力的机器人相互协作以完成任务需求。现实情况下,这些任务动态发布,且具有不同的目标和紧急程度,因此需要为每个任务分解出的细粒度动作分配和调度合适的机器人来负责执行这些动作。现有的方法大多适用于静态和同构的任务分配场景,而针对动态异构任务的分配则大多采用独占式的分配策略,导致机器人频繁进入等待状态(即机器人处于被分配了任务到真正开始执行任务之间的闲置阶段)。由于任务存在不同的紧急程度和发布时间,这种分配方式将降低对更紧急任务的响应效率,同时导致更多的等待时间和更长的任务完成时间。针对该问题,提出了一种面向多机器人环境中动态异构任务的细粒度动作分配与调度方法。其中,分配与调度的对象是任务所分解出的细粒度的动作,且一个动作能够由机器人的一种能力承担。面对任务分解出的一组细粒度动作集合,本方法借鉴拍卖算法过程,根据机器人能力、状态及任务信息计算出机器人承担特定动作的最优分配方案。另外,在每一次新任务发布或某一机器人执行完动作时执行分配和调度过程,可以将处于普通任务等待状态的机器人调度至紧急任务,以保证紧急任务优先完成,且缩短机器人的总体等待时间。基于本方法,扩展实现了机器人执行框架(ROSPlan)的执行模块。围绕一组多机器人动态异构任务的模拟实验表明,所提方法相较于采用贪心策略的方法可得到更优的分配方案。

In a multi-robot environment,robots with different capabilities collaborate with each other to complete task requirements.Realistically,these tasks are dynamically issued and can have different goals and urgency levels,so it is necessary to allocate and schedule the appropriate robots responsible for executing the fine-grained actions decomposed for each task.Most of the existing approaches are suitable for static and homogeneous task allocation scenarios,while most of the dynamic heterogeneous tasks are assigned using exclusive allocation strategies,which causes the robot to frequently enter into waiting states(i.e.,robots are in the idle phase between being assigned a task and actually starting to execute it).Since tasks vary in urgency levels and release times,this allocation method will reduce the efficiency of response to more urgent tasks,while leading to longer waiting time and task completion time.To address this problem,this paper proposes a fine-grained action allocation and scheduling method for dynamic heterogeneous tasks in a multi-robot environment.In this paper,the object of allocation and scheduling is a fine-grained action decomposed by a task,and an action can be undertaken by one capability of a robot.Faced with a set of fine-grained actions decomposed by the task,this method draws on the auction algorithm process to calculate the optimal allocation scheme for a robot to undertake a specific action based on the robot capabilities,state and task information.In addition,by executing the allocation and scheduling process at each new task release or when a robot finishes executing an action,robots in the general task waiting state can be scheduled to the urgent task to ensure the priority completion of the urgent task and reduce the overall waiting time of the robot.Based on this approach,the execution module ROSPlan is extended and implemented.Simulation experiments around a set of multi-robot dynamic heterogeneous tasks show that the proposed methodr can obtain a better allocation scheme compared to the method using greedy policies.