如何在通信开销高时选择最佳机器人？

如果机器人网络断开，则传感器网络可用于连接一些机器人。传感器和机器人采用不同的可用传输范围，都可以参与同一洪泛协议，机器人可能使用较小的重传退避等待时间，使得它们在重传方面能够优先于传感器。如果在时间用完之前，特定传感器或机器人的传输区域（其邻居集）未被所有接收传输所覆盖，则节点重传该消息。简单起见，我们这里假定机器人网络处于连通状态，并只对机器人-机器人通信进行深入讨论。

本节中描述的机器人-机器人协同方案与组网机器人服务的特定环境没有关系。对于我们来说，这种兴趣环境包括作为MRS扩展形式的无线传感器与机器人网络（WSRN）。无线传感器与机器人网络包括由无线介质连接的传感器和机器人，主要执行物理世界分布式感知、感知数据处理功能，并作用于感知事件（如图9-3所示）。我们将使用这种场景来说明我们的问题。在许多情况下，接收报告的机器人本身可能就是最佳响应候选机器人。但是，远程机器人可能收到该报告。事件发生（如火灾或传感器失效）后，传感器检测事件，并将信息路由给附近的任意机器人。但是，它可能不是最近的机器人。

图9-3 由于存在空穴区，从传感器到非最近执行器报告事件

在图9-3中，R1与R4和R2进行协商，并从R4处获知机器人R3最靠近事件。在图9-3的实例中，由于在事件和最近的机器人R1之间存在着一个传感器空穴区，因而R3接收报告。R1具有执行功能，但传感器无法直接向R1报告事件。R3启动招标过程，找到最近的机器人R1，然后将任务分配给它。

局部和分布式解决方案使用在所有机器人中间传播所有决策和规划职责。这里，我们考虑多跳单位圆盘图（UDG）场景。在这种场景中，通信图是不完全的。机器人仅使用局部可用信息来做出决策。可扩展性好、容错性强是主要优点。提出的解决方案通常接近最优解。但是，基于局部信息做出的决策有时是高度次优的。

论文（Melodia et al.，2007）基于简单竞拍协议（Simple Auction Protocol，SAP），描述了一种执行器-执行器协同解决方案（针对单机器人单任务分配场景）。拍卖机器人向所有机器人洪泛事件信息，每个执行器（机器人）向发起执行器回送能够提供的服务和执行任务的成本信息（采用独立路由任务）。能够为给定区域提供服务的机器人发送投标信息。如果采用盲洪泛，则每个机器人首次接收到该消息后，即进行重传，并在以后忽略该消息。在智能洪泛（见第2章）中，只有那些来自于骨干网的节点，且仅当它们拥有需要消息的邻居时，才传输消息。对于大型机器人网络来说，该协议会在选择最佳机器人时，会导致不可接受的延迟，而最佳响应机器人有望在事件附近。

即使对于SAP来说，可以将机器人选择限制在某些局部区域（Mezei et al.，提交待发表）。参考文献（Mezei et al.，提交待发表）进一步提出了一种称为竞拍融合的、基于市场范式的局部解决方案。这种招标过程扩展到相邻机器人，直到在机器人的k跳邻域内再也无法进行优化，它分析了其他远程机器人提供的服务能否超过该机器人知道的最佳服务。如果不能，则它停止搜索过程，使用可能是它所拥有的最佳推荐来响应其“父”机器人。使用构建树，而不是使用独立路由任务来回送报告消息。协议具有树“扩张”和树“收缩”阶段。树扩张通过生成一棵根节点位于R0的树，来从采集机器人R0处开始（如图9-4所示）。重传生成一棵响应树。每个重传节点将其父机器人的ID包含在消息中，使得机器人能够以局部方式确定它们是不是生成树中的叶子。需要注意的是，每个节点仅选择一个父节点，以防止接收到多份投标信息（如R8仅加入到R9中，R4仅加入到R2中）。如果机器人无法传输投标消息，或者无法监听到其他机器人正在将它们列为父机器人，则这些机器人变成树叶。树叶节点开始采用它们所知的最佳成本，向机器人回送响应信息。这实际上是竞拍融合过程，从而减少了招标阶段的消息数。每个中间节点等待来自于所有邻居的消息，这些消息宣称它是一个父节点，从而成为一个局部采集器。收到这些消息后，它们选择最佳成本，并向采集器进行报告。末端采集器决定哪个机器人是执行所需动作的最佳机器人，并将决策路由到该机器人。在图9-4的实例中，机器人R3、R5、R6、R7和R8是生成树的树叶，它们将投标信息发送给其父节点。R9返回消息到其父节点R0，其自己的投标2作为它知道的最佳距离。同样，R4将其投标7返回给R2，R2将其自己的投标5返回给R0。R1将R7作为最佳投标者返回给其父节点R0。然后，根节点（R0）根据收到的分别来自于R1、R2、R3和R9的4份报价材料，选择最佳投标者（在这种情形中为R7），并沿着生成路径R0-R1-R7，将任务分配给R7。竞拍融合协议将被指定为简单竞拍融合协议（Simple Auction Aggregation Protocol，SAAP）。在有限洪泛（只接收采集器k跳之内的邻居）的情形中，它被称为k-SAAP（Mezei et al.，提交待发表）。k-SAAP和k-SAP之间（类似于SAP和SAAP之间）的区别是每次招标在中间节点处融合，而不是将所有招标路由回采集器机器人。(www.xing528.com)

图9-4 用于选择最佳机器人的竞拍融合协议

通过提供为每个机器人提供重传决策自主性，可以对该算法进行深度精炼。在k-SAAP中，仅当接收机器人与招标机器人之间的距离小于k跳时，接收机器人将进行重传。k跳竞拍融合协议（k-AAP）（Mezei et al.，提交待发表）采用当前机器人周围的k跳邻域。假定每个机器人知道k跳之内所有相邻机器人的位置、成本和可用性。一种简单方法是周期性将其局部信息（包括其k-1跳邻居的状态）发送给邻居（“问候”消息），或将其添加到数据消息中。在k-SAAP（Mezei et al.，提交待发表）中，接收招标消息的机器人（和与从招标机器人到它的路径上前一个发送方有关的最佳学习成本C）将C与它的k跳邻居的服务提供成本进行比较。仅当至少它自身的一个k跳邻居具有小于C的成本，它将重传消息。否则，它不重传消息，并通过向搜索路径上的父节点，返回一条响应消息执行竞拍融合过程。在最简单的版本——0-AAP协议（k=0）中，接收机器人宣称自己是所选机器人，与0跳知识对应（即根本没有知识）。在1-AAP协议中，如果它的任一邻居具有较低成本，则采集机器人R0将进行重传。在图9-4中，R7是R0的2跳邻居，它具有较低的成本，然后R0在2-AAP版本中进行重传。接收到来自于R0、R2、R3的投标消息后，R9将不进行重传，而R1将进行重传，因为R7是其单跳邻居。每个重传节点将包含它所知道的最低成本消息。

在特殊情况下，当成本指标等于距离（从给定机器人到事件）时，可以采用另一种专门算法。我们将它表示为具有围绕事件面遍历的指向事件路由（RFTTF）算法。实际上，它在算法方面与第4章中描述的面遍历算法等价。在图9-5的实例中，e为事件位置。RTF算法在采集机器人V接收到任务开始启动。RTF采用机器人网络从V路由到事件位置e。路由在遍历完包含e的面后结束。在图9-5中，面是V→A→B→C→D→F→G→A。面遍历形成一个环路，它能够被局部检测到。环路中的第一个节点（图9-5中的A）描述了最佳（最近）机器人（实例中的B）。面遍历需要用到平面图，如UDG的Gabriel图，第4章对它进行了介绍。

图9-5 UDG的Gabriel图上的面遍历算法