网站开发服务合同范本,杭州互联网网站定制公司,品牌建设有哪些方面,国外网站备案查询摘要 本文讨论了一种新型机器人系统的理论和工程的概念基础。该系统由协作完成任务的自主机器人单元组成。本文在描述了该系统与细胞自动机和神经网络的相关性和差异后#xff0c;建立了该系统的基础属性及其对机器人单元结构的影响、它们操作的空间以及它们完成全局任务的算法…摘要 本文讨论了一种新型机器人系统的理论和工程的概念基础。该系统由协作完成任务的自主机器人单元组成。本文在描述了该系统与细胞自动机和神经网络的相关性和差异后建立了该系统的基础属性及其对机器人单元结构的影响、它们操作的空间以及它们完成全局任务的算法。此外还解释了细胞机器人系统的概念在分布式计算、分子计算、自组织和可靠性方面的意义。
1. 引言
解决的问题类型 本文为设计一种新型机器人系统奠定了概念基础。该系统由协作完成任务的自主机器人单元组成。该理论为设计机器人系统特别是设计允许机器人单元执行任务的算法提供了一种方法。
问题所属的领域 本工作中考虑的问题属于分布式计算的一般领域与元胞自动机问题密切相关。
问题的主题 所考虑的系统由大量但有限相对简单的机器人单元组成这些机器人单元能够共同完成相对复杂的任务。机器人单元的特点是其自主性既没有中央控制器也没有共享内存也没有同步时钟。由自主机器人单元组成的系统称为细胞机器人系统或CRS具有可靠性、自组织和自修复能力这是本文的主题。[3]中给出了原型问题的形式化模型和几个数学解。为了说明我们可以参考图1图1示意性地表示机器人可以根据内部协议和仅在其附近感测到的信息即通过自组织在其上操作例如移动、重新定向等和/或转移对象的无限单元阵列。 选择此问题的原因 解决这个问题的主要原因是缺乏处理分布式机器人系统的理论框架[4]。另一方面分布式计算是当前许多研究的主题但其具有普遍性的理论基础尚未应用于CRS等系统。此外细胞自动机理论也是当前许多研究的主题[5]到目前为止一直很难应用于实际的机器人系统可能是因为硬件的不可访问性通常是因为实现的成本会阻碍具体应用与一般的细胞自动机和众所周知的特殊细胞自动机如神经网络[6]有质的不同。因此建立一个新的理论基础是有益的。 这个问题的重要性 建立CRS理论基础的重要性在于开发CRS设计和构建方法的重要性。对于许多重要的应用机器人单元的自组织是必不可少的。在许多情况下在中央控制下执行任务是不可行的或者至少是不切实际的。例如在搜索区域上的目标时机器人单元的中央控制将是不切实际的因为检测和跟踪目标的机器人搜索者的本地组织将需要感测数据和机器人搜索者位置/定向的远程通信、感测数据的中央处理以及返回到每个机器人搜索器的后续期望位置/定向和感测收集策略的通信。从某种意义上说这类似于组织一支篮球队让每个球员不断地接受教练的指导例如通过无线电了解下一步的行动和关注范围。显然在这种情况下就像在目标搜索的情况下一样自组织即使不是必不可少的也是非常可取的。CRS等自组织机器人系统在许多工程领域可能非常有用并且作为生物系统的模型也可能很重要。在后者中CRS是相关的例如作为大脑组织和行为模式的模型如捕食策略。在工程应用中CRS可能对安全即火灾、地震、飞机灾难中的逃生策略等、监视、防御行动、执法行动、特殊环境太空、海洋等中的组装、人类性能的提高以及可靠性、自组织和自修复等其他情况很重要。此外当CRS的重要部分正在被销毁或已经被销毁CRS能够调整并继续执行分配的任务。 以前没有解决该问题的原因 CRS问题的一般解决方案特别是其理论基础的解决方案尚未产生原因有几个。首先分布式计算理论的问题通常非常热门因此产生的专门针对CRS问题的解决方案相对较少。其次细胞自动机理论的问题在密切相关的领域产生了许多解决方案因此可能会给人留下一种普遍的印象即自组织机器人理论也在取得进展。但是CRS还没有被真实地建模即使用保留自组织机器人系统的关键物理特征的模型。因此已经产生了旨在对机器人自组织进行建模的解决方案但所使用的模型本质上是细胞自动机模型不能保留CRS的物理特征。未能意识到这一点导致大量研究工作转向产生模式生成和自我复制问题的解决方案这些问题在数学上非常有趣但在物理上不适用于实际的机器人系统——不仅在工程意义上不适用在概念意义上也不适用。我们将在第2节中回到这一点。 解决问题的方法 本文为能够自组织的机器人系统建立概念基础的一般方法主要在于重塑问题而不是在当前范式中寻找新的数学方法例如在细胞自动机和神经网络理论中。与其他类型的自动机系统相比在重构问题时我们考虑了机器人系统的基本特征。粗略地说这个特性就是处理物质的能力。通过简单地在模型中引入这一特性作为约束我们可以推断出能够自组织的机器人系统的物理现实模型必须满足的大多数其他特性。 以前使用的方法 以前的细胞模型没有考虑机器人系统的这一特性即处理物质的能力。相反他们对机器人进行了建模就好像它们在概念上与自动机无法区分一样。因此能够处理信息的机器已经被用作能够处理信息和物质的机器的通用模型。后两个实体之间没有概念上的区别。物质本质上被视为系统的另一组状态——它与自己的描述相混淆因此作为附加信息包含在模型中。因此在建立能够自组织的机器人系统理论时没有理由重新考虑自动机模型的基本特征。因此重点是建立自动机理论模型的数学方法。 本文解决方案的优势 本文的研究重点放在寻找能够自组织的机器人系统的正确模型的概念基础上还有几个额外的优势。一个明显的例子是确定在几个简化假设模型下获得的数学证明的物理有效性范围。对于工程师来说重要的实用性是设计各种逼真的模拟算法的可能性以根据经验测量“系统在不同控制协议下的性能”在许多情况下分析解决方案是困难或不可能的。
2. 与其他理论的关系
机器人系统理论的现状 目前对机器人系统理论的许多研究与自动机理论中既适用于人工系统又适用于自然系统的分支难以区分。细胞自动机理论和神经网络理论均受生物系统启发寻求组织、结构、语言、信息和控制的一般原理这些原理可用于解释生物系统以及设计具有生物形态智能功能的人工自动机。这些理论目前也被应用于机器人系统。 机器人与自动机的区别 然而自然和人工计算机并不是对机器人系统的好描述者它们的相似性和差异激发了前面提到的许多理论。后者存在于天平的某个地方其一端是简单的机制一端是人类。相反计算机位于天平内的某个地方其一段是简单的计算设备一端是人脑。显然这两个尺度是不同的因为后一个尺度上的任何系统都是前一个尺度下相应系统的组成部分。我们可以通过将前者描述为由处理物质和信息的系统组成来抽象这两个尺度之间的本质区别后者作为只处理信息的系统。因此机器人系统的一个好的描述符必须是一个本质上包括物质处理作为系统基本功能的模型仅描述信息处理的模型是不够的。机器人系统理论不能被视为自动机理论的一个分支。 机器人系统理论的主要特点 通过基本假设机器人系统理论必须是能够处理物质除了信息的系统理论本文可能希望发现能够自组织的机器人系统的结构、操作和控制的基本原理。[后一种规范自组织很重要因为本文对集中控制的机器人系统柔性自动化和制造的标准机器人系统在理论上没有太大的兴趣。在这些系统中物质的处理发生在信息处理之后。这两种类型的处理顺序地发生并且因此被分离。[“顺序”一词不应从字面上理解而应从概念上理解]。由于这种分离以及物质处理本身作为一个系统问题在概念上很简单纯粹的信息处理主导了集中组织和控制的机器人系统的理论兴趣。] 因此机器人系统的概念相关理论必须是能够处理信息和物质的自组织系统理论。 定义自组织机器人系统的性质 本文模型的这一基本假设与“物质”即材料结构模式而非“能量状态”模式中编码的信息的一般概念有关。算盘和微处理器分别是这两种类型的编码信息的示例。在微处理器中计算是通过“物质不移动”时的能量状态转换进行的。显然电子和空穴是物质但在本文中我们从“结构”的意义上而不是严格的物理意义上指物质。这种区别在自组织系统的基本理论中是必要的因为该理论最终必须区分1编码在实体中的信息如电子能态作为一个系统不能形成自复制结构以及2编码在诸如原子、分子等实体中的信息这些实体可以作为一个系统形成自我复制结构本文不会明确讨论自我复制但该理论的目的是为描述同样能够自我复制的系统奠定基础。对于后者正如我们所注意到的一个系统必须能够通过其自身的结构单元将信息编码为其自身结构单元的模式即它必须是一个能够将信息编码成这些物质实体的模式的物质实体系统。这种性质可以被视为自组织机器人系统的定义性质与自组织计算机系统如细胞自动机和神经网络形成对比。正是这种性质我们之前在粗略地将机器人系统描述为传递“物质和信息”的系统时提到了与计算机系统形成对比它只传递信息“也正是这种特性定义了活生物体事实上活生物体是一个物质实体DNA和其他分子系统能够将信息编码为这些物质实体的模式。[这一定义并不排除生物体将信息编码为这些分子能量状态模式的能力。这种能力实际上是生物体智能的可能机制之一也是用神经网络和相关自动机理论建模的能力类型。然而这种能力并不是生物体的基本特性。相比之下如果没有将信息编码为其自身结构单元的模式的能力就不可能有自我繁殖因此也就没有生命。] CRS与元胞自动机的区别 我们注意到自我复制的概念也与细胞自动机理论的基础有关。后者最初是作为一种建模自复制自动机的方法。这种建模方式是由处理数学上可管理的问题的需要决定的。然而在这样做的过程中原始冯·诺依曼自动机自复制动力学模型的物理属性丢失了。在细胞自动机理论中构建的自我复制实体是自动机而不是机器人。根据我们的定义它们是处理信息的实体而不是物质和信息。因此尽管细胞自动机已被应用于生长模式和其他生物自组织问题包括自我繁殖但它们的普遍性阻碍了机器人系统的基本特征。在一个典型的细胞自动机模型中自组织发生在一个无限大的空间中该空间被划分为多个单元每个单元都包含相同的有限自动机单元。模型中可以使用多种形式的细胞结构。一个例子是正方形单元的无限阵列每个单元都包含相同的n态元素每个单元直接与其四个相邻的单元通信。每个单元中元素的状态变化取决于它们的状态和四个相邻元素的状态。变化以离散的时间间隔同步发生。因此在每个时间间隔阵列中所有元素的状态集形成一个模式通常在下一个时间间隔发生变化。通过这种方式模式进化例如生长或繁殖这是通过邻居通信进行自组织的结果。在细胞机器人系统理论中我们保留了1离散细胞空间和2相邻交互的细胞自动机特征。然而我们对机器人系统的基本假设的要求限制了我们的模型因此必须放松同质性每个位置的同一元素和同步性同时发生状态变化的特性。此外对相邻相互作用的规则施加约束以反映单元元件的材料性质。这些因素专门化了一般的细胞模型使得细胞机器人系统的理论与细胞自动机父模型不同例如动力学来自运动学。
3概念模型
基本特性 定义属性 CRS的概念模型基于CRS的定义属性在上一节中说明为 1 系统将信息编码为其自身结构单元模式的能力。 从这个属性可以得出三个基本属性。 异质性 第一个性质可以称为异质性性质因为它消除了细胞模型在细胞自动机中出现的同质性。更具体地说由于我们处理的是“结构”实体因此细胞空间不能被视为由相同的有限自动机元素组成这些元素在任何时候都只是在状态上不同。细胞空间必须被视为在某些位置填充了结构元件可能是相同的而在其余位置什么都没有或填充了不同类型的结构元件。因此有空的站点和被“物质”占据的站点即结构元素或被不同类型的结构元素占据的站点。这两种类型的站点不能被建模为能够改变状态的单一类型即空的状态和被占用的状态因为可以说“物质”不能凭空产生而是必须来自某个地方即相邻的站点。[确实根据特殊的质量守恒规则可以将结构元素在细胞空间上的运动模拟为相同元素的状态变化。但这一过程比将模型重新定义为异质模型更复杂]。为了强调CRS的异质性我们可以参考一组男性和女性围坐在桌子旁试图重新安排他们的坐姿以实现预先指定的男性-女性模式例如交替模式。在这种情况下细胞自动机理论是同构的因为它将通过将每个个体视为相同的个体并能够根据邻居的性别和某些给定规则改变性别来解决问题细胞机器人系统理论是异质的因为它将个体的性别视为不可改变的属性因此只有在个体物理上“交换”座位的情况下模式才能改变。 动力学 从CRS的异质性性质来看遵循第二个基本性质可以称为“动力学”性质。我们已经看到一旦细胞系统包含不同类型的单元不同的结构单元或结构单元和空位只有单元在细胞空间上的实际运动才能形成新的模式。因此这些模式是动态形成的就像成群的蜜蜂在蜂箱细胞上形成的模式一样。相比之下在元胞自动机中形成的状态模式是“静态的”不是在它们本身而是在形成它们的元素中它们保持在它们的固定位置就像灯泡阵列中的灯泡一样灯泡阵列在夜间显示不断变化的光和颜色模式作为城市中的广告标志。 异步性 最后从动力学的性质来看遵循了“异步性”的基本性质。由于系统的结构单元实际上是在移动以形成一种新的模式因此将它们的运动建模为同步运动是不物理的。环境中的随机事件通常会阻止运动的同步。此外在没有中央控制器的情况下结构单元的时钟同步将构成物理上极为严格的假设。 属性总结 因此CRS模型在概念上具有以下特性 1 定义属性系统将信息编码为自身结构单元模式的能力。 2 基本属性 2a异质性模式由结构单元和空位或不同的结构单元形成。 2b动力学图案是由结构单元物理移动到变化位置形成的。 2c异步性模式是由结构单元形成的每个结构单元都根据自己的内部时钟运行。 三个基本性质2a2b2c允许将概念模型形式化为数学框架从而可以获得并证明模式生成问题的解决方案。这些数学模型构成了细胞机器人系统理论的主体。相关工作中给出了这些模型和模式生成问题的数学解的例子。在本文的剩余部分中本文将讨论这三个基本性质对数学模型结构的影响。然而首先本文要讨论基本性质与其他概念模型的关系。 与其他概念模型的关系 CRS的替代定义属性 三个基本性质2a、2b、2c源自CRS定义性质1但这三个性质也可以与其他概念一致。因此一旦根据2a2b2c建立了CRS数学模型该模型就可以应用于不一定具有相同定义性质1的系统。 特别地满足三个基本性质但不完全对应于1的系统如下。如图2所示在细胞空间上每个位置都被一个机器人操纵器单元占据该单元能够将物体从其位置转移到任何相邻位置。机器人操纵器是异步的物体可以是不同类型的。这样的系统可以是协作机器人的完全分布式柔性自动化系统的模型。该系统根据性质2a2b2c形成模式但不将信息编码为其自身结构单元的图案即不符合定义性质1。该系统将信息编码为由机器人操纵器单元从一个地点转移到另一个地点的物体组成的模式。它们确实是物质对象的模式因此也是结构单元的模式但不是系统自身的结构单元即机器人操纵器单元的模式。因此我们看到基于2a2b2c的数学理论在1之外适用于可以由更一般的定义性质表征的系统 1a系统将信息编码为结构单元的有限集合的模式的能力。 不同CRS概念模型之间的差异 由1和1a定义的系统在概念上是不同的但都适用于大类相关问题正如我们所看到的这些问题具有共同的性质2a2b2c。由1定义的系统与生物分子细胞、生物体自组织以产生新的生物实体的系统密切相关。在工程中它们通过自主移动机器人单元的系统来实现这些单元将自己重新排列成新的模式即完成预定的任务。1a定义的系统与机械造波物理系统密切相关。模式形成单元的总“质量”是守恒的并且位移没有间断。这个概念也适用于电化学系统中的离子波。在这里机器人操纵单元和从一个地点转移到另一个地点的物体分别由电化学细胞和离子体现——离子从一个细胞转移到另个细胞形成新的化学实体模式。 后一个例子表面上使我们接近传统的细胞自动机理论和神经网络。考虑到离子波模型守恒了离子的总数即电化学系统的总电荷这种差异是明显的。通过强加总电荷守恒我们就是强加CRS的性质2a2b2c。因此如果一个类似的细胞系统是由连接到最近邻居的电容器组成的并且能够在它们之间转移电荷没有外部电源施加到系统我们也会有CRS。但是如果施加外部电源并且电容器能够独立于系统中的总电荷而处于接通或断开状态就像在任何电子计算机中发生的那样我们将不在2a2b2c的范围内因此也不在CRS理论的范围内。这个系统将产生能量状态的模式而不是“结构”单元的模式从而回到细胞自动机理论和神经网络的领域。没有外部电源的电容器系统的例子还表明特性2a、2b、2c可以由其单元不是结构性的系统例如电荷来描述。只要“守恒定律”适用于在细胞空间上转移的实体就会发生这种情况。显然在定义CRS的概念来源时我们可以采取比1和1a更普遍的观点即通过将定义属性陈述为例如 1b系统将信息编码为恒定数量实体的模式的能力。 然而很明显随着我们进一步远离1概念模型往往更接近于对满足2a2b2c的数学模型的重述因此只会稍微更具启发性。此外CRS的一些重要特征在替代定义1a和1b中变得模糊不清。例如自修复性质在表面上与1b相矛盾然后应进一步限定并且它也不严格适用于1a的一维版本。因此选择1a或1b作为唯一定义性质在概念上没有优势但参考它们以进一步阐明CRS概念的范围是有用的。 基本性质的结果 CRS概念模型的基本属性2a2b2c定义了CRS的六个主要描述特征的范围它们是1对于整个系统a细胞空间和b任务2 对于每个机器人单元a信息处理元件例如机载计算机b物质处理元件如运动系统、机械手等c“物质”到信息接口例如机载传感和显示单元和d管理协议即实现全局任务的算法。 信息处理元件 该模型施加的唯一限制是每个单元的信息处理元件在其处理功能中与其他单元解耦。数据从相邻单元传递到信息处理单元但计算本身是以完全分布式的方式完成的。时钟不同步每个单元上都没有标识符。每个单元独立且匿名运行。 物质处理元件 这些单元必须具有转移物质的能力无论是它们自己的通过移动还是其他物体的通过操纵或者两者兼而有之。前者对应于定义属性1后者对应于1a。不同的模型取决于单元是否能够绝对、相对或无方向定向。最后决定不同类别模型的一个重要因素是每个单元的“任务装置”的类型包括不存在。任务装置是每个机器人单元携带的元件通过它来完成CRS的全局任务。在这里我们注意到无论全局任务是物质处理、信息处理还是通信任务这种任务设备通常都是“物质处理”设备。 通信元件 模型的基本特性要求在机器人单元之间交换信息。因此传感元件和显示元件必须由机器人单元携带。最大范围没有理论限制但对于自组织模型通信应该是短程的例如与最近的邻居否则系统获得了集中组织的能力CRS模型的优势就消失了。 管理协议 从其基本性质来看CRS的管理协议与分布式计算协议密切相关。因此分布式计算理论中出现的一类问题在CRS中再次出现。 例如与元胞自动机相比CRS遇到了承诺问题和互斥问题。除了这些相似之处分布式计算理论和CRS理论之间还有一些不同之处。例如 1 在大多数分布式计算系统中每个节点都有一个唯一的节点id这样节点就可以区分。相反就管理协议而言一种类型的CRS机器人都是相同的没有标识符。 2 大多数分布式计算系统具有静态连接的拓扑结构。相反CRS的拓扑结构并不是固定的。机器人通常以随机配置启动协议机器人之间的连接会随着配置的变化而变化。对于系统在给定时间解决的给定问题只有一个拓扑是当前的因此在问题解决算法开始后进入配置的机器人被忽略。 任务 CRS在全局范围内可以被视为一种机器人。因此它可以完成三种类型的一般任务1物质处理任务如组装2通信任务即感测和显示和3信息处理任务例如计算。前两类任务的含义很容易理解这些任务是当前设想应用的主题。第三类是生化计算的机器人模拟。分子系统通过重新排列分子模式来处理信息。这源于生物系统将信息编码为其自身结构单元的模式的能力。正如我们所看到的CRS具有类似的性质。因此可以在CRS理论中设计生物化学计算的模型。
4. 结论
意义 在前面的章节中我们已经描述了设计一个新的机器人单元系统的概念基础该系统可以协同完成任务。本节讨论了未来研究的理论意义和相关性。 CRS理论的发展可能对以下问题产生重要影响 1分布式计算。CRS模型中开发的方法论扩展了当前分布式计算理论的方法论。后者需要大力发展因为目前大多数分布式计算理论问题都是以临时的方式解决的。“相互排斥”、承诺、多注册读者/作者和领导者发现”的各种例子已经得到解决但在统一的理论或方法论方面仍有大量研究工作要做。当然同样的情况也适用于CRS目前可用于CRS的解决方案更少。然而存在一个通用的概念框架在该框架内对大类分布式计算问题进行建模并相互关联为更广泛的适用性方法提供了有用的激励。 2分子计算。如第3节末尾所述CRS还可以为分子计算提供理论基础。通过结构单元系统进行计算分子计算已经被提出并被设想为在不久的将来的技术可能性。但是除了明显的制造困难外在这些系统的工程开始之前CRS中遇到的这类理论问题还需要解决。例如需要提供消耗资源竞争问题的解决方案以避免在分子模式演变过程中出现“闭环和死锁”。 3二维语言。源于CRS理论的另一类问题涉及用于全局协议规范的适当语言。二维语言是在细胞自动机的背景下提出的。这一概念需要扩展到CRS。开发CRS的二维语言对于开发汇编操作的形式语言也很重要。
局限性 尽管CRS似乎适用于一大类理论和实践问题但存在明显的局限性。例如该理论目前不适用于连续系统。从离散结构走向连续极限涉及改变离散细胞空间的一般框架。对于细胞自动机和神经网络所设想的应用来说这种限制并不是很重要因为所处理的问题本质上是离散的。然而对于机器人系统来说连续运动是一种非常相关的情况因此一大类机器人问题仍然不在CRS理论的范围内。然而将该理论扩展到连续空间同时保持单元的离散性是可以想象的。
未来研究主题 CRS理论的发展需要解决以下领域的理论问题1细胞空间结构2信息处理元件3物质处理元件4通信元件传感器和显示器5管理协议和6全局任务。为了表明未来可能的发展我们提到了这些领域中的一些问题。1对三维问题和不同网格结构的扩展。2两个或多个结构单元形成簇后的功能融合。3决策和运动无论是否知道绝对方向优化现场操作状态的数量和类型以最大限度地降低组装结构单元的功能成本。4多方向传感和通过空场地进行传感的战略优化多向“招牌”显示。5管理协议如语言的正式规范6设计方法论。
