一种柔性缩放的群机器人形态自修复方法

近年来，得益于通讯传感、智能控制、先进制造等诸多领域的蓬勃发展和技术融合，群体机器人技术为愈发复杂的多任务场景问题提供了有效的解决思路和可行方案[1]。区别于传统中心式控制的单机器人系统，群体机器人因为其大规模与分布式的特性，具有高鲁棒性、可扩展性、柔性等显著优势，在协同搜索、灾难援救、移动传感网、蜂群作战等领域具有广阔的应用前景。

当群体机器人在未知、动态变化的复杂环境下执行作业任务时，外部的扰动和冲击可能导致群体系统内部的部分个体发生故障或失效，从而影响整个群体系统的作业效能。群体系统具有较高的冗余性，在单个或多个机器人发生故障或失效的情况下仍能维持系统的性能[2]，但是当失效的机器人数量超过一定的安全阈值时，整个系统将出现性能劣化甚至崩溃。因此，赋予群体机器人系统一定的自诊断和自修复能力，提升整个群体系统在扰动或对抗工况下的自愈能力和抗打击能力，是确保群体系统顺利完成任务的必备条件。

在群体机器人自修复研究领域，文献[3]根据机器人的位置模式分别给予奖励与惩罚措施，以期实现虚拟胚胎方法驱动下损伤机器人有机体的再生修复，但是在群体内机器人数量有限的条件下，该自修复方法的效果欠佳。文献[4]提出了一种根据密度信息协调机器人均匀覆盖的无线通讯网络修复算法，但该修复方法因机器人能耗大导致系统自愈过程时间长。文献[5]提出了一种基于密闭容器气体分散模型的自修复算法，通过引入作用力与虚拟向量，实现机器人在指定二维区域的扩散；然而该方法中的机器人受最大通讯范围约束，系统缺失严重时可能无法对图案形状完全修复。文献[6]通过群体内机器人执行简单规则不断调整构型规模，最终实现依据当前群体规模对原始形态的缩放修复，但该方法需所有机器人不断尝试并调整修复方案，由此导致其修复过程耗费大量计算资源。

国内的研究机构在群体系统自修复领域也开展了相关研究探索工作。文献[7]提出了一种基于递归机制的移动机器人编队自修复方法，然而，由于通信量随机器人数量的增加呈指数增长，使得该修复方法不适合大规模集群机器人的修复场景。文献[8]利用元胞自动机规则和梯度方向吸引，引导机器人对L系统的目标构型进行缺失修复，该方法受L系统的构型描述约束，其主要适用于枝状拓扑结构。文献[9]通过引入活化激素和抑制激素对机器人进行动态路径规划，实现机器人对空缺位置的自主填补，该方法适用于多空缺单元的填补，对于较大范围缺失单元或部位的自修复存在一定困难。

考虑到群体机器人系统多应用于协同、编队等非结构化环境下的复杂对抗性任务，群体系统内的机器人个体需要保持一定的通讯距离来形成一个整体，从而提高整个群体系统的抗损毁性和生存能力。现有的变密度内部扩散自修复思路[6]为了保持修复前后的几何形状一致性而改变了群体内部机器人的间距，而通信距离过大则不能保持群体内机器人通信的连通性。等密度形态缩放自修复思路则是通过对群体系统规模进行判断识别，并在确保机器人间距不变的条件下自主修复为按照比例缩放的新目标构型体。因此，等密度形态缩放自修复思路维持了机器人个体之间的紧密联系，适用于复杂对抗环境下群体系统的自组织和自修复。

为此，针对大规模群体机器人系统在局部缺失情况下的自主修复问题，在借鉴等密度缩放修复思路的基础上，本文提出了一种随缺失规模柔性缩放的群体机器人形态自修复方法。即：基于以系统缺失规模为驱动的自诊断方法来判定群体系统损伤或缺失部位，并基于原始构型及当前群体状态自主生成新修复目标构型，然后在新目标构型的引导下，通过基于个体状态与周围环境信息的运动规则集，解决群体机器人自主修复过程中的“谁先走”、“怎么走”、“到哪里”3类决策问题。

1 群体机器人自主修复策略

群体机器人大规模、低成本的特性，使得群体系统中部分个体发生故障或损坏不可避免。另外，群体机器人系统缺乏全局信息的指导，无法通过系统层面的全局规划行为来实现损伤部位的修复工作。因此，机器人如何仅依赖自身有限的感知与信息交互能力，通过个体间的协调合作自主有序地完成缺失部位的修复任务，是群体机器人系统亟待解决的现实问题。

1.1 等密度形态缩放修复原理

等密度形态缩放是指：群体系统以系统内机器人规模信息为依据，以原始目标构型信息为参考，将局部缺失后的大规模群体系统修复为经比例缩放后原始构型体的相似形状，同时修复构型保持机器人之间的分布密度不变。该修复过程的比例由构型体原有的机器人数量和缺失后群体中机器人的数量确定。如图1所示，机器人系统以经缩放后的新目标构型为驱动，始终维持个体之间的紧密联系，自起始位置向新目标构型的空缺区域有序运动。

图1 等密度缩放修复原理图

1.2 分层修复策略

在前期的群体机器人自主成型方法基础上[10]，提出了大规模群体机器人的分层修复策略。该策略包含3个部分：分层剥离、分层填充、迭代循环，如图2所示。当系统检测出受外界冲击导致局部机体缺失后，对当前群体规模数量进行自主识别判断，并结合原目标构型生成新的修复构型；以该等密度缩放的构型信息作为修复任务，将修复目标构型与当前机器人聚集体组合匹配后，在分层修复策略的驱动下，处于修复目标构型体外区域，且位于当前聚集体最外层的机器人个体会有序运动到修复目标构型体内区域，实现空缺位置的填补，从而完成系统的修复任务。

图2 集群机器人自修复策略示意图

在图2中，机器人群体结合自身位置坐标，与形成的修复目标构型体函数表征式进行匹配，根据坐标与函数轮廓围成封闭区域的位置关系，将缺失后的群体系统划分成2部分，即：位置坐标在函数轮廓内的部分称为修复目标构型体内区域，位置坐标在函数轮廓外的区域称为修复目标构型体外的区域(见图2a))。在此基础上依据分层填补策略，通过目标构型体外个体间的局部交互，规划出目标构型体外优先移的机器人集合，构成运动链(见图2b))。依据分层填补策略，运动链机器人沿着聚集体边界运动，并依次填补至待填补区域内边缘层(见图2c))。当运动链内个体填补结束后，依据迭代循环策略，新的运动链不断被激发并填充到填补区域，直至完成自修复任务(见图2d))。

2 群体机器人形态自修复方法

针对二维已成型群机器人系统，基于上述等密度形态缩放修复原理和分层修复策略，提出一种群体机器人形态修复方法，如图3所示。

图3 修复目标构型任务驱动下的群体机器人自修复过程

在修复前的自诊断阶段，通过群体系统对当前聚集体规模识别判断(见图3a))，基于原成型体构型信息重新生成新修复目标构型(见图3b))，并由竞争机制选出的领导者机器人下发至所有机器人个体。随后，所有机器人个体通过局部感知与交互，重新生成覆盖整个初始聚集体的梯度场，对自身梯度参数信息初始化(见图3c))。

在修复运动控制阶段，以机器人个体不同状态为依据，沿顺时针形成运动链(见图3d))；之后，运动链内的个体沿着当前聚集体边界依次填补至待填补区域内边缘层(见图3e))；当运动链内个体填补结束后，依据迭代循环策略，新的运动链不断被激发并填充到填补区域，直至完成自修复任务(见图3f))。

2.1 修复前自诊断

已成型体作为稳定的群体系统，内部机器人在成型任务结束后通过传感器实时检测周围环境的状态变化。若循环检测的2个周期内，机器人周围环境发生突变，某方位的邻居机器人缺失，则该突变将破坏群体系统的循环检测机制，从而进入自主修复的自诊断阶段。自诊断算法通过对群体系统的损伤检测，生成新修复构型作为后续修复阶段的目标成型任务。

2.1.1 缺失部位检测

群体系统完成自主成型任务后，系统内部的机器人个体相互之间保持紧密、对齐排列的晶格式网络。将相邻晶格单元的机器人间距作为阈值，将传感器与环境交互获取的距离信息和该阈值作比较，实现循环检测自身邻域环境状态信息的目的。设定机器人可以保存2个检测周期时间范围内其邻域内晶格单元的状态信息，即该晶格位置是否被机器人独立占据。若受到外部冲击导致局部机器人出现故障或损坏，则已成型体的构型必然出现局部缺失。对于处于缺失区域边缘的机器人来说，其邻域晶格的状态信息也必然发生变化，从而引发2次循环检测得到的状态信息发生跳变。

如图4所示，因邻域范围内的机器人邻居缺失而引发检测信息跳变的机器人个体(见图4b)),分化为缺失边缘的危险状态机器人，并向群体系统广播损伤检测结果，令所有机器人获取修复任务执行许可，由成型后的循环检测状态切换至修复前自诊断状态(见图4c))。待系统内机器人均完成状态转化，可开展后续群体系统规模识别工作。

图4 缺失部位检测方法

2.1.2 群体系统规模识别

群体系统规模识别作为自诊断工作的重要部分，决定了以当前系统规模为依据而生成的修复目标构型的准确性。如图5所示，群体系统规模识别阶段通过2个步骤来实现：①在缺失区域的边缘选举出1个领导者模块机器人作为任务执行起点(见图5a))；②由领导者机器人开始，通过信号绕当前聚集体的边缘传递1周，确定当前系统内机器人的总数量规模(见图5b))。

图5 群体规模识别

1) 领导者选举

文献[11]中利用形态发生梯度机制来确定胚胎细胞发育过程中自身位置与极性的经典方法，令每个处于危险状态的机器人个体都向其邻居传播自身ID信息，从该集体中选举出一名领导者，作为群体系统规模识别的原点。机器人的ID信息可确保每个机器人在其局部通讯范围内的身份信息独一无二，处于危险状态的机器人在接收到比自身ID值更低的信号时，则表明该机器人受到信号抑制退出选举过程，且将较低的ID信息重新传输给其他机器人。最终，在设定的时间内未收到任何低于其自身ID值的机器人将被选举为领导者。

2) 边缘统计信号传递与规模统计

处于“领导者”状态的机器人作为群体系统规模识别的原点，统计当前系统的机器人数量规模。领导者结合自身与缺失区域的位置关系，在顺时针方向优先的约束条件下，向其邻居机器人发送用于识别当前系统规模的统计信号，且该统计信号被限制在边缘机器人个体中传播。接收到统计信号的非领导者机器人处理完数据后，以信号传入方向作为判断依据，以顺时针方向优先为约束，依次尝试向信号传入的高优先级顺时针方向输出修正处理后的统计信号，直到该信号被邻居边缘状态机器人响应并接收。随着统计信号沿边缘机器人集合传递，最终返回领导者本体，标志着规模识别过程的终止。领导者机器人接收到由它发出的统计信号后，以相同方式对信号作识别处理，但信息处理结束后终止规模识别过程，关闭统计信号发送通道，并向群体系统广播最终的统计结果，让每个机器人都获取当前群体系统内机器人的总数量规模。

2.1.3 修复构型的形态再生

经群体系统的规模识别阶段后，每个机器人均得到当前系统内机器人的总数量规模。将当前群体系统剩余机器人的数量n与原始已成型体机器人的数量N比较，可得到缩放比例参数：并将其作为修复目标构型的形状因子，引导修复构型的形态再生。在二维平面内，期望图形可以看作由该图像的几何轮廓包围成的一片封闭区域。结合给定的期望图形，基于图像的几何轮廓特征，人为统计轮廓上包含信息较多的关键点，即轮廓顶点的集合。通过轮廓顶点计算图形各轮廓边缘的函数表达式与各自函数因变量的范围区间，可以得到由有限个函数组合围成的目标构型图案。故本文采用函数表征方式来实现目标构型的建立与识别。以成型任务的目标构型函数为依据，以修复构型的形状因子fshape为驱动，结合各图形的结构特征与函数表征特征，如圆形图案选取中心点作为比例缩放中心，而其他图形以最高顶点作为比例缩放中心，按比例缩放目标构型图形，便可得到修复目标构型的信息。

修复构型的形态再生过程可分为以下2步：

step1 根据缺失后群机器人总数n和原有机器人总数N计算缩放比例参数：

step2 将原有成型形状的外轮廓函数依据缩放比例参数进行缩放。

2.1.4 机器人个体信息初始化

机器人结合自身位置坐标，与构型函数表征式进行匹配，根据坐标与函数轮廓围成封闭区域的位置关系，将机器人初始化为修复目标构型体内机器人(state-inshape)与修复目标构型体外机器人(state-outshape)。处于构型体内的机器人，通过机身搭载传感器感知邻域范围机器人存在情况，若属于目标构型区域的晶格为空，则表明该晶格位置空缺受损，该机器人初始化为缺失边缘机器人，向外提供缺失区域的方位信息。处于构型体外的机器人，若检测出周边存在空缺晶格，则认为自身处于构型体的边缘，初始化为外边缘机器人，如图6所示。

图6 机器人个体状态分化

位置状态初始化完成以后，缺失区域由缺失边缘状态的机器人集合包围而成。将梯度重新定义为机器人所处位置到达缺失边缘机器人的最短曼哈顿距离，表征着机器人到达缺失区域的相对距离。故令所有处于缺失边缘状态的机器人梯度值设为最小值1，由其开始向外扩散梯度信息，在当前聚集体内生成覆盖所有机器人个体的梯度场，引导修复目标构型体外的机器人向该缺失区域运动填充。

2.2 修复运动控制

在完成修复目标构型生成、机器人参数初始化的基础上，采用五邻域结构下的四向运动方式，以自诊断阶段再生的修复目标构型为任务驱动，建立以个体行为规则为核心的自修复运动控制算法，并通过机器人个体间的协调配合，自下而上呈现出缩放规模的修复构型，实现群体系统在局部缺失条件下的形态自修复任务。

2.2.1 外边缘个体激活与分离规划

机器人完成自诊断阶段的工作后，经角色分化，均由空闲状态切换至待激活状态。所有个体均已获取自身梯度信息，进入个体的激活与分离阶段。由梯度定义可知，梯度表示了该机器人所处位置到达缺失边缘机器人位置的最短曼哈顿距离，也可理解为该机器人距离缺失区域包裹的层数。如图7所示，群体系统通过自诊断阶段形成的梯度场，在覆盖了整个已成型体的范围内实现分层。处于最外层的外边缘机器人个体由待激活状态切换至边缘激活状态，通过与邻域内邻居机器人持续的信息交互，判断自身是否满足运动激发条件。

图7 机器人运动激发过程

其中，运动激发条件总结如下：

1) 个体在局部范围内梯度值最大。机器人的梯度值在局部范围内最大，意味着该机器人不仅处于当前聚集体的外边缘，更没有被其他机器人包裹在内，运动分离时不会被约束干扰。满足该条件的机器人则触发运动分离，个体被激活且切换至运动状态。

2) 若局部范围内存在多个梯度值最大的机器人，则ID值最大者先触发运动分离。在梯度场的同一层级中，若存在多个机器人均满足局部范围梯度值最大，则这些机器人的同时运动会导致运动碰撞或缺失运动参考等意外发生。为了保证机器人有序分离出聚集体，将机器人的ID值作为依据，通过对比局部范围内相同最大梯度机器人的ID信号，选择ID值较大者优先激活。被激活的运动状态个体则持续在局部范围内发送运动压制信号，确保离开安全距离后，其他机器人才可被激活，实现层内机器人集合以ID值递减次序的有序逐个激活分离。

2.2.2 运动个体绕行修复

群体机器人功能简单，通信能力与运动能力均有限。局部范围的通讯能力限制了机器人对自身运动规划的范围，因此机器人的每一次运动决策仅可实现局部范围，即邻域结构内的直线或绕行运动。结合元胞自动机理论，可实现群体机器人的分布式运动控制，建立群体机器人自主修复系统的元胞自动机运动规则集。通过机器人在元胞单元上的独立运动，实现整个群体系统的分布式控制修复运动。

应用于群体机器人个体的元胞运动规则，包含了机器人邻域内的环境信息与自身具体的运动方案，采用二维元胞自动机模型规则的表达形式。环境信息的具体描述为邻域位置是否存在机器人个体；具体运动方案则针对具体的环境信息，结合机器人坐标和梯度信息，依据局部范围的直线或绕行移动，规划实现相应的运动任务。处于运动状态的机器人个体按照元胞规则中的环境信息来匹配对应的元胞规则，并通过运动执行元胞规则的方案。

机器人根据邻居的环境信息进行元胞规则的判断，若传感器检测无响应，表明该方位无机器人存在；若有机器人存在且进行信息交互，则记录该方位邻居机器人状态信息。为了实现运动状态的机器人个体从聚集体中初始位置的有序分离，并沿着聚集体边缘顺时针运动至目标构型体区域的空缺位置，结合机器人邻域与传感器的方位信息，制定了如图8所示的12条适用于修复任务的元胞运动规则。其中，规则1～8用于绕聚集体边缘运动以及2.2.1节中第一类运动激发条件下的运动规划，规则9～12用于第二类运动激发条件下的运动规划。该规则集始终让机器人保持顺时针绕行趋势，且每运动至一处新位置需匹配新的元胞规则，实现运动的连续性。

图8 元胞运动规则示意图

2.2.3 修复进程结束判定

如图9所示，于自诊断阶段生成的修复目标构型信息使用函数的形式，将期望图形的外边缘轮廓函数表达式给出。当目标构型的边缘位置空缺时，触发以目标构型的外边缘轮廓为基准的终止判定。机器人内部运动时通过更新坐标值，对局部范围的构型信息进行识别，与外边缘函数进行匹配。而当存在机器人占据构型的外边缘轮廓时，则触发以梯度信息为基准的终止判定。

图9 运动停止判断方法

1) 边缘终止判定

运动状态机器人进入目标构型体区域后，沿着已成型体的边缘对空缺位置填补。机器人结合感知的局部范围环境信息，匹配相应的元胞运动规则，依据运动方向与邻域方位信息，预测下一步运动位置。如图9a)所示，当机器人预测出下一步运动抵达的位置处于目标构型外轮廓函数之外，即将离开目标构型体区域，则触发边缘终止条件，个体在当前位置停止运动，做最后一次坐标更新，随后切换至终止状态。

2) 梯度终止判定

在某运动状态机器人运动至目标构型体区域之前，已有一部分机器人填补至空缺区域并终止运动。如图9b)所示，当该个体进入目标构型区域后，若检测到下一运动方向的晶格位置处存在终止状态机器人，且其梯度值与自身梯度值相同，即：当前填充层内已有个体将目标构型外边缘轮廓填充完成，但目标构型体内部区域仍存在空缺位置待填充。此时触发梯度终止条件，个体在当前位置停止运动，对当前位置做坐标更新，并切换至终止状态。

3 群体系统形态自修复方法实验验证

基于多智能体仿真软件Netlogo，对局部缺失情况下的群体形态自修复方法进行仿真验证；同时也研发了具有一定的感知、交互与运动能力的小型移动机器人，完成了16台移动机器人的自修复实验验证。

3.1 形态自修复方法仿真验证

基于Netlogo软件搭建了大规模群体机器人形态自修复仿真验证平台。由于群体机器人系统的修复工作展开于自主成型任务实现之后，故仿真初始结合成型目标，将群体系统排布成相应的几何形状，并在此基础上对已成型体形状的随机区域做移除缺失处理。故仿真修复验证主要针对已成型体局部缺失情况下的形态自修复算法展开。

3.1.1 自修复方法的可行性验证

假设所有机器人初始按照成型目标构型紧密排布在初始聚集区域，随后人为随机移除部分区域机器人，造成已成型体的局部缺失。基于上述实验平台，通过机器人内嵌自修复算法，展开不同种类构型的修复工作，即正方形、三角形、圆形以及箭头状构型，最终实现将现有规模下的机器人修复为原始成型构型经缩放后的相似形状。图10a)～10d)分别展示了正方形、三角形、圆形及箭头构型部分缺失情况下修复过程。图中的ticks代表Netlogo软件的运行时间步长。

在图10a)中，当已成型体发生缺失后，应用2.1.1节缺失部位检测方法，检测出缺失部分A；接下来由2.1.2节中的方法选出规模识别的领导者，进而识别出缺失后系统的规模B；在统计出缺失后群机器人规模后，与原有机器人数量比较，得出缩放比例，由2.1.3节策略指导形成修复目标构型C；最后在2.2节提出的修复运动方法控制下，进行自修复运动过程执行D；在执行完所有操作后，得到自修复后构型E。

图10 正方形、三角形、圆形和箭头的自修复仿真实验

3.1.2 自修复方法的可扩展性验证

可拓展性是群体机器人系统的基本属性。以图11所示的50×50规模的正方形构型作为已成型体，选取不同规模的缺失区域进行修复仿真验证。基于50×50规模正方形已成型体系统，分别对其部分区域作缺失处理，在仿真软件Netlogo中实现最终修复构型为20×20,23×23,25×25,28×28,30×30,33×33,35×35,38×38,40×40,43×43,45×45,48×48的缺失区域可扩展性实验。实验结果如图11中A～L系列所示：

图11 自修复方法可扩展性仿真实验

综合上述实验数据和仿真结果拟合出缺失仿真耗时和缺失规模之间的二次函数关系(见图12)。处于修复目标构型体外区域的机器人数量，随着缺失规模的变化呈现出二次函数的变化，且在缺失一半机器人时达到巅峰值。而处于修复目标构型体外区域需执行元胞运动规则，运动至缺失区域填充空缺位置，每运动一步即对应一个时间步长，因此仿真耗时也随着机器人数量的增加而线性增长，最终呈仿真耗时与缺失规模之间呈二次关系。

图12 缺失仿真耗时与缺失规模关系图

3.2 形态自修复方法实物验证

仿真环境中的实验验证基于理想条件，对于实物机器人的元器件差异性、信息处理速度差异性和通信干扰等问题无法进行准确评估。因此，以仿真模型为设计参考，搭建移动机器人Cilibot实物，外形尺寸仅为4.5 cm×4.5 cm×4.8 cm，如图13所示。并对本文提出的形态自修复算法做小规模的硬件实物验证。

图13 Cilibot实物图与爆炸图

以Cilibot机器人为自主修复任务载体，将群体机器人形态自修复算法内嵌至控制器中。以正方形构型体为例，在规则排列好的已成型体基础上移除一部分机器人，作局部缺失处理，针对缺失后的已成型体自修复问题，展开相应的实物验证(见图14)。

图14 群体系统自修复实物实验验证

修复任务开始前，规则排布的群体机器人系统局部区域内的个体被人为移除。处于循环检测周围环境状态的机器人检测出周围邻域发生机器人缺失后，开启修复的自诊断阶段(见图14中A1)，分化出缺失边缘状态机器人后，进行系统规模的识别，并结合给定的成型信息自主生成修复目标构型，通过个体间的交互完成梯度值的生成(见图14中A2)。满足梯度在局部范围内最大的机器人被激活，从初始聚集体中分离并依据元胞运动规则集做绕行运动(见图14中A3，A4)，且绕行过程中运动个体依据运动防撞阻塞机制，向局部范围的机器人做运动压制(见图14中A5)。进入修复目标构型区域的运动状态个体根据终止条件的判定，完成对空缺位置的填充(见图14中A6)，直至所有机器人均运动至空缺区域，完成已成型体的形态自修复任务(见图14中A7)。

4 结 论

主要研究结论如下：

1) 提出了一种基于分层策略的群体机器人自主修复方法：采用“分层剥离、分层填充、迭代循环”的分层策略，将自主修复的全局行为转化为边缘个体的局部行为，解决了大规模群体在修复运动过程中运动冲突和规划干扰等问题。

2) 提出了一种针对受损群体机器人系统的自诊断方法：针对发生局部缺失的已成型体，对其具体缺失现状作损伤检测分析，并根据分析结果识别当前系统规模，基于原始构型信息自主生成修复目标构型作为等密度缩放修复的解决方案，为修复任务提供目标驱动。

3) 提出了一种以元胞运动规则为核心的运动控制方法：基于元胞自动机理论，构建了基于个体状态与周围环境信息的运动规则集，解决了群体机器人自主修复过程中的“谁先走”、“怎么走”、“到哪里”3类决策问题。

下一步工作将围绕复杂构型与复杂环境下的群体机器人系统自愈机制、较大规模的机器人实物平台验证等方面进行深入研究。