最佳机器人选择策略在可忽略通信开销条件下的应用

针对单事件或多事件、单机器人或多机器人、每个机器人单任务或多任务的大多数现有多机器人协同解决方案都是集中式的。某个机器人或中心实体从其他机器人处采集所有的信息并做出决策。很少考虑多跳机器人网络中信息采集时的通信开销。由于可以假定通信成本忽略不计，因而通过使用较小成本采集所有必要信息，决策者理论上可以做出一个最优决策。可以间接（由于未给出所用通信协议的细节信息）地采用完全图（其中每个机器人位于其他机器人的通信距离内）。通常，集中式解决方案将协同通信问题定义为一个ILP问题。集中式解决方案的主要优点是理论上可以找到最佳解决方案。但是，集中式解决方案具有计算和通信开销高、可扩展性差、响应速度慢等特点。同时，实际通信开销可忽略不计，尤其是对于大型机器人网络来说。如果不是完全图，机器人如何进行通信也不太清楚。如果主导机器人发生任何故障，则集中式解决方案容错性也比较差。

对于静态执行器来说，参考文献（Melodia et al.，2007）提出了一种混合整数非线性规划（Mixed Integer Nonlinear Program，MINLP）表达方式，用于在满足行动完成时限约束条件的前提下，实现选择用于执行某项任务的（多）机器人的平均剩余能量最大化。参考文献（Shah and Meng，2007）假定存在一个全局单元，它接收每项任务中每个机器人的工作状态更新消息（开始、完成、故障或超时）。如果某个机器人在完成分配的任务时需要帮助，则全局单元能够选择一个或多个机器人进行协助。选择基于竞拍方法，充分考虑机器人能力、与当前任务位置的距离、机器人可用性和机器人局部队列中的任务数等因素。论文（Selvaradjou et al.，2006）表明，为了实现机器人运动总距离最小，使用时限和能量约束条件，寻找最佳分配（单）机器人分配方案是NP完全问题。它们用MINLP来表示。这种表达方式采用事件和任务的先验知识，为每个机器人寻找一条访问事件的路线。他们还提出基于区域间和区域内的局部启发式方案，用于为适当事件寻找近似最优的机器人调度方案。在区域内调度方案中，代理传感器节点为区域内的机器人，计算最优调度方案。在区域间调度方案中，（代理所在簇的）CH为所有位于其簇内的机器人，寻找最优调度方案。提出的启发式方案用于采用最早期限，为那些能够在规定期限内执行任务、且具有足够能量的最近机器人分配任务。

不存在单一事件分配多个机器人和多项任务分配给一个机器人的情况。该问题可看做是最优分配问题的一个实例，参考文献（Gerkey and Mataric，2004）对此进行了详细的描述。它讨论了集中式解决方案。在这种方案中，任务和机器人信息都是在单一位置采集的，由任务数不能超过机器人数。如果机器人数等于任务数，这种场景是一种经典分配问题实例（也称为线性加权和分配问题）。假定移动能耗与运动距离成正比，如果机器人的能量是有限的，则我们的目标是寻找一种分配方案，使得移动总能耗最小（对于所有移动到对应事件的机器人）。执行任务所需能量不在优化函数中，但可以添加进去。该问题可以扩展为具有边界约束条件的分配问题的一个实例，如果总能耗必须限制在每个机器人的能量预算之内。对于具有实时约束条件的任务来说，可以添加时限要求（到达区域所需时间加上执行任务所需时间）。如果任务数超过机器人数，通过将算法应用于按期限排列的任务上，算法可以进行多轮重复，并在每轮中为一个机器人分配一项任务。另一种方法是通过依次对任务进行访问和类似路线的逐事件访问，将多项任务一次分配给一个机器人。最后，甚至可以采用一种贪婪算法来依次分配任务，为每项任务选择一个机器人（在所有可用机器人中）。(www.xing528.com)

迄今为止，文献中的问题表达方式未将因某些机器人能量耗尽而导致的网络性能下降考虑在内。某项给定任务的最佳机器人可能会将对机器人组的能量需求降到最低，但也可能导致自身无力执行其他任务，这可能也会影响到机器人组为传感器提供支撑的能力。因此，需要用到一些负载均衡机制来解决这个问题。最佳机器人可能会通过在机器人中间协商确定，并对目标进行修改，使得第一个机器人能量消耗时间最大化。可能会出现其他一些定义，如机器人网络分区时间，或监测区构成，或不可接受的组反应时间。一种可能的负载均衡策略是修改任意机器人的成本函数，将剩余能量包含在内。当接收到为某事件提供服务的行动请求后，每个机器人B计算d/E，其中d为机器人与事件之间的距离，E为当前剩余能量（或者，可以考虑执行任务后的剩余能量）。满足实时约束条件且能够实现比值最小化的机器人将承担该任务。