动态任务分配：机器人分配任务的实现方法

在一些应用中，需要在机器人之间动态分配任务。例如，在40个机器人的搜索和救援任务中，首选的任务分配方案是30个机器人搜索环境，2个机器人标记资源，8个机器人维护一个通信网络（Ogren et al.，2002）。一般情况下，假定为机器人p_i分配第i项任务，且仅为每个机器人分配一项任务。

参考文献（McLurkin and Yamins，2005）提出了4种分布式算法，用于为子组分配同构机器人群，每个子组执行不同任务，以满足指定的全局任务分配。在简单的随机选择算法中，每个机器人以某个概率选择一项给定任务，该概率与目标分配中的任务子组相对大小成正比。在上面的实例中，每个节点分别以概率3/4、1/20、1/5来选择任务。随机选择算法不需要机器人之间进行通信，可以立即完成。但是，如果群的规模比较小，则该算法无法实现可以接受的目标分配概率比较高。

其次，极端通信算法是所涉及通信开销的另一个极限值。总之，机器人洪泛必要信息，包括它们的ID和任务需求，直到所有机器人学习所有做出与集中式算法相同决策需要的信息。可以按照机器人ID排序来分配任务。更准确地说，每个机器人广播一条消息，该消息包含了机器人的ID和接收到的来自于邻居的中继消息。这些消息从每个机器人传播到整个网络。因此，每个机器人能够构建一个群中所有其他机器人的完整列表。假设给定的目标分配矢量是{p₁，p₂，…，p_m}，机器人总数为n。每个机器人确定它在ID列表中的相对位置，并选择p_i，使得p₁+…+p_i-1≤X<p₁+…+p_i。该算法运行速率快，且能够输出精确的解决方案，因为对于每个机器人来说，所有机器人的ID都是可用的。但是，该算法需要进行大量机器人之间的通信。(www.xing528.com)

第三，卡经销商算法将任务分配分解为一系列阶段。波传播用于在每一轮中学习任务主导者（选择下一项任务的机器人）。在给定轮中，所选机器人是具有最小ID且无法确定其任务的机器人。为了学习那个机器人，每个机器人（只有那些还没有被“完全”分配任务的机器人）向其邻居重复广播它的ID，直至它接收到一条类似的广播消息，它是由具有较小ID的机器人发起的。它转向重传这个较小的ID。不竞争下一项任务的机器人，将只重传接收消息和最小ID。该过程持续进行，直至网络中的最小ID是唯一剩余的ID，且所有机器人都知道它。

最后，在树重新着色算法中，应用波传播只学习一个主导者（在一轮内），生成一棵扩展树，其根节点为主导者，它确定每个机器人的角色，并将角色信息发送给它们。更准确地说，在一轮波传播中，具有最小ID的节点成为主导者。它发起一次洪泛（每个接收机器人将只重传一次该消息）来构建网络的生成树，根节点为网络自身。洪泛包含在第2章中。每个机器人建立一个指向父机器人的指针，父机器人接收洪泛消息的第一个拷贝。在这种方式中，所有机器人加入一个根节点为主导者的单树中。树根（主导者）学习所有任务，做出决策，采用沿着构建的通信方式，将每个机器人的角色（任务）发送出去。为了实现合理的分配，树的内部节点应当存储其下行节点（机器人）的编号。通过从树叶开始、持续指向树根的反射广播来发现。树叶（第1级机器人）向第2级机器人发送消息，第2级机器人学习其子机器人的数目，并将信息转发给其父机器人。每个内部节点计算子节点计数总和，来寻找自身子树中的节点计数。采用这种计数器，可以对任务列表进行分配，树根可以通过向其子树传送适当数目的任务，来启动任务分配。该过程使用对应的任务分配列表，从每个子节点开始递归进行。分配消息沿着从源到网络中所有机器人的生成树进行传播。通信开销比前两种解决方案都低。