一種柔性縮放的群機器人形態自修復方法

王蓀馨, 王彥明, 孔杰, 申高攀

(1.西安理工大學 機械與精密儀器工程學院, 陜西 西安 710048; 2.西北工業大學 機電學院, 陜西 西安 710072)

近年來，得益于通訊傳感、智能控制、先進制造等諸多領域的蓬勃發展和技術融合，群體機器人技術為愈發復雜的多任務場景問題提供了有效的解決思路和可行方案[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 修復構型的形態再生

修復構型的形態再生過程可分為以下2步：

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類決策問題。

下一步工作將圍繞復雜構型與復雜環境下的群體機器人系統自愈機制、較大規模的機器人實物平臺驗證等方面進行深入研究。