自主移动机器人的分布研究（9.8）

参考文献（McLurkin and Smith，2004）研究了自主移动机器人。问题是在维护其网络连通性的前提下，将一大群机器人分布到兴趣空间，以提高其区域覆盖。该算法的主要思路如下：机器人的移动方向与指向邻居的力矢量和方向相反。边界机器人向前移动。为了防止网络断开和振荡，并保持与两个子节点的连通性，树叶机器人也保持初始区域的覆盖，并在边界机器人移动时，确保附近机器人处于固定状态。

参考文献（McLurkin and Smith，2004）提出了两种分散算法，即分散统一和边界引导分散。这些算法可以交替运行在机器人群上。分散统一是均匀分布机器人，而边界引导分散算法用于引导机器人到达未搜索区域。在分散统一算法中，基本思路是采用边界条件来引导机器人，以限制分散。物理墙和任意两个机器人之间的最大分散距离r_safe可用作边界条件，来协助防止群过于分散和分解为多个不连通部分。每个机器人被定向到远离其c个最近邻居的相对位置{p₁，…，p_c}矢量和的方向。速度矢量的大小为

其中，I_i为指示函数，v_max是最大允许速率。矢量充当虚拟力，引导机器人远离它的c个最近邻居。实验结果表明，采用两个最近邻居（c=2），在实践中效果最好。

边界引导分散算法在探索空间边界上使用机器人，来引导群进入无人占领区。如果所有边界机器人沿着最优路径移动，且将群中剩余机器人“拉”进它们的最终位置，则可以实现系统目标。每个机器人可能具有3种状态：墙、边界和内部。墙机器人是那些检测到障碍物的机器人。它们在与墙有关的对称位置处生成虚拟邻居，该墙可以充当抵挡机器人继续向前移动的虚拟力。边界机器人是在超过180°的角范围内既没有邻居，又没有墙的机器人。也就是说，边界机器人位于开放空间的边缘。内部机器人是那些既不是墙机器人，又不是边界机器人的机器人。在图9-7的实例中，W表示墙机器人，F代表边界机器人，I表示内部机器人。5个圆表示由机器人生成的虚拟邻居，它检测到附近的墙。(www.xing528.com)

图9-7 墙、边界和内部机器人

边界机器人通过传输形成根节点在边界机器人的树的梯度，来将群引导进水搜索区域。然后，所有机器人从树中的子节点处移开。树叶不发生移动，以提供一条指向充电器的路由或者标记先前访问过的区域。“边界树”引导群向边界机器人移动。边界机器人将群中其他机器人“拉”到它们后面。但是，任何基于以多跳方式拉机器人的算法，可能会导致新发现的边界将机器人从先前访问的区域拉走。这会造成边界机器人重新出现在旧位置上，并把群拉回去，形成一种振荡，或分解群且将机器人从原始位置（可能是那些需要对机器人进行充电的地方）断开。机器人仅从边界树中的子机器人处移开。为了针对容错应用，构建可靠的（双连通）网络，仅当机器人至少与边界树中的两个子节点建立联系时，机器人应当移动。这会提高网络的两个子节点之间的最小割，且有助于处理由角或移向本地进行充电的机器人生成的空穴区。