0 引言

随着机器人技术的发展，机器人在我们日常生活的应用范围越来越广。多机器人任务分工与协调问题是多机器人协调领域的热点问题，广泛应用于工业、服务、军事等领域，比如多机器人车辆装配、机器人餐厅、多机器人侦察排雷等。多机器人任务分工与协调的目的是使每个机器人都承担一部分任务，并且为每个机器人找到一个任务计划满足任务之间的偏序关系(即，先后顺序关系)，使得机器人完成任务的总代价最小，如时间最少、能耗最少等。通常，任务分工与协调问题可分为两步：首先，将任务分割成几个能被单独执行的子任务；其次，根据每个机器人的性质和需求进行分配^[1-4]。

近年来，学界或工业界提出大量关于多机器人任务分工与协调的方法。Dias等^[5]提出了一种基于市场法的分布式求解方法, 解决了机器人团队中复杂任务的有效分工问题; 但是该方法只是局限于把复杂任务分割为用布尔逻辑算子表示的多个子任务，忽略了对任务进行均等化分割，导致机器人之间存在负载不平衡现象。Zhang等^[6]基于免疫算法和粒子群算法对装配序列规划问题展开研究，首先对这类问题设计命名规则，然后假定几何可行性和一致性约束条件，即目标函数; 虽然该算法能解决任务之间的偏序关系问题，但是却忽略了任务分配过程中负荷不均等的问题。文献[7-8]提出了一种基于Voronoi图的等质量分割方法进行多机器人并行组装，机器人通过使用Voronoi图分割后的小区域内的组装零件质量差异最小化不断调整它们的位置平衡工作量，每个机器人只需完成自己区域内的任务; 虽然该方法分配给每个机器人近似相等的任务，但是不能确保机器人是否能够顺利、高效地到达组装地点执行任务，同时没有明确解释零件之间在组装过程中存在的偏序约束关系。

因此，本文主要针对多机器人任务分工与协调过程中如何考虑任务偏序关系和任务负荷平衡问题，提出一种基于交换树的多机器人任务协调与负荷平衡方法。首先，将带偏序关系约束的多机器人任务分工问题描述为有向赋权图；其次，提出任务协调与负荷平衡两步策略：前者通过改进Dijkstra算法解决多机器人之间任务协调问题，并给出多机器人初始任务分工算法，后者通过交换树竞拍的方法解决机器人之间任务负荷不平衡问题，并给出基于交换树的多机器人负荷平衡算法；最后，通过多机器人机场维修/搬运仿真，验证了方法的有效性。

1 问题描述

假设有一个由N个同构机器人组成的机器人团队，共同执行任务集T:={t₁, t₂, …, t_M}，其中t_i∈T表示一个独立子任务。各个子任务以及子任务之间的关系可以通过一个无向图G_S:=(V_S, E_S)来表示，其中V_S为任务集，即V_S=T，E_S:={(t_i, t_j)|t_i∈V_S, t_j∈V_S}为相邻子任务构成的边集。

为了考虑任务分工过程中子任务之间的偏序关系，通过一个有向图(约束图)G_C:={V_C, E_C}来表示，其中，V_C=V_S，V_C=T，E_C:={(t_i, t_j):=e_ij|t_i≺t_j}为相邻子任务构成的有向边集(或偏序集)^[9-10]，表示任务t_i必须在子任务t_j之前完成，否则就会违背先后关系。另外，给G_C的每一条有向边赋予一定的权值ω_ij(1≤i, j≤M, i≠j)，表明执行任务后执行子任务t_j的代价。

在多机器人执行任务的初始时刻，机器人随机分布于任务的任意可行初始状态，以图 1为例。

假设两个机器人R₀和R₁要共同构建图 1(a)所示的机构，机构中每个小方格表示一个独立子任务t_i，相邻两个方格形成边(t_i, t_j)，在初始时刻，机器人可以任意分布于第一层机构最外围的任意位置，比如，深色方格位置。通过方格之间的连接关系得到无向图G_S，并在此基础上定义了一个如图 1(b)所示的有向赋权图G_C，其中，带箭头的边e_ij(1≤i, j≤M, i≠j)表示机器人构建该机构由下至上，层层搭建的先后顺序关系；权值ω_ij表示机器人搭建完方格t_i后搭建下一个方格t_j的代价；深色节点表示初始时刻R₀和R₁所处的位置。从初始时刻开始，R₀和R₁需要从各自初始位置出发，按照子任务偏序关系，且互不冲突地(不能重复搭建同一个方格)分工协作完成整个机构的搭建工作。多机器人任务分工可以通过集中或分布的方法来实现，常用的方法有A^*算法、D^*算法和Dijkstra算法^[11]等。不考虑机器人工作负荷平衡，会产生如图 2所示的任务分工结果，其中，深色节点表示任务分工后R₀的子任务集，浅色节点则表示R₁的子任务集，可以看出无论从子任务数量上还是任务代价上，R₁明显高于R₀。该任务分工结果导致了机器人之间任务负荷严重不平衡，针对这一现象，本文需要解决任务之间的协调与任务负荷平衡问题。

2 任务协调与负荷平衡方法

本章通过两步策略来实现N个机器人之间的任务协调与负荷平衡。首先，通过改进Dijkstria算法实现对多机器人的初始分工；其次，在不违背先后顺序约束关系的前提下，提出一种基于交换树的竞拍方法来实现多机器人之间的任务平衡。

2.1 满足偏序关系约束的初始任务分工策略

在初始分工过程中，N个机器人分别在无向图G_S中同时运行一个相同的改进Dijkstria算法。与一般Dijkstria算法不同之处在于：我们在一般Dijkstria算法的基础上，通过有向图来检验搜索到的代价最小路径是否违背偏序约束关系，如果违背约束图中的约束关系，则通过嵌套一个A^*算法找到代价最小的路径。算法运行的起点为机器人当前位置，终点为任务集中子任务所处位置。

以图 3为例，假设节点1为机器人R的初始位置，首先，通过Dijkstria算法在图 3(a)无向图G_S中搜索机器人R到其余所有节点的代价最小路径，其中可能会存在违背图 3(b)中所示的有向图G_C偏序关系的路径，比如，图 3(c)表示的是在一般Dijkstra算法下，得到的机器人R到任务节点2的路径图，其中，虚线箭头表示机器人找到的到达节点2的违背有向图图 3(b)中的偏序关系约束的路径“1-3-2”，深色节点2表示违背约束关系的子任务。

为了满足任务之间的偏序关系约束，可以在一般Dijkstria算法的基础上，通过A^*算法搜寻到达违背约束的节点2的最优路线，使得机器人完成该节点处任务所需代价最小。A^*算法是在一个无向图中运行的，但是该无向图并不是最初的无向图，而是在初始无向图的基础上作了局部改变，即，在初始无向图中把违背约束的节点v_i的所有子节点v_k(k=1, 2, …, m)全部删除后，得到一个新的任务集T′:={t₁, t₂, …, t_M-1}，V′_S=T′。再在无向图中把所有去除子节点所对应的边也删除，得到临时边集E′_S，本文把变化后的无向图称为临时无向图G′_S(V′_S, E′_S)。如图 3(d)所示的临时无向图与图 3(a)的无向图相比，已经把违反有向图图 3(b)中约束关系的节点2的子节点4删除，且与节点4相连的所有边也已经删除。在运行A^*算法时，把节点2作为其起始点，终点为机器人初始位置，即节点1，找到的有效路径为“1-2”。不断迭代该过程，直到所有的节点都被遍历完成。当所有的机器人都遍历完所有节点时，通过竞拍的方法对每个机器进行初始任务分工，即，所有机器人竞拍同一节点，竞拍代价最小的机器人获得该节点，不断重复该过程，直到所有节点都有对应的机器人执行。最后，每个机器人都会形成各自的任务集合。具体算法如算法1所示。

算法1   基于改进Dijkstra算法的多机器人初始任务分工算法。

While存在未加入的节点时

 找出路经最短的节点→node

 If该节点不违背约束

  node分配给相关生成树的最近根节点

 else

  删除违背G_C中约束的边

 在G′_S中运行A^*算法

 If找到最短路径

  把该节点分配给相关生成树，并且找到经过该路径的所有节点

 else

  断开到达该节点的所有边

 end If

end If

end While

该算法与一般Dijkstra算法相比，把任务集之间的偏序关系约束充分考虑在内，使得机器人能够按照一定的序列完成任务。图 4(a)为算法实现流程。

2.2 基于交换树的任务负荷平衡策略

完成初始任务分工之后，任务T已经被分给N个机器人，但这种分工往往是不合理的，机器人之间的任务负荷通常会严重不平衡，为此，需要在初始分工基础之上进一步进行任务负荷的再平衡。该算法将在不违背偏序约束关系前提下，即，在2.1节的基础上完善，采用竞拍方式来实现多机器人之间任务负荷的平衡。

经过初始分工后，每个机器人产生了满足偏序约束关系的子任务集合，并以生成树Z_i(i∈1, 2…, n)的形式进行储存。如图 4所示是由图 1所示不规则几何结构的非平衡任务负载条件下多机器人任务分工产生的生成树。为了使机器人R₀与R₁之间的任务负荷达到相对平衡，本文首先根据子任务数量设置每个机器人的任务容量范围δ，然后再设置两个标准，具体如下：第一个准则是各个机器人执行各自初始分工任务集中的任务总代价W_total，即有向图边值和：

$ {W_{{\rm{total}}}} = \sum\limits_{i = 1}^m {{W_i}} $

(1)

其中m表示生成树中节点数。根据任务总代价设置阈值范围γ。第二个准则是各自任务集中的子任务数N，见式(2):

$ {N_{{\rm{total}}}} = \sum\limits_{i = 1}^n i ;i = \left\{ \begin{array}{l} 0,\;\;\;\;i \notin Z\\ 1,\;\;\;\;i \in Z \end{array} \right. $

(2)

其中:n表示节点标号，Z表示当前所在的生成树。给两个标准对应的参数都赋给一个权值，权值的设定需根据实际情况而定，将作为机器人之间存在任务交换的依据。本文根据任务总代价W和子任务数N的加权和Q从生成树中选取需要进行子任务交换的树。加权和计算见式(3):

$ Q = a * \frac{{{W_{{\rm{total}}}}}}{{{W_{\max }} - {W_{\min }}}} + b * \frac{{{N_{{\rm{total}}}}}}{{\sum\limits_{i = 1}^m {{N_{{\rm{total}}}}} }} $

(3)

其中:a和b为常数，分别表示任务总代价与子任务数重要程度的占比。

根据选取的依据找出加权值最小的一个生成树作为最小交换树Z(i)_c，即机器人R_i所对应的生成树，再找出加权值最大的一个生成树作为最大交换树Z(j)_c，从最大交换树Z(j)_c中找出最合适的子任务节点n_k或节点集合N:={n₁, n₂, …, n_c}，加入到最小交换树Z(i)_c中，同时把它们从最大交换树Z(j)_c中删除。重复该过程直至所有生成树的加权和在一个设定的阈值范围内时，则不再进行任务交换。若图 5中的(a)和(b)分别是最小交换树和最大交换树，用于进行节点交换，那么图(b)中用线圈标出的两个节点是分给最小交换树的节点集，最后得到的结果如图 6所示，具体算法如算法2所示。

算法2  基于交换树的多机器人负荷平衡算法。

While

 找到最小交换树

 找到最大交换树

 从最大交换树中找出最优节点i给最小交换树

 节点i给候选树后的代价score

 If score < bestscore

  bestscore →score

  bestnode →i

  newTree→候选树

  oldtree → tree

 end If

 newTree从oldTree中获取bestnode

 Until不存在可交换的树

end While

图 4(b)为完整算法实现流程。

3 仿真实验与分析

本章以双机器人机场搬运货物为例，进行仿真实验来验证方法的有效性和效率。以图 7所示的机场为例，货物分布在跑道、机场联络道和停机坪上，要求机器人先搬运停机坪上的货物，再搬运联络道上的货物，最后搬运跑道上的货物。任务之间的偏序关系通过图 7表示，其中，节点对应10个货物，深色节点表示跑道上的货物，用任务集合{a₁, a₂, a₃}表示，虚线节点表示联络道上的货物，用{t₁, t₂, t₃, t₄}表示，浅色节点表示跑道上的货物，用{r₁, r₂, r₃}表示。节点之间的边值表示货物完成的代价。

假设机器人R₀和R₁的初始位置分别在任务节点1和2附近，机器人与这些节点的距离可忽略不计。在进行均等分工时，机器人的任务容量范围δ设置为6~8，阈值γ为20，a和b各占50%。

首先，将一般Dijkstra算法(即，一个既不带约束也不考虑负载平衡的算法)同改进Dijkstra算法(即，带约束但不考虑平衡的算法)进行对比，结果如图 9所示。参照有向图 8可以看出，在通过一般Dijkstra算法得到的生成树中，节点5是违反约束的点，节点4与节点5之间存在约束关系，只能从节点5到节点4，因此路径1-4-5不存在。通过改进算法后，找到能够到达节点5且不违反约束的最短有效路径1-2-5。证明了该算法能够解决带偏序约束关系的任务问题，但是未考虑机器人之间负载平衡方面，导致图中所示的任务分工不均等现象。

其次，将带任务平衡策略同前面两种不带任务平衡策略的算法进行比较，得到的结果如图 10所示。可以看出，虽然与一般Dijkstra算法相比代价有了一定的提高，但是完全改进算法与改进算法相比，明显两个机器人之间的工作负荷大小差异缩小了大约30%，工作效率提高了至少12%, 验证了负荷平衡算法的有效性。

4 结语

本文提出的基于换树的多机器人任务协调与负荷平衡方法主要解决多机器人之间存在偏序约束的任务分工和协调问题。通过对Dijkstra算法的改进解决了任务之间存在偏序约束的问题，同时通过交换树的方法使得多机器人之间的任务负荷达到基本趋于平衡，提高了任务完成的效率。

在今后研究中，将对负荷平衡算法进一步改进，提高其计算效率；并且设计一种新的约束型任务描述的方法，使得该算法适用范围更广，可以用到机器人实验平台进行验证。