一种移动机器人的作业任务动态调度下发系统及方法

摘要

本发明公开了一种移动机器人的作业任务动态调度下发系统及方法，该方法包括以下步骤：将机器人的作业任务，根据任务种类分组为若干个任务组并生成任务列表，且所述作业任务的数据结构以有向图的形式表示；根据所述任务列表的先后顺序下发作业任务给机器人；根据作业任务完成情况实时更新作业任务的任务状态，并通过将有向图上存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务，对作业任务进行动态调度。本发明，以有向图的边表示相连的两个作业任务执行的先后依赖关系，通过将存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务，对作业任务进行动态调度，算法简单，效率高，且可以对作业任务进行灵活地调度。

权利要求

1.一种移动机器人的作业任务动态调度下发方法，其特征在于，包括以下步骤：将机器人的作业任务，根据任务种类分组为若干个任务组并生成任务列表，且所述作业任务的数据结构以有向图的形式表示；每个任务组中包含有若干个作业任务，且所述作业任务分别通过组内有向边连接，所述组内有向边用于表示相连的两个作业任务执行的先后依赖关系；不同的任务组中的作业任务通过组间有向边连接形成总任务有向图，所述组间有向边用于表示任务组之间相连的两个作业任务执行的先后依赖关系；

根据机器人空闲情况，以一个任务组作为最小单元分配给相应的机器人；

根据作业任务完成情况实时更新作业任务的任务状态，并通过将存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务，对作业任务进行动态调度，且将所述上级作业任务的任务状态修改为已完成。

2.根据权利要求1所述的方法，其特征在于，存在依赖关系的两个作业任务，如果后级作业任务在规定时间内未更新任务状态为已完成，则自动对作业任务进行动态调度。

3.根据权利要求1或2所述的方法，其特征在于，对作业任务进行动态调度的方式为：在上级任务组中增一个新作业任务，并将所述新作业任务的任务状态设置为已完成，将存在依赖关系的下级作业任务的上级任务指向所述新作业任务。

4.根据权利要求1或2所述的方法，其特征在于，对作业任务进行动态调度的方式为：创建一个新任务组，并在所述新任务组中增加至少一个新作业任务，将其中一个新作业任务的依赖关系指向上级任务组中相应的作业任务。

5.根据权利要求1所述的方法，其特征在于，存在依赖关系的两个任务组中，上级任务组中的最后的一个作业任务指向下级任务组中的第一个作业任务。

6.一种移动机器人的作业任务动态调度下发系统，其特征在于，包括：任务列表生成单元，用于根据任务种类分组为若干个任务组并生成任务列表，所述作业任务的数据结构以有向图的形式表示；每个任务组中包含有若干个作业任务，且所述作业任务分别通过组内有向边连接，所述组内有向边用于表示相连的两个作业任务执行的先后依赖关系；不同的任务组中的作业任务通过组间有向边连接形成总任务有向图，所述组间有向边用于表示任务组之间相连的两个作业任务执行的先后依赖关系；

任务状态更新单元，用于根据作业任务的完成情况实时更新任务状态；

任务状态修改单元，用于将存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务；

调度单元，用于根据机器人空闲情况，以一个任务组作为最小单元分配给相应的机器人，自动对作业任务进行动态调度。

7.根据权利要求6所述的系统，其特征在于，根据存在依赖关系的两个作业任务中，后级作业任务在规定时间内未更新任务状态为已完成，所述调度单元自动对作业任务进行动态调度。

8.根据权利要求6或7所述的系统，其特征在于，还包括：新任务增加单元，用于在任务组中增一个新作业任务，并通过所述任务状态修改单元将所述新作业任务的任务状态设置为已完成，通过所述任务列表生成单元将存在依赖关系的下级作业任务指向所述新作业任务；或者，创建一个新任务组，并在所述新任务组中增加所述新作业任务。

说明书

一种移动机器人的作业任务动态调度下发系统及方法

技术领域

[0001] 本发明涉及机器人技术领域，具体涉及一种移动机器人的作业任务动态调度下发系统及方法。

背景技术

[0002] 目前，移动机器人在工业、农业、医疗、服务等行业中得到了广泛的应用。并且，在实际应用中，通常由多个移动机器人共同协作完成工作任务。因此，移动机器人的作业任务
分配，在提高作业任务完成速度和效率方面，起到了非常关键的作用。

[0003] 目前，移动机器人的作业任务，通常是静态下发的，也就是説，调度系统根据作业任务的整体规划，将作业任务分解，并把分解出的每一个任务，下发分配给相应的机器人，
从而实现协同工作。但是，这种静态下发作业任务的方式，机器人的执行效率较低。

[0004] 为此，中国发明专利CN 102831319 A公开了一种细粒度的多机器人协作系统任务分配算法，将现实生活中的声望应用于机器人协作系统中，通过机器人自身或者是联盟等
的声望值来决定任务的分配，可以将不同的任务合理的分配给相应具有最高声望的机器
人，提高了任务完成的效率；并且，结合细粒度时间模型，通过周期时间的约束，针对一些任
务撤销、机器人失效等突发状况，可以及时的做出调度，提高了整个系统的鲁棒性和容错
度。但是，上述技术方案还存在以下问题：

[0005] 1.作业任务分配算法比较复杂，造成系统效率低。

[0006] 2.任务分配是机器人之间相互委托实现的，当机器人出现严重故障时，无法发出委托指令，造成作业任务不能有效执行。

[0007] 有鉴于此，急需对现有的机器人作业任务分配方法进行改进，以简化算法，提高效率，并确保作业任务有效执行。

发明内容

[0008] 针对上述缺陷，本发明所要解决的技术问题在于提供一种移动机器人的作业任务动态调度下发系统及方法，以解决现有技术，任务分配算法复杂、效率低，作业任务不能有
效执行的问题。

[0009] 为此，本发明提供了一种移动机器人的作业任务动态调度下发方法，包括以下步骤：

[0010] 将机器人的作业任务，根据任务种类分组为若干个任务组并生成任务列表，且所述作业任务的数据结构以有向图的形式表示；每个任务组中包含有若干个作业任务，且所
述作业任务分别通过组内有向边连接，所述组内有向边用于表示相连的两个作业任务执行
的先后依赖关系；不同的任务组中的作业任务通过组间有向边连接形成总任务有向图，所
述组间有向边用于表示任务组之间相连的两个作业任务执行的先后依赖关系；

[0011] 根据机器人空闲情况，以一个任务组作为最小单元分配给相应的机器人；

[0012] 根据作业任务完成情况实时更新作业任务的任务状态，并通过将存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务，对作业任务进行动态调度，且将所
述上级作业任务的任务状态修改为已完成。

[0013] 在上述方法中，优选地，存在依赖关系的两个作业任务，如果后级作业任务在规定时间内未更新任务状态为已完成，则自动对作业任务进行动态调度。

[0014] 在上述方法中，优选地，对作业任务进行动态调度的方式为：在上级任务组中增一个新作业任务，并将所述新作业任务的任务状态设置为已完成，将存在依赖关系的下级作
业任务的上级任务指向所述新作业任务。

[0015] 在上述方法中，优选地，对作业任务进行动态调度的方式为：创建一个新任务组，并在所述新任务组中增至少一个新作业任务，将其中的一个新作业任务的依赖关系指向上
级任务组中相应的作业任务。

[0016] 在上述方法中，优选地，存在依赖关系的两个任务组中，上级任务组中的最后的一个作业任务指向下级任务组中的第一个作业任务。

[0017] 本发明还提供了一种移动机器人的作业任务动态调度下发系统，包括：

[0018] 任务列表生成单元，用于根据任务种类分组为若干个任务组并生成任务列表，所述作业任务的数据结构以有向图的形式表示；每个任务组中包含有若干个作业任务，且所
述作业任务分别通过组内有向边连接，所述组内有向边用于表示相连的两个作业任务执行
的先后依赖关系；不同的任务组中的作业任务通过组间有向边连接形成总任务有向图，所
述组间有向边用于表示任务组之间相连的两个作业任务执行的先后依赖关系；

[0019] 任务状态更新单元，用于根据作业任务的完成情况实时更新任务状态；

[0020] 任务状态修改单元，用于将存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务；

[0021] 调度单元，用于根据机器人空闲情况，以一个任务组作为最小单元分配给相应的机器人，自动对作业任务进行动态调度。

[0022] 在上述系统中，根据存在依赖关系的两个作业任务中，后级作业任务在规定时间内未更新任务状态为已完成，所述调度单元自动对作业任务进行动态调度。

[0023] 在上述系统中，还包括：

[0024] 新任务增加单元，用于在任务组中增一个新作业任务，并通过所述任务状态修改单元将所述新作业任务的任务状态设置为已完成，通过所述任务列表生成单元将存在依赖
关系的下级作业任务指向所述新作业任务。

[0025] 在上述系统中，所述新任务增加单元创建一个新任务组，并在所述增一个所述新作业任务。

[0026] 由上述技术方案可知，本发明提供的移动机器人的作业任务动态调度下发系统及方法，解决了现有技术的算法复杂、效率低，作业任务不能有效执行的问题。与现有技术相
比，本发明具有以下有益效果：

[0027] 将机器人的作业任务，根据任务种类分组为若干个任务组并生成任务列表，且作业任务的数据结构以有向图的形式表示，并以有向边表示相连的两个作业任务执行的先后
依赖关系，通过将存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务，
对作业任务进行动态调度，算法简单，效率高，且可以对作业任务进行灵活地调度。

[0028] 另外，在本发明的优选方案中，如果后级作业任务在规定时间内未更新任务状态为已完成，则可以通过增加新任务或增加新任务组的方式执行后级任务，确保了作业任务
的有效执行。

附图说明

[0029] 为了更清楚地说明本发明的实施例或现有技术中的技术方案，下面将对本发明实施例或现有技术描述中所需要使用的附图做出简单地介绍和说明。显而易见地，下面描述
中的附图仅仅是本发明的部分实施例，对于本领域普通技术人员来讲，在不付出创造性劳
动的前提下，还可以根据这些附图获得其他的附图。

[0030] 图1为本发明提供的一种移动机器人的作业任务动态调度下发方法流程图；

[0031] 图2为本发明中一种任务组有向图的实施例示意图；

[0032] 图3为本发明中一种总任务有向图的实施例示意图；

[0033] 图4为本发明中一种任务组有向图的实施例修改指向关系的示意图；

[0034] 图5为本发明提供的一种移动机器人的作业任务动态调度下发系统示意图。

具体实施方式

[0035] 下面将结合本发明实施例附图，对本发明实施例的技术方案进行清楚、完整地描述，显然，以下所描述的实施例，仅仅是本发明的一部分实施例，而不是全部的实施例。基于
本发明的实施例，本领域普通技术人员在没有做出创造性劳动的前提下，所获得的所有其
他实施例，都属于本发明保护的范围。

[0036] 本发明的实现原理是：

[0037] 将机器人的作业任务，根据任务种类分组为若干个任务组并生成任务列表，且作业任务的数据结构以有向图的形式表示；

[0038] 根据作业任务完成情况实时更新作业任务的任务状态，并通过将存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务，对作业任务进行动态调度。

[0039] 本发明提供的方案，算法简单，且可以对机器人的作业灵活地进行动态调度。

[0040] 为了对本发明的技术方案和实现方式做出更清楚地解释和说明，以下介绍实现本发明技术方案的几个优选的具体实施例。

[0041] 需要说明的是，本文中“内、外”、“前、后”及“左、右”等方位词是以产品使用状态为基准对象进行的表述，显然，相应方位词的使用对本方案的保护范围并非构成限制。

[0042] 请参见图1，图1为本发明提供的一种移动机器人的作业任务动态调度下发方法的流程图，该方法包括以下步骤：

[0043] 步骤110，将机器人的作业任务，根据任务种类分组为若干个任务组并生成任务列表。

[0044] 作业任务的数据结构以有向图的形式表示，每个任务组中包含有若干个作业任务，且作业任务分别通过组内有向边(有向图的边)连接形成任务组有向图，组内有向边用
于表示相连的两个作业任务执行的先后依赖关系。

[0045] 例如，物业清洁机器人的作业任务有扫地任务，除尘任务以及清洗任务等。将若干个扫地任务分组为任务组A，将若干个除尘任务分组为任务组B，将若干个清洗任务分组为
任务组C。

[0046] 任务组A中有5个作业任务，分别是扫地A1区域的作业任务A1，扫地A2区域的作业任务A2，扫地A3区域的作业任务A3，扫地A4区域的作业任务A4，扫地A5区域的作业任务A5；
除尘任务组B中，除尘A1区域的作业任务为B1，除尘A2区域的作业任务为B2，除尘A3区域的
作业任务为B3；清洗任务组C中，清洗A1区域的作业任务为C1，清洗A2区域的作业任务为C2，
清洗A3区域的作业任务为C3，清洗A4区域的作业任务为C4等。

[0047] 由此，生成如下的任务列表。

[0048] 任务列表LIST

[0049] 任务组A

[0050] {任务A1，任务A2，任务A3，任务A4，任务A5，……}

[0051] 任务组B

[0052] {任务B1，任务B2，任务B3，……}

[0053] 任务组C

[0054] {任务C1，任务C2，任务C3，任务C4，……}。

[0055] 任务列表以任务组排序，且每个任务组中，以作业任务排序。

[0056] 任务组有向图G1如图2所示，节点A1，A2，A3，A4，A5表示不同的作业任务，连接节点A1，A2的有向边EA1(A1，A2)表示相连的两个作业任务A1，A2执行的先后依赖关系，即作业任
务A2依赖于作业任务A1，只有当作业任务A1执行完成后才可以开始执行作业任务A2。

[0057] 同样地，有向边EA2(A2，A3)，EA3(A3，A4)，EA4(A4，A5)分别表示作业任务A2，A3，A4，A5之间作业任务执行的先后依赖关系。

[0058] 不同的任务组中的作业任务通过组间有向边(有向图的边)连接形成总任务有向图，组间有向边用于表示任务组之间相连的两个作业任务执行的先后依赖关系。

[0059] 组内有向边和组间有向边可统称为有向图的边。

[0060] 对于不同的任务组A、B而言，作业任务的先后依赖关系为：B1依赖于A5的完成，C1依赖于B3的完成。

[0061] 总任务有向图如图3所示，三个任务组A、B和C分别构成任务组有向图G1、G2和G3，任务组有向图G1、G2通过组间有向边EG1(G1、G2)连接，组间有向边EG1(G1、G2)表示任务组
G2中的第一个作业任务B1依赖于任务组G1中最后一个作业任务A5的完成。

[0062] 通常情况下，后一个任务组有向图中的第一个作业任务依赖于前一个任务组有向图中的最后一个作业任务的完成。但是，不排除前一个任务组有向图中的最后一个作业任
务完成后，跳过后一个任务组有向图中的第一个作业任务，执行任务组内的其他作业任务
的情况，例如跳过任务C‑1，而执行任务C‑2；或者，跳过前一个任务组有向图中的最后一个
作业任务，执行后一个任务组中的相应任务的情况，例如执行完任务B‑2后，跳过任务B‑3，
而执行任务C‑1。具体作业任务的执行顺序或者依赖关系，可以根据作业任务故障，或者人
工改变等实际情况进行设定，根据设定，调整或规划有向图的边的指向关系即可。

[0063] 步骤120，根据机器人空闲情况，以一个任务组作为最小单元分配给相应的机器人。

[0064] 一个机器人可以接收多个任务组。

[0065] 当区域内有多台机器人时，不同的任务组也可以分配给多个机器人进行协同工作。

[0066] 当任务组有变化，包括优先级的变更，或后续任务的取消等等，通过改变任务的依赖关系来进行任务组之间的连接，从而进行逻辑上的删除操作。

[0067] 以删除任务组举例，改变了该任务组的连接，也就是说，这个任务组在系统中存在，但没有任何的前序任务或者后续任务，是一个孤立的节点。

[0068] 步骤130，根据作业任务完成情况实时更新作业任务的任务状态，任务状态分为开始、进行中和已完成三种状态。通过将存在依赖关系的下级作业任务修改为指向该作业任
务的上级作业任务，对作业任务进行动态调度，进行动态调度前，需要将上级作业任务的任
务状态修改为已完成。

[0069] 当其中一个作业任务的任务状态在规定时间内未能由进行中改变为已完成时，说明该作业任务的执行出现了故障，可能是机器人本身的故障，也可能是作业环境有问题，出
现这种情况时，系统将与之存在依赖关系的下级任务指向该任务的上级作业任务状态为已
完成的任务，从而解决下级任务无法执行的问题。

[0070] 本发明方法中，可以通过两种方式实现步骤130中作业任务的动态调度。

[0071] 方式一：

[0072] 在该作业任务的任务组中增一个新作业任务，并将其状态设置为已完成，然后将与该作业任务存在依赖关系的下级作业任务指向新作业任务。可以在出现问题的任务后面
插入新作业任务，也可以在该任务组的最后插入新作业任务。

[0073] 例如以下的实施例中，任务组B的任务B3无法进行，或者尝试多次后失败，任务组C的任务C1依赖这个任务B3的完成，只有当B3的任务执行完成后任务C1才能开始。

[0074] 系统生成的原始任务列表如下：

[0075] 任务列表LIST

[0076] 任务组A

[0077] {任务A1，任务A2，任务A3，任务A4}

[0078] 任务组B

[0079] {任务B1，任务B2，任务B3}

[0080] 任务组C

[0081] {任务C1，任务C2}。

[0082] 对于此问题，系统发现任务B3在规定的时间内，任务状态没有更新为已完成，于是在任务组B中出现问题的作业任务B3之后增加一个新任务B4，并将新任务B4的任务状态设
置为已完成，这样，由于新任务B4的任务状态是已完成，于是任务C1就可以执行了。修改后
的任务列表如下：

[0083] 任务列表LIST

[0084] 任务组A

[0085] {任务A1，任务A2，任务A3，任务A4}

[0086] 任务组B

[0087]

[0088] 方式二：

[0089] 解决上面问题的第二种方式是创建一个新的任务组D，并增至少一个新任务D1，将其中一人新作业任务的依赖关系指向上级任务组中相应的作业任务B2。修改后的任务列表
如下：

[0090] 任务列表LIST

[0091] 任务组A

[0092] {任务A‑1，任务A‑2，任务A‑3，任务A‑4}

[0093] 任务组B

[0094]

[0095] 上述两种方式，第一种方式是针对后级任务组不是强依赖于上级作业任务组的情况，而第二种情况是后级任务组强依赖于上级作业任务组的情况。

[0096] 例如，任务组C强依赖任务组B，任务组B是“呼叫电梯，机器人等待电梯等一些列任务”，任务组C是“机器人进入电梯，系统控制电梯到达xx楼层等”。但是，由于任务组B中的某
一个任务，比如“呼叫电梯失败”。导致机器人没办法乘坐电梯。但此时机器人并没有异常，
可以正常工作，可以继续清扫同一楼层的某个区域。于是增加任务组D“行走到xx点，清扫区
域YY”等一系列任务，这样，当机器人完成作业任务B‑2后，就会跳过作业任务B‑3和作业任
务组C，而去执行任务组D中的作业任务。

[0097] 本发明中，通过邻接矩阵表示有向图，作业任务的动态调度，通过修改邻接矩阵修改有向边的指向关系，近而改变作业任务的依赖关系。

[0098] 基于上述方法，本发明提供的方案，也可以根据要求灵活地进行动态调度，而不限于只是在任务无法完成时才进行调度。

[0099] 例如，系统根据实际作业任务的完成情况，或者临时增加的新任务时，通过修改组内有向边的指向，或者修改组间有向边的指向而动态调度作业任务。

[0100] 上述修改，同样可以通过增加组内任务，或者增加任务组的方式实现。例如图4所示的实施例中，通过删除原有向边E(A3、A4)，增加有向边E(A3、A5)，从而全程任务A3完成后
直接执行任务A5，而不再执行任务A4。

[0101] 上述方法同样适用于跨任务组的灵活调度。

[0102] 本发明中，可以在终端上显示任务有向图，通过手动修改有向边的指引关系实现作业任务的灵活调度。

[0103] 在以上方法的基础上，本发明还提供了一种移动机器人作业任务动态调度下发系统。

[0104] 如图5所示，该系统包括任务列表生成单元10、任务状态更新单元20、任务状态修改单元30、新任务增加单元40和调度单元50。

[0105] 任务列表生成单元10用于根据任务种类分组为若干个任务组并生成任务列表，其中作业任务的数据结构以有向图的形式表示；每个任务组中包含有若干个作业任务，同一
个任务组中各作业任务分别通过组内有向边连接，组内有向边用于表示相连的两个作业任
务执行的先后依赖关系；不同的任务组中的作业任务通过组间有向边连接形成总任务有向
图，组间有向边用于表示任务组之间相连的两个作业任务执行的先后依赖关系。

[0106] 任务状态更新单元20用于根据作业任务的完成情况实时更新任务状态。

[0107] 任务状态修改单元30用于将存在依赖关系的下级作业任务修改为指向该作业任务的上级作业任务。

[0108] 新任务增加单元40用于在任务组中增一个新作业任务，并通过任务状态修改单元30将新作业任务的任务状态设置为已完成，通过任务列表生成单元10将存在依赖关系的下
级作业任务指向新作业任务。

[0109] 新任务增加单元40还可以创建一个新任务组，并在所述新任务组中增加一个新作业任务，然后，再通过任务状态修改单元30将新作业任务的任务状态设置为已完成，通过任
务列表生成单元10将存在依赖关系的下级作业任务指向新作业任务。

[0110] 调度单元50用于根据机器人空闲情况，以一个任务组作为最小单元分配给相应的机器人，自动对作业任务进行动态调度。

[0111] 综合以上具体实施例的描述，本发明提供的移动机器人的作业任务动态调度下发系统及方法，与现有技术相比，具有如下优点：

[0112] 首先，将机器人的作业任务，根据任务种类分组为若干个任务组并生成任务列表，其中作业任务的数据结构以有向图的形式表示。机器人的作业任务调度通过任务列表进
行，算法简单，效率高。并且，可以灵活地修改任务列表，达到对机器人作业任务的动态调
度。

[0113] 第二、对于存在依赖关系的两个作业任务，如果后级作业任务在规定时间内未更新任务状态为已完成，则自动对作业任务进行动态调度，保证了作业任务能够有效执行，避
免出现由于上级任务无法完成，致使下级任务不能开始的情况。

[0114] 第三、通过自动或手动修改有向图的指引关系可以实现对作业任务的灵活调度，使用方便。

[0115] 最后，还需要说明的是，在本文中使用的术语"包括"、"包含"或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括
那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或
者设备所固有的要素。在没有更多限制的情况下，由语句"包括一个…"限定的要素，并不排
除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

[0116] 本发明并不局限于上述最佳实施方式，任何人应该得知在本发明的启示下做出的结构变化，凡是与本发明具有相同或相近的技术方案，均落入本发明的保护范围之内。