多机器人系统中的任务分配技术

一些文献和几篇综述论文对多机器人系统（Multirobot system，MRS）进行了深入的研究，一些书的章节也涉及该主题（如参考文献（Dudek et al.，2002；Farinelli et al.，2004；Parker et al.，2008））。大多数与MRS有关的论文焦点在于一般的通信、协同和合作。组网机器人是MRS的一种扩展形式，在这种场景中，实体之间的通信是协同和合作的基础，因而是网络的核心角色（Bekey and Yuh，2008；Ku-mar et al.，2008）。组网机器人的应用包括执行运动和操作任务的耦合，执行勘探、映射、搜索和侦察任务或游戏（如机器人足球）时的协同。组网机器人还可以执行需要协同的独立任务（如钻孔或焊接）。

图9-2 两个并发事件和两种可能配置的监控区域

我们也使用无线传感器与机器人网络（Wireless Sensor and Robot Network，WS-RN）这个术语。它涉及机器人在传感器网络中用作移动执行器时的特殊情况。如图9-2所示，它给出了传感器、4个机器人和两个事件。无线传感器与机器人网络可使用实时响应约束条件、传感器-传感器、传感器-机器人和机器人-机器人协同来表征。通过将数据从传感器传输到机器人，传感器-机器人协同能够提供事件信息。移动机器人提出了更为严峻的挑战，因为传感器无法轻易维护接收报告信息的机器人位置。当这些信息不存在时，传感器需要洪泛事件信息，这样会通过大量无用通信来耗尽能量。为了降低能耗，机器人需要通过周期性向特定区域或方向发送消息，先应式维护其位置信息（见第8章），使得传感器能够在事件发生时，实现高效报告。这是一项非常困难的任务。在参考文献（Selvaradjou et al.，2006）中，通过假定将区域划分为网格来解决该问题，在每个网格中至少有一个执行器（因而大量机器人是可用的，且位于任一可能发生的事件附近），且传感器网格主导（“代理”）被进一步组织成簇。(www.xing528.com)

WSAN运行在事件感知、数据通信和执行器动作的循环中。通常将移动自控执行器称为机器人。在WSAN中，一旦检测到事件，并从传感器报告给执行器（机器人），执行器通过协同来重构事件，估计其特性，就行动方案和如何实施联合做出决策。整个过程是一个执行器-执行器协同实例（Akyildiz and Kasimoglu，2004）。当就行动达成协议时，执行器-执行器协同中的基本问题是确定那些执行器来执行这些行动，使得执行器总体性能最大化。在WSAN中，该问题被称为任务分配问题（Melodia et al.，2007）。

假定WSAN中的每个事件被报告给一个机器人。当存在多个事件（可能是并发的）时，几项任务在机器人组成员中间进行分发。例如，在火灾监控场景中，检测到火灾的传感器将信息路由给机器人，机器人需要决定那个机器人负责灭火。有时，任务需要多个机器人才能成功完成（如较大的火灾）。当存在多个事件（如多个地点发生火灾或多个传感器部署）时，并发性和时间约束条件可能决定行动方案。如果没有时限，所有多事件问题可以看做是单事件问题的迭代版本。区别在于这些事件是事先已知的，还是不可预测的。例如，在图9-2中，机器人R4在对事件e1响应完后，可以接着响应事件e2。或者，它仅处理事件e2，机器人R3负责响应事件e1。总之，针对每次有/无严格时限的事件执行，存在着单/多任务，需要单/多机器人实施行动。

这些一般性问题陈述考虑到许多具体实例。几乎不存在解决相关问题的通用方法。取决于决策过程，任务分配解决方案可以划分为集中式、局部和基于市场的解决方案。在集中式解决方案中，决策是在采集完所有必要信息，由单个机器人或汇聚节点（基站）做出的。在局部解决方案中，每个机器人的决策是基于其直接邻域和输入请求中的可用信息做出的。与集中式解决方案相比，局部解决方案的计算开销和通信开销低，可扩展性强，容错性好，且响应速度快。但是，由于信息非常有限，因而很难在局部解决方案中找到最优决策。在基于市场的分布式解决方案中，机器人与特定数目的其他机器人在较小或较大邻域内进行通信，以协商解决局部做出决策中的行动缺乏或行动过度的问题。目标是使得单个机器人和整个机器人网络都具有更好的响应效率。在基于市场的解决方案中，机器人作为自由代理开展工作，实现单个机器人效益最大化。机器人可以通过协商或竞拍的方式来分配任务，这是决策的主要工具。包含在竞拍过程的通信可能会超过严格的邻域信息，可以折衷为一种半局部行为。