英语原文共 9 页

智能卵石机器人二维形状复制的分布式算法

凯尔·吉尔平和丹妮拉·罗斯

摘要:我们提出了一种从智能粒子集合中制造二维活动物体的数字制造技术。给定要形成的物体的被动模型，我们设想将这个原始物体浸入一个充满智能粒子的容器中，执行本文描述的新的形状复制算法，然后删除所有额外的模块，并排显示原始物体和精确副本。复制算法的扩展可用于创建模型对象的原始或多个副本的放大版本。我们的新复制算法使用分布式的方法来识别被复制对象的几何特征，然后从原始对象附近的空闲模块中形成复制。

本文详细介绍了复制算法及其特点，使其具有鲁棒性(1)不完全包装的模块周围的原始对象;(2)相邻模块间通信链路缺失;(3)重复对象附近缺失模块。我们证明了该算法需要每个模块的O(1)存储空间，并且每个模块交换O(n)条消息。最后，我们提供了60个硬件试验和150个仿真的实验结果。实验结果表明，该算法在通信链路中断、模块缺失的情况下仍能正常可靠地工作。

1. 介绍

在这篇论文中，我们提出了一种新的使用大量的能够通信和相互结合的智能粒子的方法来快速制造主动物体。传统制造业使用分层的方法创建设备，这种方法被组织成一个序列，包括机械设计、制造、电子设计、PCB生产、组装和精加工。相比之下，我们将必要的机械、感知和计算能力封装在小型智能构建块中，这些构建块集成了驱动、感知、通信和控制。在我们提出的系统中，制造包括为所需的形状或设计选择这些模块的正确聚合。通过使用一组同质的智能模块，而不是异构的、特定于任务的材料，我们(1)允许在不同的应用程序中轻松地回收和重用设备的组件;(2)复杂结构的自动化制造;(3)赋予物体固有的感知和计算能力。

图1展示了我们通过分布式形状复制来制作的方法。给定要制造的对象的被动物理模型，我们在本文中提出的分布式算法识别对象的几何规范，并形成一个或多个潜在放大的对象，复制从我们的可编程物质粒子在一个单一步骤的过程。由此产生的副本不仅具有原始被动模型的形状，而且具有智能、感知和通信能力。

图1所示。本文提出的分布式复制算法利用智能模块(这里是我们的机器人鹅卵石)的集合，将一个被动物体包裹起来，感知该物体的形状，然后从原始物体附近的空闲模块复制一个副本。(此图仅为说明，本文通过各种小型硬件实验验证了该算法的适用性。)

这种通过形状分布进行数字制造的方法是通用的，独立于组成可编程物质系统的单个粒子的体系结构。本文以1cm立方计算机Pebbles[1]为背景，采用可编程连接器和邻居间通信的方式，对其算法进行了说明。当前的制造技术限制了鹅卵石的大小(因此我们可以复制对象的分辨率)，但是随着制造技术的发展，我们将能够进一步缩小这些模块。最终，我们希望生产出亚毫米智能沙粒，具备目前机器人卵石的所有通信和计算能力。

无论可编程物质模块的尺寸、键合机制或通信接口如何，我们在这里给出的算法都是一样的。被动对象被埋在或淹没在可编程物质模块的集合中。在接收到启动信号后，模块与它们的邻居机械地结合在一起，将原始对象封装在一个规则的格子中。(目前，该系统无法处理网格内的晶界，但其他[2]已经开始解决这个问题，我们希望将他们的结果纳入我们算法的未来迭代中。)一旦在被动物体周围凝固，这些模块就会执行我们的复制算法来感知物体的形状。当系统捕捉到原始物体的形状后，它通过选择性地打开不必要的模块，利用剩余的可编程物质，创建一个或多个可能被放大的物体复制品。当这个自拆卸完成后，用户可以刷掉新断开连接的模块，以显示原始对象的副本。

该算法具有几个重要的性质。首先，它是完全分布式的，运行在一组相同的模块上。其次，由于任何模块都不知道目标形状的完整描述，分布式形状形成算法在我们形成越来越大的形状时具有良好的扩展性。忽略与存储大数相关的O(logn)缩放，这里给出的复制算法只需要每个模块的常量存储。此外，复制过程中交换的邻居到邻居消息的总数为O(n2)。第三，该算法既考虑了通信链路的破坏，又考虑了模块的缺失，使得该算法对无源形状周围的规则模块格的不完善具有鲁棒性。最后，该算法实现了从仿真到硬件的无缝过渡。它是用C语言实现的，其中的代码可以在模拟环境中编译并运行，也可以在硬件上运行而无需修改。

相关工作

我们的工作建立在一个研究机构的可编程物质和模块化的自我重新配置系统的[3]，[4]，[5]，[6]。研究人员将模块化机器人定义为链系统或晶格系统[7]。基于链的系统[8]、[9]、[10]是围绕树状拓扑构建的。相比之下，基于网格的系统[11]、[12]、[13]一直是可编程物质的基础，因为它们倾向于使用均匀的、对称的模块，这些模块以规则的2或3-D网格模式排列，模块可以在每个方向上与相邻的模块连接和通信。

Klavins等人已经为一个三角形自组装系统开发了硬件和算法，该系统在空气表[14]上运行。Griffith等人的研究表明，自组装系统可以以分布式方式进行自复制。Lipson的团队还在开发随机驱动的自组装可编程物质系统[16]和[17]方面发挥了重要作用。Christensen等人开发了一种可以指导机器人自组装的语言。尽管自组装系统很有前途，但它们并不适合我们在这里介绍的分布式复制算法。我们需要的不是一个通过逐块添加模块来构造对象的系统，而是一个从一组紧密封装的模块开始的系统，这些模块(1)封装要复制的形状，(2)形成一块原材料，可以用它来制作重复的形状。一个这样的系统是Catoms[5]。Catom的一般概念是一个球形或圆柱形机器人，其表面覆盖有执行器，使Catom能够与之结合并移动。

相对于另一个Catom。Goldstein等人提出了一种巧妙的形状形成算法[19]，该算法通过在结构内部创建和吸收气泡(或可移动的空隙)，对密集排列的Catoms进行操作。其优点是，所形成的形状的描述只需要与表面模块共享。

在其他工作中，Pillai等人提出了一种算法[6]，用于能够复制被动形状的Catoms系统。这个算法的目标实际上和我们自己的是一样的。该算法能够成功地捕获和复制仿真中的被动物体的形状。与我们的算法不同，Pillai算法是集中式的，它依赖于具有强大处理能力的外部计算机来管理复制过程。它还会导致高通信开销，因为所有形状数据都是从单个点流出并进入粒子集合的。该算法也不能对包含空洞的格进行操作。在最近的研究中，Funiak等人开发了一种有趣的算法，能够在完全不规则的智能粒子包装中进行分布式定位。我们在这里提出的分布式复制算法是通用的，可以在Catoms、数字粘土模块[20]或Miche[21]和机器人Pebble[1]可编程物质系统上实现。虽然许多可编程物质系统还没有表现出足够的模块间扭矩和力，以承受作为工具的使用，但他们有希望最终将[22]，[23]，[1]。

本文的其余部分组织如下。第二节解释了作为通信骨干的基本消息路由算法。第四节分析了复制算法的鲁棒性。第五节概述了如何形成多个副本或多个副本，这些副本是原始对象的放大版本。第六节给出了仿真和硬件实验结果，验证了分布式复制算法的正确性和鲁棒性。最后，我们在第七节中提出今后工作的途径。

二、路由算法

分布式形状复制需要一种可靠的方式将消息从系统中的一个可编程物质模块发送到任何其他模块。由于模块集合可能是非凸的，缺少通信链路，且包含凹的空洞，简单的梯度下降路由算法是不够的。每个模块有限的处理能力和存储空间限制了路由算法的选择。例如，不可能维护路由表，特别是随着系统中模块数量的增长。我们选择使用传统的bug算法[24]在系统中路由消息。错误不是机器人，消息是错误，模块是消息必须从源导航到目的地的环境。

特别地，我们使用Bug2算法。该算法可证明是正确的[24]，并确保，如果消息有可能到达其目的地，它最终将到达;如果不是，系统最终会得到通知。Bug2算法对于我们的系统来说是一个很自然的选择，因为它假设bug不能访问全局信息。错误(消息)只需要确定它的位置，以及它是否遇到了障碍(在我们的例子中是一个没有被模块占用的空间)，这些事实可以从模块本身获得。Bug2算法也很有优势，因为bug只需要维护恒定数量的状态信息，所有这些信息都可以轻松地存储在消息中。bug算法也有其缺点。基本上，基本的bug算法在3D中不起作用。有关如何扩展算法以处理3D原始文件的讨论，请参见第七节。本文的实验只考虑二维形状，但该理论可以推广到三维形状。

三、复制算法

分布式复制算法是一个多步骤的过程，它能够感知被可编程物质模块包围的被动物体的形状，然后使用同一初始块材料中的其他模块形成该物体的副本。该算法是完全分布式的，所有模块执行相同的代码，所有计算都在船上进行。图2所示的算法由五个主要阶段组成:

1)封装和本地化

2)形状感知/领袖选举

3)边界通知

4)形状填充

5)自我拆卸

简而言之,毕竟模块本地化和债券将被复制的对象,该算法感官边境的原始对象,创建一个重复的边界在最初的旁边,通知所有的模块内的边境,他们形成了重复的形状,然后提示所有模块除形成自我拆卸重复的形状。然后，用户可以刷掉多余的模块，就像雕刻家从一块大理石上移除多余的石头，以显示新创建的复制对象一样。

A.封装和本地化

形状复制过程从用户周围的被动对象开始，这些被动对象被一组可编程的物质模块复制。在一个有沙粒大小的三维系统中，我们设想的是将物体掩埋到复制的物体中。利用二维厘米尺度的机器人鹅卵石，我们可以使用一个倾斜的振动台，就像一袋沙子，用主动模块包围被动物体。一旦对象被包围，用户将向开始封装和定位过程的单个模块发送start命令。此消息的接收方任意假设其坐标为(0,0)，然后将其坐标告知其所有邻居。当每个模块在系统中学习它的坐标时，它会机械地与它的邻居绑定，从而严格地封装被复制的被动对象。每个模块与相邻模块绑定后，进入形状感知和领袖选举阶段。

B.形状感知/领袖选择

感知阶段的目标是双重的:确定原障碍物边界盒的周长、面积和尺寸;并在要复制的障碍物的周长上选择一个领袖模块。当一个模块被一个传入的位置消息本地化后，它通过假设没有响应的邻居存在来检测哪些邻居存在。它假设这些缺失的邻域对应于要复制的原始对象所呈现的障碍。然后，模块尝试(使用bug算法)将一条感知消息路由到它丢失的每个邻居。因为目标坐标被复制的障碍物占用，所以感知消息永远不会传递到它的目的地，但这就是目的。相反，感知信息将穿越被感知障碍物的整个周长。最终，它将返回给发送方，发送方将知道消息无法传递。

在遍历障碍物的过程中，感知消息由它经过的每个模块修改，以便在消息返回给发送方时，它持有障碍物的区域、周长和障碍物边界框的范围。图3显示了这个过程的实际情况。当错误算法导致消息与复制的障碍物实际碰撞时，由感知消息计算的周长就会增加。障碍物的面积按行积分。对于每一行，从最大的x坐标中减去最小的x坐标加1，但是这些操作从来不会同时发生。最后，感知消息通过记录障碍物所经过的最小和最大的x坐标和y坐标来确定障碍物的边界框。

虽然图3只显示了单个模块的sense消息，但是边界上的所有模块都会生成消息。为了从障碍物周围的模块中选出一个领袖模块，并减少传输的消息总数，模块丢弃来自唯一id比自己更低的模块的传入感知消息。因为只有一个最高的ID，所以在返回给发送方之前，除一个ID外的所有sense消息都将被丢弃。其sense消息返回的模块是实际的领导者。图3还忽略了一个事实，即在整个模块配置的外部边界上的所有模块都会生成感知消息。这些消息以相同的方式路由，但是当ID最高的模块生成的消息返回给发送方时，感知区域将为负，因此模块将知道它没有检测到障碍。

C.边境通知

边界通知阶段复制附近模块中原始形状的边界，并涉及三种类型的消息。重复消息通知边界上的每个模块其特殊状态的原始形状。边界消息由原始形状边界上的模块发送，并通知边界上的每个模块其状态的重复形状。确认消息则由边界消息的收件人发送并允许领导确定副本的边界何时完成。

图2所示。定位完成后，分布式复制算法首先在(a)中沿障碍物边缘路由感知消息。(b)所示,发送的消息模块最高的惟一的ID将最终回到发送方,促使该模块复制消息路由(c)边境的障碍。在收到重复的信息,一个模块发送边界信息,将成为它的共轭复制对象的边界。毕竟复制边界模块发送确认消息回(d)领袖,领袖广播消息填充(e)告知模块包含的新边界,他们是重复的形状,使它们的一部分发送确认消息回领袖(f)。在收到确认消息,领导广播拆卸消息(g)导致复制所有模块除形状自我拆卸(h)。注意:本图适用其余全部内容

图3所示。当模块试图使用bug算法将感知消息从源(5,1)路由到不存在的目标(5,2)时，它们更新消息中包含的周长、区域和边框字段。随着每一次与障碍物的“碰撞”，周长都会增加，面积也会逐行累积。当消息返回给发送方时，这些参数准确地描述了障碍。

边界通知阶段从形状感知阶段选择的领袖开始，该领袖试图使用bug算法将复制消息路由到其丢失的邻居，而该邻居的位置被要复制的障碍物所占据。与之前发送的sense消息一样，复制消息跟踪障碍物的周长，向边界上的每个模块传输两条关键信息:领袖的坐标和一个复制方向向量(其长度由原始形状的边界框决定)。

当复制消息通过原始形状边界上的模块时，每个模块尝试将边界消息路由到添加到发送方坐标的方向向量标识的模块。在刺激原始形状边界上的每个模块发送边界消息之后，复制消息最终返回给领袖，并在其中丢弃。

当边界消息到达其目的地时，如下所示：

模块成为重复形状的边界。(虽然图2没有显示它，但是原始边框上的模块可以同时作为复制的边框。)因为边界消息还携带领袖模块的坐标，所以每个边界接收方向领袖发送一条边界确认消息，该消息携带模块边界所在形状的重

资料编号：[4004]