基于改進免疫啟發(fā)群聚集算法的群機器人自恢復(fù)方法

劉養(yǎng)菊，倪建軍

(河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 常州 213022)

0 引 言

群機器人通過許多自治機器人進行交互、協(xié)調(diào)，涌現(xiàn)群體智能來合作完成相對復(fù)雜的任務(wù)，比單機器人有更高的魯棒性能[1]，這意味著當(dāng)群體中的某些機器人發(fā)生故障時，剩余的健康機器人能夠繼續(xù)完成剩余的任務(wù)。但是這需要2個假設(shè)：1)健康機器人的數(shù)量要遠多于故障機器人的數(shù)量；2)故障機器人不能干擾健康機器人進行正常的工作。最近的研究表明群體機器人系統(tǒng)并未如起初預(yù)想的那么健壯[2-3]。

故障恢復(fù)成為群機器人系統(tǒng)中最重要和最具挑戰(zhàn)性的熱點問題之一[4-5]。文獻[6]提出了一種基于廣義隨機Petri網(wǎng)的錯誤恢復(fù)框架，這種框架可以模擬發(fā)生在真實的環(huán)境中的各種錯誤情況，從而能夠使機器人自主地進行故障恢復(fù)。文獻[7]提出了一種遞歸和分布式的自修復(fù)方法，結(jié)合切換拓?fù)淇刂品椒ê瓦f歸方法恢復(fù)移動機器人網(wǎng)絡(luò)的同步性和連通性。文獻[8]基于貝葉斯決策規(guī)則和分布式智能技術(shù)，提出了一種能夠適應(yīng)動態(tài)系統(tǒng)的概率性多機器人巡查策略。然而，這些方法有許多不足。其中一些故障恢復(fù)方法只針對故障機器人本身，沒有充分考慮多機器人協(xié)作的優(yōu)勢，另外基于規(guī)則的一些故障恢復(fù)方法的規(guī)則庫通常是不完整的。

近年來，生物啟發(fā)式方法受到越來越多的學(xué)者關(guān)注。文獻[9]受螢火蟲的同步閃光行為的啟發(fā)，提出了一種簡單的算法來檢測群體機器人系統(tǒng)中的故障機器人，被檢測出來的故障機器人將被其他機器人修復(fù)或移除。文獻[10]提出了基于行為的容錯模塊控制方法處理多機器人邊界巡邏的容錯問題。文獻[11]基于免疫啟發(fā)算法，設(shè)計了一系列規(guī)則隔離故障機器人，以減少對群體的影響并修復(fù)故障機器人。文獻[12]基于免疫系統(tǒng)中肉芽腫形成(granuloma formation)機制，提出了一種免疫啟發(fā)群機器人自修復(fù)方法。上述生物啟發(fā)式方法中，免疫啟發(fā)是主要的研究方向之一，因為動物的免疫系統(tǒng)機制與群機器人系統(tǒng)中自恢復(fù)問題極為相似[13]。然而，對于復(fù)雜的自恢復(fù)問題，現(xiàn)有的免疫啟發(fā)算法過于簡單而不能有效地解決問題。針對上述問題，本文提出一種改進的免疫啟發(fā)自修復(fù)方法，以群聚集算法為基礎(chǔ)，結(jié)合離散粒子群算法，引入包含影響故障恢復(fù)各種因素的適應(yīng)度函數(shù)用來改善免疫啟發(fā)算法的性能，并通過仿真實驗驗證該方法的有效性。

1 問題描述與相關(guān)工作

在本文群機器人系統(tǒng)中，有一系列的自治和同類機器人，標(biāo)號為Ri, i=1,2,…,N, N代表群機器人系統(tǒng)中機器人的數(shù)量。每個機器人都是全向移動的并且能夠和其他機器人進行信息交換。一個紅外輻射發(fā)光器分布在未知環(huán)境中，且發(fā)出能夠被機器人感知的一些信息。該系統(tǒng)的核心任務(wù)是群機器人以聚集狀態(tài)成功到達發(fā)光器所在的目標(biāo)區(qū)域。

1.1 群機器人系統(tǒng)的任務(wù)描述

為了使機器人在保持聚集狀態(tài)的同時一起向正確的方向移動，幾個協(xié)作規(guī)則制定如下：

1)防止聚集狀態(tài)被破壞。如果某一機器人遠離群體中心，它必須返回向群體中心移動。

2)為了避免碰撞，機器人之間必須保持某一最小的距離。

3)為了確保群體準(zhǔn)確地移向發(fā)光器，引入對稱破裂機制[14]。其原理是位于被發(fā)光器照亮的區(qū)域的機器人的避障半徑大于處于暗處的機器人的避障半徑。

如圖1所示(方格代表被照亮的機器人，斜線代表未被照亮的機器人)，機器人B被發(fā)光器照亮，機器人A未被發(fā)光器照亮。由于機器人A位于機器人B的避障半徑內(nèi)，機器人B將遠離機器人A并向發(fā)光器移動。而機器人A避障半徑范圍內(nèi)檢測不到機器人B，不會產(chǎn)生避障行為。

圖1 對稱破裂機制

在機器人移動的過程中，機器人群體的中心位置與發(fā)光器之間的距離DRC表示如下：

(1)

其中，Rx(i)和Ry(i)是機器人Ri的位置坐標(biāo)值，Bx和By是發(fā)光器的位置坐標(biāo)值。本文中群機器人的移動過程被稱為ω算法，文獻[12,14]對該算法進行了詳細介紹。

1.2 群機器人系統(tǒng)的故障模式

本文研究機器人系統(tǒng)的局部故障——能量供應(yīng)不足故障。當(dāng)這種故障出現(xiàn)時，可以有充足的能量使機器人進行信息交流，但是沒有足夠的能量驅(qū)動發(fā)動機使機器人進行移動。

基于1.1節(jié)所介紹的移動機制，能量短缺故障將對群機器人系統(tǒng)有著非常嚴(yán)重的影響，出現(xiàn)故障的機器人將干擾其他機器人的正常工作進而阻礙群體向目標(biāo)移動，該過程的影響如圖2所示。

圖2 群機器人的移動過程

1.3 群機器人系統(tǒng)的自恢復(fù)

為了解決上述故障問題，文獻[12]提出了基于免疫原理的肉芽腫形成算法。在生物免疫系統(tǒng)中，肉芽腫對宿主的防御至關(guān)重要，肉芽腫缺失將使細菌不受控制地生長和擴散，進而大大地增加致命性的感染[15]。肉芽腫形成的工作機制總結(jié)如下：1)抗原呈遞細胞激活T細胞；2)巨噬細胞、被激活的T細胞和樹突細胞釋放趨化因子和細胞因子，被釋放的這些因子將吸引和保留諸如巨噬細胞、T細胞等特定細胞群；3)特定的細胞群將移向被感染的細胞并形成肉芽腫；4)形成的肉芽腫將已感染的和未感染的細胞區(qū)分開來，進而將細菌從健康的細胞中隔離。因此絕大多數(shù)細胞將不會受病變細胞的影響。免疫系統(tǒng)中的肉芽腫的形成機制適用于群機器人系統(tǒng)的故障自恢復(fù)。本文將肉芽腫形成中的相關(guān)概念映射到自恢復(fù)問題，具體如表1所示。

表1 概念映射

肉芽腫形成肉芽腫形成算法被感染的巨噬細胞故障機器人(低電量機器人)未被感染的巨噬細胞健康機器人(電量充足)T細胞供體機器人趨化因子等故障機器人發(fā)送的信號

肉芽腫形成算法的工作過程如下：1)隨機分配群機器人的初始位置，并且各機器人之間可以相互通信；2)群機器人向目標(biāo)移動；3)在移動過程中若出現(xiàn)故障機器人，故障機器人將停止移動并發(fā)送能被非故障機器人識別的故障信號；4)通過故障信號將非故障機器人選為供體的機器人將向故障機器人移動，供體機器人將隔離故障機器人，并與故障機器人分享能量將其修復(fù)，剩余的其他機器人將忽視故障機器人和供體機器人繼續(xù)進行正常的工作。

2 改進的自恢復(fù)方法

上文中的自恢復(fù)方法存在一些問題，如果有太多的供體機器人去修復(fù)故障，將會導(dǎo)致群機器人系統(tǒng)整體的工作效率降低，或者機器人有因大量消耗能量而發(fā)生故障的趨勢。因此如何從群機器人系統(tǒng)中合理地選取供體機器人去修復(fù)相應(yīng)的故障機器人至關(guān)重要。為了解決這個問題，本文引入離散粒子群算法對肉芽腫形成算法進行改進。

粒子群算法是一種基于群體智能的全局優(yōu)化算法，其所描述的粒子位置和速度都是基于連續(xù)變量的，為了解決建模在離散空間的問題，需要將粒子群算法離散化。本文使用基于整數(shù)編碼的離散粒子群算法，根據(jù)研究問題的特點，建立粒子和研究問題的對應(yīng)關(guān)系，并對離散粒子群算法進行相應(yīng)的改進。本文將故障機器人的數(shù)量標(biāo)記為F，非故障機器人的數(shù)量標(biāo)記為H，則群體中總機器人數(shù)量為N=F+H。

2.1 離散編碼方式

在本文中，每個粒子代表給故障機器人分配供體機器人的一種方式。為了確保整個群體的工作效率，規(guī)定每個故障機器人最多擁有m個供體機器人。利用供體機器人的標(biāo)號進行編碼，粒子的長度為m×F。第k個粒子可表示為：

(2)

(3)

其中，RH(L)代表供體機器人的標(biāo)號,j=1,2,…,F代表故障機器人的數(shù)目。圖3表示在有10個機器人的群體中，有2個機器人發(fā)生故障且m=3時粒子的編碼情況。例如粒子X1中，3號供體機器人修復(fù)故障機器人1，1號供體機器人修復(fù)故障機器人2。

圖3 粒子編碼方式

2.2 粒子更新方式

在粒子群算法中，粒子的位置移動是基于粒子的當(dāng)前狀態(tài)、自身最佳狀態(tài)和群體最佳狀態(tài)之間相互作用的結(jié)果，與此類似，離散粒子群算法的粒子更新公式如下：

(4)

其中，Pk(t)和Pg(t)分別是t時刻的第k個粒子經(jīng)歷的個體最優(yōu)位置和所有粒子經(jīng)歷的全局最優(yōu)位置，r代表[0,1]之間的隨機數(shù)，c1和c2分別為個體因子和群體因子，ω(t)為慣性權(quán)重，表示為：

(5)

其中，ωmax和ωmin分別是權(quán)重最大值和最小值，T和t分別是最大的迭代次數(shù)和當(dāng)前迭代次數(shù)。F3相當(dāng)于對粒子Xk的變異操作，為了使粒子進化過程中有更好的多樣性，本文隨機使用交換變異操作和插入變異操作這2種變異方法中的一種[16]。F2相當(dāng)于粒子β和Pk(t)的交叉操作，表示粒子根據(jù)自己的最優(yōu)位置進行調(diào)整。本文使用基于工件優(yōu)先順序的交叉操作方法[17]。F1相當(dāng)于粒子α和Pg(t)的交叉操作，表示粒子根據(jù)全局的最優(yōu)位置進行調(diào)整，交叉方法跟F2相同。

2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是判斷粒子群進化過程中粒子優(yōu)劣的依據(jù)，本文在綜合考慮各故障機器人和非故障機器人的位置和能量信息基礎(chǔ)上，適應(yīng)度函數(shù)定義如下：

(6)

其中，ω1和ω2分別是距離信息和能量信息的貢獻權(quán)值，Djh表示故障機器人Rj與所有的非故障機器人之間的距離，Djd表示故障機器人Rj與其相應(yīng)的供體機器人之間的距離，優(yōu)化函數(shù)ρj定義如下：

(7)

其中，能量比E(i,j)為供體機器人所能分享的能量和故障機器人被修復(fù)所需要的能量之比，定義如下：

(8)

其中，ψ(i)為第i個供體機器人所具有的能量，φ(j)為修復(fù)第j個故障機器人所需要的能量，ET為機器人正常工作的能量閾值。如果有多個供體機器人修復(fù)同一個故障機器人，將考慮所有供體機器人的能量總和。

從適應(yīng)度函數(shù)定義可知，某粒子的適應(yīng)度函數(shù)越小，該粒子成為最優(yōu)粒子的可能性越大。從距離角度來看，越靠近故障機器人的健康機器人，越可能去修復(fù)故障機器人。同時，機器人的能量因素也被充分考慮，當(dāng)某個機器人的能量ψ(i)小于能量閾值ET時，該機器人將不具有成為供體的資格。

改進后的群機器人自恢復(fù)系統(tǒng)流程如圖4所示。

圖4 改進的自恢復(fù)算法流程圖

3 仿真實驗與結(jié)果分析

為了驗證本文所提出的改進算法在群機器人自恢復(fù)系統(tǒng)的性能，將其與原肉芽腫形成算法[12](簡稱原算法)進行比較，并在Matlab平臺進行仿真實驗。實驗中，系統(tǒng)共有10個機器人，其電池容量設(shè)為5000 J，驅(qū)動機器人移動的能量最小值為500 J(若某個機器人能量小于500 J，則認(rèn)為發(fā)生故障)，其余參數(shù)如表2所示。

表2 改進算法的實驗參數(shù)

參數(shù)值備注C12個體學(xué)習(xí)因子C22群體學(xué)習(xí)因子ωmax1.5權(quán)重最大值ωmin0.7權(quán)重最小值ET/J1500能量閾值ω10.6距離權(quán)重ω20.4能量權(quán)重

本文使用網(wǎng)格法建立機器人實驗環(huán)境模型[18]，環(huán)境大小為70×70。為了簡化實驗，將機器人視為質(zhì)點，且所有機器人信息交流沒有延時。機器人的速度設(shè)為1/步，能量消耗為10 J/步，供體機器人充電速度為80 J/步。當(dāng)群機器人距目標(biāo)(發(fā)光器)的距離在5范圍內(nèi)時，可認(rèn)為任務(wù)完成。為了減小算法隨機性的影響，每次實驗執(zhí)行10次。為了評價算法的性能，定義3種指標(biāo)：群機器人系統(tǒng)到達目標(biāo)的執(zhí)行步數(shù)(STP)、機器人剩余能量的均值(ARE)、能量消耗百分比(PE)。指標(biāo)PE定義如下：

(9)

其中，IE(i)和RE(i)分別為機器人Ri的初始能量和剩余能量。

1)單故障機器人實驗。

在此實驗中，只有一個機器人發(fā)生故障。目標(biāo)的位置為(60,60)，機器人R2的初始能量為500 J，其余機器人的初始能量均為5000 J。仿真結(jié)果如圖5與圖6所示。

圖5 單故障機器人時使用改進算法的能量變化

圖6 單故障機器人的10次實驗中群體中心到目標(biāo)的距離變化

圖5顯示了使用改進算法時群機器人的能量變化過程，圖中顯示在第3步～第17步時，供體機器人R4給故障機器人R2充電。圖6顯示了10次實驗中使用2種方法時群機器人中心到目標(biāo)的距離變化過程，可以看出，群機器人均能到達目標(biāo)區(qū)域，但是使用改進算法比原算法需要的總步數(shù)少。

2)多故障機器人實驗。

為了進一步測試改進算法的性能，本文進行多個機器人同時發(fā)生故障的實驗。其中以3個故障機器人為例，機器人R2，R4，R7的初始能量分別為500 J、560 J、600 J，其余的設(shè)置均不變。仿真結(jié)果如圖7與圖8所示。

圖7 多故障機器人時使用改進算法的能量變化

圖8 多故障機器人的10次實驗中群體中心到目標(biāo)的距離變化

圖7顯示了使用改進算法時群機器人的能量變化過程，圖中顯示所有故障機器人均可以被修復(fù)(機器人R5，R6，R8分別作為R2，R4，R7的供體)。圖8顯示了10次實驗中使用2種方法時群機器人中心到目標(biāo)的距離變化過程，可以看出，改進算法大約需要70步到達目標(biāo)，而原算法則需要80步。

表3 各個參數(shù)指標(biāo)對比

故障數(shù)目算法ARE/JPE/%STP1改進算法3768.817.1768原算法3747.417.64703改進算法2857.422.0672原算法2713.925.97785改進算法1996.627.8781原算法184433.3888

表3統(tǒng)計了在故障數(shù)目不同的情況下各個參數(shù)指標(biāo)值，從表中可以看出，在故障機器人數(shù)目相同時，改進算法下的3種指標(biāo)均優(yōu)于原算法的。說明改進算法在修復(fù)故障的同時，以更少的能量和更短的時間使群機器人系統(tǒng)完成任務(wù)。同時對群體中心到目標(biāo)的距離采用曼-惠特尼U檢驗[19]進行差異顯著性檢驗。當(dāng)故障機器人數(shù)為1和2時，得到的概率P值分別為0.533，0.491，都大于顯著性水平0.05，說明2種算法沒有明顯差異。而當(dāng)故障機器人數(shù)目繼續(xù)增加時，P值小于顯著性水平0.05，說明2種算法存在顯著差異。結(jié)合表3的分析，可以看出改進算法顯著優(yōu)于原算法。

4 有效性分析

為了討論本文算法在復(fù)雜環(huán)境下的有效性，在環(huán)境中引入障礙物，其他初始條件均與上述3個故障機器人時相同。實驗結(jié)果如表4所示，可以看出，當(dāng)有障礙物時雖然消耗的能量和時間有所增加，但是群機器人系統(tǒng)依然能避開障礙物并完成故障恢復(fù)功能，說明該算法在有障礙物的環(huán)境中能夠有效地處理故障自恢復(fù)問題。

下面討論改進算法在總機器人的個數(shù)發(fā)生改變時的有效性，將系統(tǒng)中總機器人的個數(shù)設(shè)置為20，故障個數(shù)分別設(shè)為1, 6, 10。實驗結(jié)果如表5所示?？梢钥闯鲭S著機器人數(shù)量的增加，改進算法依然能處理群機器人系統(tǒng)的故障自恢復(fù)問題。

表4 改進算法在有無障礙情況下的指標(biāo)對比

ARE/JPE/%STP有障礙物2574.629.3285無障礙物2857.422.0672

表5 增加機器人情況下的指標(biāo)對比

故障機器人數(shù)目ARE/JPE/%STP1762323.32926512629.56114103465.432.86121

5 結(jié)束語

本文對群機器人系統(tǒng)的局部故障自恢復(fù)問題進行了研究，對文獻[12]中所提算法作了進一步改進。改進算法通過引入離散粒子群算法獲取最佳的修復(fù)方案來完成對故障機器人的修復(fù)任務(wù)。仿真實驗表明，當(dāng)機器人發(fā)生故障時，改進算法能為故障機器人選取合適的供體機器人，并完成故障修復(fù)。通過比較實驗，該算法能更快更好地使群機器人系統(tǒng)完成任務(wù)，提高了系統(tǒng)的魯棒性。

參考文獻：

[1] Navarro I, Matía F. An introduction to swarm robotics[J]. ISRN Robotics, 2013, doi: 10.5402/2013/608164.

[2] Ohkura K, Yu Tian, Yasuda T, et al. Robust swarm robotics system using CMA-NeuroES with incremental evolution[J]. International Journal of Swarm Intelligence and Evolutionary Computation, 2015,4(2), doi:10.4172/2090-4908.1000125.

[3] Haek M A, Ismail A R, Basalib A O A, et al. Exploring energy charging problem in swarm robotic systems using foraging simulation[J]. Jurnal Teknologi, 2015,76(1):239-244.

[4] Frei R, McWilliam R, Derrick B, et al. Self-healing and self-repairing technologies[J]. International Journal of Advanced Manufacturing Technology, 2013,69(5-8):1033-1061.

[5] Eoh G, Choi J S, Lee B H. Faulty robot rescue by multi-robot cooperation[J]. Robotica, 2013,31(8):1239-1249.

[6] Park J T, Song J B. Error recovery framework for integrated navigation system based on generalized stochastic Petri nets[J]. International Journal of Control Automation and Systems, 2009,7(6):956-961.

[7] Ju Jianjun, Liu Zhe, Chen Weidong, et al. Switched topology control and negotiation of distributed self-healing for mobile robot formation[M]// Communications in Computer & Information Science. Springer, 2014,462:562-574.

[8] Portugal D, Rocha R P. Cooperative multi-robot patrol with Bayesian learning[J]. Autonomous Robots, 2016,40(5):929-953.

[9] Christensen A L, Ogrady R, Dorigo M. From fireflies to fault-tolerant swarms of robots[J]. IEEE Transactions on Evolutionary Computation, 2009,13(4):754-766.

[10] Marino A, Parker L E, Antonelli G, et al. A fault-tolerant modular control approach to multi-robot perimeter patrol[C]// Proceedings of the 2009 International Conference on Robotics and Biomimetics. 2009:735-740.

[11] Timmis J, Andrews P, Hart E. On artificial immune systems and swarm intelligence[J]. Swarm Intelligence, 2010,4(4):247-273.

[12] Timmis J, Ismail A R, Bjerknes J D, et al. An immune-inspired swarm aggregation algorithm for self-healing swarm robotic systems[J]. Biosystems, 2016,146:60-76.

[13] Raza A, Fernandez B R. Immuno-inspired robotic applications: A review[J]. Applied Soft Computing, 2015,37:490-505.

[14] Bjerknes J D. Scaling and Fault Tolerance in Self-organized Swarms of Mobile Robots[D]. University of the West of England, Bristol, UK, 2009.

[15] Sandor M, Weinstock J V, Wynn T A. Response to Doenhoff: Granulomas: These gizmos are cool![J]. Trends in Immunology, 2003,24(4):169-170.

[16] Sang Hongyan, Gao Liang, Pan Quanke. Discrete artificial bee colony algorithm for lot-streaming flowshop with total flowtime minimization[J]. 中國機械工程學(xué)報(英文版), 2012,25(5):990-1000.

[17] Piroozfard H, Hassan A, Moghadam A M, et al. A hybrid genetic algorithm for solving job shop scheduling problems[C]// MIMEC2013. 2013:559-563.

[18] Tanzmeister G, Friedl M, Wollherr D, et al. Efficient evaluation of collisions and costs on grid maps for autonomous vehicle motion planning[J]. IEEE Transactions on Intelligent Transportation Systems, 2014,15(5):2249-2260.

[19] 孔祥芬,何楨,車建國. SPC中非正態(tài)過程穩(wěn)定性的檢驗研究[J]. 組合機床與自動化加工技術(shù), 2008(5):16-19.