蜂群激發(fā)抑制與刺激響應(yīng)相結(jié)合的群機(jī)器人區(qū)域覆蓋算法

曹 勇，肖人彬

(華中科技大學(xué)人工智能與自動化學(xué)院，武漢 430074)

0 引言

區(qū)域覆蓋的目的是在未知的環(huán)境中，通過一定的手段對未知區(qū)域進(jìn)行快速、有效的探索從而得到盡可能完善的地圖信息。區(qū)域覆蓋技術(shù)在現(xiàn)實(shí)生活中具有非常多的應(yīng)用場景。例如在輔助掃雷[1]、幫助人類除草[2]、農(nóng)作物種植與收割[3]、清洗玻璃[4]、清理泄漏石油[5]等領(lǐng)域，區(qū)域覆蓋技術(shù)都能夠有效發(fā)揮作用。在早期的研究中，多采用單個機(jī)器人探索未知環(huán)境，得到地圖信息；但是單個機(jī)器人的能力有限，探索環(huán)境的效率較低，并且系統(tǒng)的魯棒性較差，機(jī)器人的故障會使整個系統(tǒng)癱瘓從而導(dǎo)致區(qū)域覆蓋任務(wù)無法繼續(xù)進(jìn)行[6]。

群機(jī)器人是一種特殊的多機(jī)器人系統(tǒng)[7]。群機(jī)器人系統(tǒng)具備以下特征[8]：1)自治性：個體機(jī)器人作為一個獨(dú)立存在的物理實(shí)體，能夠自主做出一些簡單的決策；2)去中心化：系統(tǒng)沒有中心控制層；3)局部感知能力：每個個體只能夠感知到局部范圍內(nèi)的信息而無法獲取全局的信息；4)個體能力有限：系統(tǒng)中的每個個體的能力有限，當(dāng)缺失較少數(shù)量的個體，對系統(tǒng)的整體性能影響不大。群機(jī)器人系統(tǒng)所具備的上述特征使其具有魯棒性、規(guī)模彈性和靈活性等優(yōu)勢。

現(xiàn)有的研究多采用啟發(fā)式算法對群機(jī)器人區(qū)域覆蓋問題進(jìn)行求解。Cheng等[9]提出一種啟發(fā)式覆蓋算法，該算法在靠近彼此以獲得更多的信息減少覆蓋冗余和遠(yuǎn)離彼此獲得更大的覆蓋量這兩者之間做出均衡選擇，能夠在一定程度上提升覆蓋率，但是算法的計算量大、易造成維數(shù)災(zāi)難。李慧勇[10]提出了一種改進(jìn)的基于NC(Node Counting)算法的機(jī)器人全區(qū)域覆蓋算法，該算法在NC算法上引入方向變量，使機(jī)器人盡可能減少重復(fù)覆蓋，但沒有考慮到多個機(jī)器人相遇，占據(jù)同一個柵格的情況。Jeon[11]提出基于Boustrophedon路徑算法的DmaxCoverage算法，在該算法中機(jī)器人對于簡單、無障礙的環(huán)境有更高的優(yōu)先級，剩下難以覆蓋的區(qū)域由人工協(xié)助完成，但某些應(yīng)用場景如無人搜索救援很難實(shí)現(xiàn)人工協(xié)助，限制了其使用范圍。Ranjbar-Sahraei[12]提出基于信息素的多機(jī)器人覆蓋算法，該算法會對機(jī)器人覆蓋過的區(qū)域留下標(biāo)記物質(zhì)，引導(dǎo)其他機(jī)器人不再進(jìn)入此區(qū)域，但是這種算法容易導(dǎo)致某些中心區(qū)域無法被覆蓋。Wagner等[13]將蟻群算法、李冠男等[14]將粒子群算法分別應(yīng)用于群機(jī)器人區(qū)域覆蓋問題中，這些群智能優(yōu)化算法雖然能取得一定的效果，但只是利用了群智能算法中個體眾多的優(yōu)勢，沒有充分發(fā)揮群機(jī)器人之間充分協(xié)作的特點(diǎn)。文獻(xiàn)[15]利用群機(jī)器人與環(huán)境之間的交互，基于刺激響應(yīng)模型提出了基于黃蜂群算法的群機(jī)器人區(qū)域覆蓋算法，但是仍然沒有考慮群機(jī)器人之間的協(xié)作問題，并且群機(jī)器人在覆蓋過程中可能出現(xiàn)擁堵問題。

群機(jī)器人涉及到數(shù)量較多的個體，在區(qū)域覆蓋過程中，如何確定群機(jī)器人的交互規(guī)則以及交互方式，使機(jī)器人個體之間進(jìn)行協(xié)作并且使機(jī)器人在未知區(qū)域中均勻分布，最終使整個機(jī)器人群體快速、有效地創(chuàng)建信息更加完整的地圖至關(guān)重要。

蜂群勞動分工是自然界中的蜂群為了高效完成任務(wù)而形成的一種任務(wù)分配方式[16]。激發(fā)抑制是蜂群勞動分工的重要體現(xiàn)方式。蜂群勞動分工具有如下特征：1)蜂群勞動分工能夠給不同的個體(例如蜜蜂個體生理年齡的不同、螞蟻個體形態(tài)大小的不同)分配不同的任務(wù)，也就是說將不同的任務(wù)分配給最適合完成這種任務(wù)的個體，從而保證種群利益的最大化，并且這種分配方式隨著種群的實(shí)際需求而發(fā)生改變；2)在蜂群勞動分工系統(tǒng)中，不存在中心控制層、整個種群是一個自治系統(tǒng)、種群中單個個體微不足道、種群中的個體之間存在某些局部交互規(guī)則[17]。蜂群勞動分工系統(tǒng)中存在一種高效的個體交互規(guī)則，實(shí)現(xiàn)任務(wù)的合理分配，其特征與群機(jī)器人系統(tǒng)所具備的特征相似。因此，可將蜂群勞動分工應(yīng)用于求解群機(jī)器人區(qū)域覆蓋問題。本文將蜂群勞動分工用于求解群機(jī)器人區(qū)域覆蓋問題，結(jié)合刺激響應(yīng)模型設(shè)計蜂群激發(fā)抑制與刺激響應(yīng)相結(jié)合的算法(Algorithm for Combining bee Colony Activator Inhibition with Stimulus Response，AISRA)，使機(jī)器人個體之間緊密協(xié)作、機(jī)器人群體在未知區(qū)域中盡可能分布均勻，提高區(qū)域覆蓋效率。

1 群機(jī)器人區(qū)域覆蓋問題

1.1 問題描述

群機(jī)器人區(qū)域覆蓋問題，是指對某個封閉、未知的二維空間內(nèi)的環(huán)境進(jìn)行遍歷，最終得到該區(qū)域的部分或完整地圖。在進(jìn)行區(qū)域覆蓋的過程中，系統(tǒng)中的多個機(jī)器人獨(dú)立探索未知區(qū)域中的某一區(qū)域，每個機(jī)器人獲得面積較小的局部地圖，同時將探索到的局部地圖添加到機(jī)器人團(tuán)隊共同維護(hù)的全局地圖中。

群機(jī)器人區(qū)域覆蓋問題可簡要描述如下：

M=f(A)

(1)

式中，A代表群機(jī)器人將要探索的未知區(qū)域的狀態(tài)，f代表機(jī)器人團(tuán)隊對A的覆蓋作用，M為區(qū)域覆蓋完成之后得到的地圖。

A是由點(diǎn)集以及點(diǎn)集的狀態(tài)組成的集合，即A={(x1,y1)，(x2,y2)，……,(xn,yn)|?(xi,yi)∈[0,1]，0代表未被覆蓋，1代表被覆蓋}；在f的作用下，如果未知區(qū)域A被覆蓋，則A的狀態(tài)會發(fā)生改變，機(jī)器人團(tuán)隊由四要素構(gòu)成：(I，D，C，R)，其中I表示機(jī)器人團(tuán)隊的輸入，D表示機(jī)器人探測同伴，C為機(jī)器人之間的協(xié)作，R為機(jī)器人的運(yùn)動方向；M也是一組點(diǎn)的集合，即M={(x1,y1)，(x2,y2)，…,(xn,yn)|?(xi,yi)∈1}，與A不同的是M中點(diǎn)的狀態(tài)都為1，地圖中的這些點(diǎn)都是被群機(jī)器人覆蓋過的點(diǎn)。對于A和M，有如下關(guān)系存在：M?A，因?yàn)樵趨^(qū)域覆蓋過程中，可能存在某些區(qū)域未被完全覆蓋，得到的地圖M只是原始未知區(qū)域中的一部分。

初始狀態(tài)下機(jī)器人在A中隨機(jī)分布，進(jìn)行獨(dú)立探索，對未被遍歷的區(qū)域加以標(biāo)記：即在f的作用下，A的組成點(diǎn)(xi,yi)的狀態(tài)由0變?yōu)?。在探索過程中若機(jī)器人感知到同伴，將與同伴進(jìn)行協(xié)作、交互，以高效的方式對A進(jìn)行遍歷覆蓋。

1.2 地圖表示方法

未知環(huán)境地圖的表示方法主要有3種：柵格地圖表示法[18]、幾何地圖表示法[19]以及拓?fù)涞貓D表示法[20]。柵格地圖表示法利用占用柵格地圖來描述已知或未知的環(huán)境。在柵格地圖中，將環(huán)境劃分為固定大小的平面格點(diǎn)，每個格點(diǎn)稱為柵格，在機(jī)器人經(jīng)過探測之后按照概率值區(qū)分周圍的柵格是否存在障礙物，探索完成后便得到由許多柵格組成的柵格地圖；幾何地圖是從環(huán)境中抽取出幾何特征，將環(huán)境表示為由點(diǎn)、線、面等基本幾何特征組成的集合，地圖的這種表示方式更加簡潔，完整地反映出環(huán)境中的重要特征；拓?fù)涞貓D利用拓?fù)鋱D來表示環(huán)境，將環(huán)境中的重要特征狀態(tài)、地點(diǎn)抽象為拓?fù)鋱D中的結(jié)點(diǎn)，節(jié)點(diǎn)間的連線代表節(jié)點(diǎn)之間存在連接。

柵格地圖表示法的實(shí)現(xiàn)簡單、能較好地表達(dá)實(shí)際空間中物體位置分布，目前被廣泛應(yīng)用于自動導(dǎo)引車[21]、路徑規(guī)劃[22]、目標(biāo)搜索等領(lǐng)域[23]。本文采用這種簡單實(shí)用的地圖表達(dá)方式。

1.3 群機(jī)器人功能描述

群機(jī)器人區(qū)域覆蓋任務(wù)需要多個機(jī)器人遵循特定的規(guī)則協(xié)作完成，本文假定機(jī)器人具備如下功能：1)移動能力：每個機(jī)器人都是一個獨(dú)立的個體，能夠在探索區(qū)域中自主移動；2)局部感知能力：局部感知能力是指群機(jī)器人中每個機(jī)器人個體能夠感知到較小范圍的局部信息，例如機(jī)器人周圍是否存在其他機(jī)器人，局部感知能力是群機(jī)器人完成任務(wù)的基本能力之一，通過局部感知與個體交互才能更好的完成指定的任務(wù)；3)簡單的交互能力：交互能力是指機(jī)器人團(tuán)隊中的每個機(jī)器人個體之間進(jìn)行交互、獲取到周圍其他機(jī)器人個體信息的能力。機(jī)器人個體簡單的交互能力能夠充分利用其他個體所攜帶的信息，提高完成任務(wù)的效率；4)簡單的計算能力：用于當(dāng)某機(jī)器人與其他機(jī)器人之間有交互時，獲取相關(guān)信息并進(jìn)行一定的運(yùn)算。

2 蜂群激發(fā)抑制和刺激響應(yīng)原理與模型

2.1 激發(fā)抑制原理與模型

激發(fā)抑制模型是群智能勞動分工的典型代表之一。激發(fā)抑制模型主要描述的是個體與個體之間進(jìn)行交互的一種勞動分工模式，這種勞動分工模式的典型代表生物是蜂群[24]。激發(fā)抑制原理可作如下描述：種群任務(wù)之所以能夠保證高效分配，主要依賴于個體與個體之間的交互，個體從出生到死亡的過程中所扮演的角色不是遵循特定的順序，而是根據(jù)任務(wù)需求進(jìn)行調(diào)整，發(fā)育過程具有靈活性。具體表現(xiàn)為：個體能夠加速、延遲、甚至逆轉(zhuǎn)其行為發(fā)育來應(yīng)對族群環(huán)境的變化[25]。

Huang和Robinson[26]提出了激發(fā)抑制模型來解釋蜂群的勞動分工行為，該模型為一個verbal模型。該模型認(rèn)為激發(fā)劑和抑制劑共同決定蜜蜂個體的行為發(fā)育，激發(fā)劑和抑制劑處于平衡狀態(tài)時，個體正常發(fā)育，否則個體的發(fā)育狀態(tài)會加速或者延遲、逆轉(zhuǎn)。Beshers[27]等人則給出了verbal模型的一個定量描述，如式(2)所示：

x(t+1)=f(x(t),y(t))

(2)

其中，t為時間變量；x為個體狀態(tài)變量，用以描述個體生理年齡；y為輔助變量，用以描述抑制作用，這種抑制作用通過個體之間的交互來實(shí)現(xiàn)。函數(shù)f(x,y)與個體生理年齡x呈正相關(guān)，而與輔助變量y呈負(fù)相關(guān)，生理狀態(tài)x隨時間t的變化情況反映了個體隨時間的行為發(fā)育過程。激發(fā)抑制模型已成功應(yīng)用于動態(tài)分配問題[28]的求解。

2.2 刺激響應(yīng)原理與模型

刺激響應(yīng)模型源于Bonabcau等[29]于1996對自然界中蟻群任務(wù)分配行為的深入研究。在刺激響應(yīng)模型中，將螞蟻抽象為簡單個體，每個個體自身存在一個固定的響應(yīng)閾值θ，環(huán)境中的每個任務(wù)都對應(yīng)著一個刺激強(qiáng)度s，不同的任務(wù)對應(yīng)著不同的刺激強(qiáng)度s。當(dāng)某個體的響應(yīng)閾值θ低于某個任務(wù)的刺激強(qiáng)度s時，這個個體便開始執(zhí)行這個任務(wù)。當(dāng)執(zhí)行某個任務(wù)的個體數(shù)量慢慢增多的時候，對應(yīng)任務(wù)的刺激強(qiáng)度s也會逐步降低，如果該任務(wù)的刺激強(qiáng)度s比執(zhí)行任務(wù)的個體響應(yīng)閾值θ還要低的時候，個體可能會退出，此時的任務(wù)刺激強(qiáng)度s又可能會增加，即某個任務(wù)的刺激強(qiáng)度s會隨著執(zhí)行這項(xiàng)任務(wù)的個體數(shù)量而變化。

某個個體開始執(zhí)行任務(wù)的概率模型如式(3)所示：

(3)

式中，Si表示個體i的狀態(tài)，為0表示空閑狀態(tài)，為1表示正在執(zhí)行任務(wù)。Si由0變?yōu)?表示個體由空閑狀態(tài)轉(zhuǎn)變?yōu)閳?zhí)行某個任務(wù)。

刺激強(qiáng)度s的演化過程如式(4)：

s(t+1)=s(t)+δ-?nact

(4)

式中，δ為刺激強(qiáng)度s的單位時間增量，一般取為常數(shù)。nact為正在執(zhí)行任務(wù)個體的數(shù)量，?為衡量由于一個個體的活動而引起刺激強(qiáng)度減少的比例因子，即個體執(zhí)行任務(wù)的效率。?nact起到動態(tài)調(diào)整任務(wù)刺激強(qiáng)度的作用，如果執(zhí)行某任務(wù)的個體數(shù)量較多，刺激強(qiáng)度就越低，其他個體選擇該任務(wù)的概率就會變小，正在執(zhí)行該任務(wù)的個體也有可能退出，使任務(wù)分配達(dá)到動態(tài)平衡。刺激響應(yīng)模型在機(jī)器人救援[30]領(lǐng)域具有較好的應(yīng)用效果。

3 群機(jī)器人區(qū)域覆蓋算法

3.1 映射關(guān)系

在自然生物群體中，不同的生物個體執(zhí)行不同的任務(wù)從而完成任務(wù)分配，在群機(jī)器人區(qū)域覆蓋中，不同的機(jī)器人覆蓋不同的區(qū)域以完成區(qū)域覆蓋任務(wù)。

圖1 生物群與群機(jī)器人映射關(guān)系

圖1給出了自然蜂群與群機(jī)器人之間的映射關(guān)系。映射關(guān)系如下：將蜜蜂個體映射為機(jī)器人個體；環(huán)境中任務(wù)的刺激強(qiáng)度映射為未知區(qū)域的覆蓋狀態(tài)(未被覆蓋的區(qū)域刺激強(qiáng)度較強(qiáng)，而已被覆蓋的區(qū)域刺激強(qiáng)度較弱)；蜜蜂個體的響應(yīng)閾值映射為機(jī)器人個體的響應(yīng)閾值；蜜蜂個體的抑制劑映射為機(jī)器人之間的距離；蜜蜂個體的激發(fā)劑映射為機(jī)器人個體周圍能夠檢測到的機(jī)器人數(shù)量。在映射關(guān)系中，直接將蜜蜂個體與機(jī)器人個體對應(yīng)起來，通過激發(fā)抑制原理與刺激響應(yīng)原理，使機(jī)器人個體既能夠和環(huán)境發(fā)生交互，也能夠和其他機(jī)器人個體相互通信，實(shí)現(xiàn)個體之間的協(xié)作、對機(jī)器人的分布加以調(diào)整。

3.2 算法原理

3.2.1 刺激響應(yīng)與激發(fā)抑制結(jié)合原理

在刺激響應(yīng)模型中，主要關(guān)注的是個體與環(huán)境之間的交互，在群機(jī)器人區(qū)域覆蓋問題中表現(xiàn)為機(jī)器人根據(jù)個體自身閾值與區(qū)域中某位置刺激強(qiáng)度之間的相對關(guān)系選擇機(jī)器人的行走方向。在群機(jī)器人中個體數(shù)量較多是一大優(yōu)勢，如果不對這一加以利用就不能充分發(fā)揮群機(jī)器人的優(yōu)勢。激發(fā)抑制模型關(guān)注的是個體與個體之間的交互，將激發(fā)抑制原理應(yīng)用于群機(jī)器人的控制，能夠發(fā)揮群機(jī)器人數(shù)量上的優(yōu)勢。

由于在刺激響應(yīng)模型中只涉及到個體與環(huán)境之間的交互，無論某個機(jī)器人周圍是否存在其他機(jī)器人，這個機(jī)器人將按照自己的行走規(guī)則對未知區(qū)域進(jìn)行覆蓋，如圖2a所示。當(dāng)機(jī)器人采用這種交互方式時，圖2a中機(jī)器人1的可選方向?yàn)榧^所指方向。但是當(dāng)朝著機(jī)器人2、3、4所指向的方向行走時，可能產(chǎn)生碰撞，并且機(jī)器人2、3、4可能將機(jī)器人1周圍的未知區(qū)域進(jìn)行覆蓋，導(dǎo)致機(jī)器人1被黑色的覆蓋區(qū)域所包圍，如果機(jī)器人1從被包圍的區(qū)域行走出來就會產(chǎn)生重復(fù)覆蓋問題；由于機(jī)器人1和2、機(jī)器人2和3相隔距離較近，如果機(jī)器人都只與環(huán)境發(fā)生交互，這兩組機(jī)器人將可能發(fā)生碰撞、產(chǎn)生擁堵問題。

圖2 兩種機(jī)器人交互模型

如果該機(jī)器人不僅能夠與環(huán)境發(fā)生交互，而且還能夠與其他個體進(jìn)行交互，當(dāng)某個機(jī)器人感知到周圍存在較多的個體時，能夠有選擇的向某些方向運(yùn)行，能夠使機(jī)器人團(tuán)隊盡可能均勻地分散在未知區(qū)域中，有效減少重復(fù)覆蓋率，提升區(qū)域覆蓋效率。例如在圖2b中，機(jī)器人1感知到周圍存在機(jī)器人2、3、4，這時機(jī)器人1的可選方向?yàn)閳D2b中箭頭方向所示，機(jī)器人1能夠朝著未被覆蓋并且不擁擠的方向運(yùn)動；而機(jī)器人2和機(jī)器人3彼此都能夠感知到對方的存在，不會朝著虛線箭頭所指向的方向運(yùn)行，防止發(fā)生碰撞。從整體上看，如果采用個體與環(huán)境加個體與個體之間的交互策略，機(jī)器人能夠盡可能的分散在地圖的未知區(qū)域、減少重復(fù)覆蓋率，使機(jī)器人的每一步都盡可能朝著未被覆蓋并且不擁擠的區(qū)域運(yùn)動，使區(qū)域覆蓋效率更高效。

圖3 機(jī)器人檢測鄰域其他個體

3.2.2 個體之間的協(xié)作

在圖1的映射關(guān)系中，個體激發(fā)劑、抑制劑分別與機(jī)器人周圍的數(shù)量、個體之間的距離相對應(yīng)，根據(jù)檢測范圍內(nèi)某個體與其他個體之間的距離對抑制劑進(jìn)行調(diào)節(jié)、某個機(jī)器人周圍的其他個體數(shù)量對激發(fā)劑進(jìn)行調(diào)節(jié)。在某個個體的檢測范圍內(nèi)存在其他機(jī)器人的前提下(如圖3中的機(jī)器人R1與機(jī)器人R2、R3、R4之間)，若距離較小，個體之間傳遞的抑制劑增加，并且距離越小，抑制劑增加的速度越快；反之，若距離較大，個體之間傳遞的抑制劑減小。

對應(yīng)模型如下：

θ′i(t+1)=θ′i(t)+βi

(5)

(6)

(7)

其中，m為機(jī)器人i周圍的機(jī)器人數(shù)量，Ii為來自機(jī)器人i周圍其他機(jī)器人個體的抑制劑總和，βi為個體激發(fā)劑Ai與抑制劑Ii的比值，dij為機(jī)器人i與機(jī)器人j之間的距離，f是和dij呈正相關(guān)的距離函數(shù)。在本文中距離越小抑制劑也越小，從而導(dǎo)致激發(fā)抑制比βi越大，最終使機(jī)器人響應(yīng)閾值θ′i變大，機(jī)器人將會更大的概率停留在原地。

如果某個機(jī)器人在檢測范圍內(nèi)存在其他機(jī)器人，探索過程如圖4所示。

圖4 機(jī)器人之間距離對機(jī)器人行為的影響

當(dāng)某個機(jī)器人周圍存在其他機(jī)器人，并且距離該機(jī)器人較遠(yuǎn)時，這個機(jī)器人接收到的抑制劑減小，抑制劑減少使個體的響應(yīng)閾值減小，此時個體會以較大的概率在未知區(qū)域中進(jìn)行探索；當(dāng)某個機(jī)器人周圍存在機(jī)器人，并且距離該機(jī)器人較近時，這個機(jī)器人接收到的抑制劑隨距離的減小快速增加，抑制劑增加會使個體的響應(yīng)閾值快速增加，此時個體會以較大的概率在停留在原地。這種動態(tài)調(diào)節(jié)閾值的方式能夠避免機(jī)器人做重復(fù)的探索。

3.2.3 分布調(diào)整策略

機(jī)器人個體不僅能夠檢測一定范圍內(nèi)與其他機(jī)器人之間的距離，還能夠?qū)崿F(xiàn)簡單的信息交互，如圖5中的共享信息Info1、Info2、Info3，在本文中，共享信息為各機(jī)器人之間的距離，如圖5中距離L12、L23、L34。

假設(shè)機(jī)器人的檢測半徑為r(如圖5中機(jī)器人R2虛線范圍)，當(dāng)某個機(jī)器人與其他機(jī)器人之間的中心距離小于等于2r時(如圖5中機(jī)器人R1、R2、R3所示)，這些相鄰機(jī)器人之間能夠互相通信，獲取對方的信息，即機(jī)器人之間的共享信息具有傳遞性；例如，圖5中機(jī)器人R1與R2、R1與R3能夠直接交換信息。而R2能夠獲取R1的信息，R1又獲取到了R3的信息；因此，R2能夠通過R1間接獲取R3的信息；同理，R3能夠通過R1間接獲取R2的信息。機(jī)器人之間通過這種通信方式擴(kuò)大了感知范圍，充分體現(xiàn)出個體之間交互的優(yōu)勢。獲取整個感知區(qū)域(直接或者間接感知)的信息之后，處于邊緣部分的機(jī)器人可以選擇繼續(xù)在該區(qū)域探索或者離開該區(qū)域。

圖5 機(jī)器人之間互相通信

在機(jī)器人分布調(diào)整策略中，為了衡量某區(qū)域中機(jī)器人是否過于擁擠，定義機(jī)器人平均密度指標(biāo)。如式(8)所示：

(8)

其中，R表示區(qū)域內(nèi)直接或者間接通信的機(jī)器人所構(gòu)成的范圍，N表示R區(qū)域中機(jī)器人的個數(shù)。機(jī)器人平均密度能夠反映機(jī)器人的分布是否均衡。如果該指標(biāo)較小，說明某區(qū)域中的機(jī)器人數(shù)量太多，過于擁擠，應(yīng)當(dāng)重新調(diào)整機(jī)器人的分布情況；反之說明機(jī)器人能夠以較高的效率完成區(qū)域覆蓋任務(wù)。

在圖6中，灰色部分表示已被覆蓋的區(qū)域，這些區(qū)域被再次探索的概率較低；白色部分表示未被覆蓋的區(qū)域，這部分沒有被探索，機(jī)器人將優(yōu)先選擇探索這些區(qū)域。當(dāng)機(jī)器人1在覆蓋過程中處于圖5所示的狀態(tài)時，面臨3種選擇：1)向被覆蓋的區(qū)域運(yùn)動；2)向機(jī)器人2、機(jī)器人3、機(jī)器人4所組成的子群體運(yùn)動；3)向其他未被覆蓋的區(qū)域運(yùn)動；其中，上述3種情況中，情況1)和情況2)為圖中α角度范圍。對于情況1)，由于機(jī)器人1當(dāng)前的可選覆蓋區(qū)域有未被覆蓋的區(qū)域，根據(jù)刺激響應(yīng)模型式(9)，機(jī)器人1選擇未被覆蓋區(qū)域的概率比選擇覆蓋區(qū)域的概率大。因此，機(jī)器人1將更加傾向于遠(yuǎn)離已被覆蓋區(qū)域。對于情況2)，雖然該區(qū)域還未被覆蓋，該區(qū)域已經(jīng)存在較多數(shù)量的機(jī)器人；根據(jù)式(8)，機(jī)器人1感知到該區(qū)域較為擁擠，將遠(yuǎn)離擁擠區(qū)域，向其他方向運(yùn)動，即選擇情況3)，在圖6中即為除α角度范圍的其他未被覆蓋區(qū)域。通過上述方式，群機(jī)器人即能夠保證某一區(qū)域內(nèi)有合適數(shù)量的機(jī)器人進(jìn)行探索，也能夠保證未知區(qū)域中有機(jī)器人進(jìn)行探索，讓群機(jī)器人團(tuán)隊同時兼顧探索效率和獨(dú)立探索新的位置區(qū)域的能力，在未知區(qū)域中形成一種合理的分布。

圖6 機(jī)器人行走方向決策

機(jī)器人系統(tǒng)的這種間接感知能力，能夠使機(jī)器人的感知范圍進(jìn)一步擴(kuò)大。在獲取區(qū)域中的信息之后，某些機(jī)器人能夠選擇繼續(xù)在該區(qū)域探索或者是選擇離開，這既能在一定程度上避免資源的浪費(fèi)，又能夠使該區(qū)域不至于過于擁擠，能有效提高了區(qū)域覆蓋效率。

3.3 算法模型

基本刺激響應(yīng)模型如式(9)所示：

(9)

其中，sj為單元格j的刺激量，θi為機(jī)器人i的響應(yīng)閾值，sk為與單元格i相鄰單元格的刺激量，m為相鄰單元格的數(shù)量，T(sj)為執(zhí)行任務(wù)sj的概率。

根據(jù)機(jī)器人之間的協(xié)作規(guī)則以及機(jī)器人的分布調(diào)整策略，在基本刺激響應(yīng)模型上加以改進(jìn)，得到AISRA算法。如式(10)、(11)所示：

(10)

(11)

3.4 算法描述

算法描述如下：

初始化系統(tǒng)參數(shù)：群機(jī)器人數(shù)量n，地圖單元格數(shù)量m，單元格的刺激量s，機(jī)器人的響應(yīng)閾值θ，平均密度的閾值ηth；

loop=1；

repeat：

if 機(jī)器人周圍存在其他機(jī)器人：

計算機(jī)器人之間的距離dij；

由式(6)更新抑制劑I的大??；

由式(7)調(diào)整激發(fā)抑制比βi；

由式(5)更新自身的閾值θ′；

由式(8)計算平均密度指標(biāo)η，得到η與ηth的相對大小關(guān)系；

ifη>ηth：

由式(10)計算執(zhí)行任務(wù)概率；

elseη<ηth：

由式(11)計算得到機(jī)器人執(zhí)行任務(wù)的概率；

loop=loop+1；

until loop=CONDITION(終止條件，這里為達(dá)到最大時間步長)；

結(jié)束區(qū)域覆蓋任務(wù)，得到結(jié)果。

4 仿真實(shí)驗(yàn)

為驗(yàn)證基于激發(fā)抑制模型的群機(jī)器人區(qū)域覆蓋算法的有效性，本文使用MATLAB平臺設(shè)計兩個群機(jī)器人區(qū)域覆蓋仿真實(shí)驗(yàn)，第一個仿真實(shí)驗(yàn)用于說明AISRA分別在規(guī)則地圖、不規(guī)則地圖中的區(qū)域覆蓋效率，第二個實(shí)驗(yàn)中將AISRA與基于刺激響應(yīng)模型的黃蜂群算法進(jìn)行對比，通過兩個實(shí)驗(yàn)的實(shí)際效果驗(yàn)證本文算法的優(yōu)越性。

群機(jī)器人區(qū)域覆蓋效率的衡量指標(biāo)有覆蓋率、平均覆蓋次數(shù)、時間步長。其中，覆蓋率指的是機(jī)器人在完成區(qū)域覆蓋任務(wù)之后，所有機(jī)器人探索得到的總覆蓋面積與整個地圖可覆蓋面積的比值；平均覆蓋次數(shù)指的是所有機(jī)器人遍歷面積之和與總地圖面積的比值；時間步長指的是群機(jī)器人得到地圖時步數(shù)最多的機(jī)器人步數(shù)。

4.1 AISRA在不同環(huán)境中的覆蓋效果

在本實(shí)驗(yàn)中，選取相同規(guī)格的地圖，即設(shè)置柵格地圖大小固定為100×100，得到AISRA分別在規(guī)則地圖、不規(guī)則地圖中的區(qū)域覆蓋效率。本實(shí)驗(yàn)中機(jī)器人數(shù)量分布設(shè)置為10、20、30、40、50、60、70、80、90、100，根據(jù)實(shí)驗(yàn)結(jié)果分析不同機(jī)器人數(shù)量對區(qū)域覆蓋效果的影響。本文所用柵格地圖如圖7所示，黑色代表機(jī)器人所處的位置以及機(jī)器人已經(jīng)遍歷過的位置，白色代表未被探索到的位置(圖7所示為10×10地圖)。在實(shí)驗(yàn)中，機(jī)器人可以在平面內(nèi)的8個方向上選擇一個方向作為下一次移動的方向，機(jī)器人的可選方向如圖8所示。

圖7 10x10柵格地圖

圖8 機(jī)器人可選前進(jìn)方向

4.1.1 參數(shù)設(shè)置

1)地圖顏色初始為1，即地圖初始為白色；

2)地圖大小為100×100：如果地圖太小，機(jī)器人在地圖中會處于比較擁擠的狀態(tài)，如果地圖太大，機(jī)器人之間的通信機(jī)會較少，不利于實(shí)現(xiàn)機(jī)器人之間的交互；

3)機(jī)器人響應(yīng)閾值初始為0.1：在初始時刻，機(jī)器人在未被探索過的地圖中隨機(jī)分布，由于此時機(jī)器人周圍的環(huán)境均為初始狀態(tài)，設(shè)置機(jī)器人的響應(yīng)閾值為較小的值，可以讓機(jī)器人以更大的概率到周圍的環(huán)境中進(jìn)行探索，而停留的概率較小，在探索的過程中，由于機(jī)器人的閾值能夠自適應(yīng)調(diào)整，隨著時間的推移，機(jī)器人的閾值會慢慢得到調(diào)節(jié)；

圖9 地圖單元格刺激量為100時的平均覆蓋次數(shù)

4)地圖刺激量初始為10：當(dāng)?shù)貓D被遍歷過之后，地圖單元格的刺激量衰減為原來的0.1，如果地圖初始刺激量設(shè)置得過大，當(dāng)?shù)貓D的單元格被遍歷過一次之后的刺激量仍然大于機(jī)器人的響應(yīng)閾值，會導(dǎo)致該單元格被再次遍歷，造成地圖單元格被遍歷的次數(shù)增加，如圖9所示；如果地圖初始刺激量設(shè)置得過小，機(jī)器人在探索過程中將會受到限制，更可能以較大概率停留，導(dǎo)致覆蓋效率降低；

5)機(jī)器人數(shù)量初始化為10，后續(xù)的每一輪實(shí)驗(yàn)將機(jī)器人數(shù)量增加10，直到機(jī)器人數(shù)量達(dá)到100為止；

6)時間步長最大值取為2 500：多次仿真實(shí)驗(yàn)結(jié)果表明，最大時間步長取為2 500，每次仿真結(jié)束時，區(qū)域覆蓋率基本不發(fā)生改變。

4.1.2 仿真實(shí)驗(yàn)結(jié)果及分析

1)規(guī)則地圖

本文選取10次數(shù)據(jù)進(jìn)行平均，將10次結(jié)果的平均值作為最終結(jié)果。平均覆蓋次數(shù)指標(biāo)與覆蓋率指標(biāo)折線圖如圖10、11所示。

圖10 不同機(jī)器人數(shù)量對平均覆蓋次數(shù)的影響

圖11 不同機(jī)器人數(shù)量對覆蓋率的影響

由圖10與圖11可知，隨著機(jī)器人數(shù)量的增加，最終得到的指標(biāo)中平均覆蓋次數(shù)沒有呈現(xiàn)大幅度的增加，而是在穩(wěn)定值附近波動，并且地圖的覆蓋率隨機(jī)器人的增加得到顯著提高；這說明群機(jī)器人在區(qū)域覆蓋過程中分布調(diào)整策略起到了作用，在機(jī)器人發(fā)生擁擠的時候選擇回避，并且在檢測到周圍有其他機(jī)器人之后停留在原地的可能性更大，從而有效減少不必要重復(fù)覆蓋。

對比圖9與圖10可知，當(dāng)?shù)貓D單元格的初始值選取與機(jī)器人的響應(yīng)閾值搭配較為合理時，機(jī)器人的平均覆蓋次數(shù)能夠控制在穩(wěn)定且較小的范圍內(nèi)，而當(dāng)初始值的選取過大，并且與機(jī)器人的響應(yīng)閾值相差較大時，會導(dǎo)致機(jī)器人在區(qū)域覆蓋過程中的平均覆蓋次數(shù)增加，并且機(jī)器人的數(shù)量越多，平均覆蓋次數(shù)會增加得越明顯。

2)不規(guī)則地圖

不規(guī)則地圖如圖12所示，在地圖中黑色表示不可達(dá)區(qū)域，剩余部分為群機(jī)器人將要進(jìn)行覆蓋的未知區(qū)域。

圖12 不規(guī)則地圖

該地圖被許多突出的黑色部分分隔開來，群機(jī)器人在這種不規(guī)則地圖中進(jìn)行覆蓋時，如果不對機(jī)器人加以有效的控制某些機(jī)器人會以較大概率陷入某個角落中，導(dǎo)致區(qū)域覆蓋效率較低，或者某個角落沒有機(jī)器人到達(dá)，導(dǎo)致區(qū)域覆蓋率降低。

在AISRA的協(xié)調(diào)控制作用下，群機(jī)器人在不規(guī)則地圖中的仿真實(shí)驗(yàn)結(jié)果如圖13、14所示。

從圖13可知，在不規(guī)則地圖中，隨著機(jī)器人數(shù)量的增加，平均覆蓋次數(shù)會呈現(xiàn)上升趨勢，但是增加的幅度較小，并且在機(jī)器人數(shù)量較少(圖13中10-50)以及機(jī)器人數(shù)量較多(圖13中60-100)時平均覆蓋次數(shù)趨于穩(wěn)定，在某個穩(wěn)定值上下小幅度擺動。由圖14可知，在機(jī)器人數(shù)量較少的時候，由于機(jī)器人之間協(xié)作的機(jī)會較少，區(qū)域覆蓋率也相對較低；當(dāng)機(jī)器人數(shù)量逐步增加以后，區(qū)域覆蓋率也隨之上升。由圖13、14，在不規(guī)則地圖中，群機(jī)器人仍然能夠以較高的效率完成覆蓋任務(wù)。

圖13 不同機(jī)器人數(shù)量對平均覆蓋次數(shù)的影響

圖14 不同機(jī)器人數(shù)量對覆蓋率的影響

4.2 對比實(shí)驗(yàn)

在本實(shí)驗(yàn)中，將AISRA和黃蜂群算法置于同一場景下(柵格地圖大小為100×100)，根據(jù)兩種算法的最終區(qū)域覆蓋效果，分析AISRA相較于黃蜂群算法的有效性。

4.2.1 參數(shù)設(shè)置

在實(shí)驗(yàn)二中，柵格地圖的大小取為100×100，選取的機(jī)器人數(shù)量分別為20、40、60、80、100，與所選取的100×100柵格地圖相比，能夠代表機(jī)器人分布狀態(tài)：較為分散、適中、較為集中；AISRA參數(shù)與實(shí)驗(yàn)一中實(shí)驗(yàn)參數(shù)相同，黃蜂群算法的機(jī)器人響應(yīng)閾值選取為2，由于地圖單元格的刺激量為10，當(dāng)?shù)貓D的單元格被遍歷過一次之后衰減為0.1，即此時的單元格刺激量變?yōu)?，而機(jī)器人的響應(yīng)閾值為2，比單元格的刺激量1要大，機(jī)器人選擇重復(fù)覆蓋被遍歷過的單元格的概率將會大大降低。

表1 兩種算法區(qū)域覆蓋效果對比

4.2.2 仿真實(shí)驗(yàn)結(jié)果及分析

AISRA與黃蜂群算法最終的區(qū)域覆蓋效果對比數(shù)據(jù)如表1所示，該數(shù)據(jù)為10次仿真數(shù)據(jù)的平均值。

由表1數(shù)據(jù)可知，AISRA最終的覆蓋率顯著高于黃蜂群算法得到的覆蓋率，但是AISRA最終的平均覆蓋次數(shù)同樣高于黃蜂群算法得到的平均覆蓋率；直觀上看，AISRA平均覆蓋次數(shù)指標(biāo)比較大，這是由于AISRA的總覆蓋率指標(biāo)比較大，所走過的路徑長度肯定比黃蜂群算法總覆蓋長度要長，并且AISRA的總覆蓋率指標(biāo)值不是在黃蜂群算法總覆蓋指標(biāo)值的基礎(chǔ)上成倍增加，而是在其基礎(chǔ)上增加一定的幅度，可以理解為相對于黃蜂群算法提高的覆蓋率而增加的路徑長度。

5 討論分析

在AISRA中，主要從群機(jī)器人之間的協(xié)作、群機(jī)器人的均勻分布兩個方面設(shè)計了控制策略：

1)當(dāng)某區(qū)域存在著多個機(jī)器時，如果周圍機(jī)器人向某個機(jī)器人靠攏，會使機(jī)器人之間的距離減小。在激發(fā)抑制作用的調(diào)控下，使機(jī)器人自身的閾值增加，機(jī)器人會以更大的概率停留在原地。機(jī)器人之間的這種協(xié)作關(guān)系能夠使機(jī)器人周圍存在其他個體時盡可能減少不必要的探索，因?yàn)槿绻麢C(jī)器人周圍存在其他機(jī)器人的時候，該區(qū)域的周圍很可能已經(jīng)或者將要被其他機(jī)器人探索；與固定閾值相比，若機(jī)器人較為集中，機(jī)器人之間的緊密協(xié)作使機(jī)器人停留在原地的概率更大，不僅能減少機(jī)器人重復(fù)覆蓋的可能性，還減小了碰撞的可能性。

2)在響應(yīng)閾值模型中如果某個區(qū)域已經(jīng)較為擁擠，導(dǎo)致機(jī)器人分布不合理，該區(qū)域中的機(jī)器人仍然會在該區(qū)域繼續(xù)探索，當(dāng)該區(qū)域被基本探索完畢之后，可能導(dǎo)致如下情況的發(fā)生：(1)機(jī)器人將會以更大的概率停留在原地；(2)某些機(jī)器人可能處于該區(qū)域較為中心的位置，可能被處于該區(qū)域邊緣的機(jī)器人所包圍(這里的包圍指邊緣處的機(jī)器人已將單元格探索過，中心的機(jī)器人四周都是被探索過的區(qū)域，將會以更大的概率停留下來)，導(dǎo)致機(jī)器人資源的浪費(fèi)。例如在圖15中，初始時刻有較多的機(jī)器人處于該區(qū)域，隨著區(qū)域覆蓋過程的進(jìn)行，處于該局部區(qū)域中心的機(jī)器人最終不能逃出“包圍圈”，當(dāng)這個局部區(qū)域被基本探索完成之后中心的機(jī)器人基本停留在原地；(3)機(jī)器人可能都朝局部區(qū)域的中心位置移動，導(dǎo)致與局部區(qū)域相鄰的區(qū)域沒有機(jī)器人探索，如圖16中局部區(qū)域圖所示。

圖15 機(jī)器人初始分布

圖16 探索過程中某一時刻地圖

當(dāng)加入機(jī)器人分布調(diào)整策略之后，若某個區(qū)域的機(jī)器人分布較為密集，機(jī)器人將會退出這個較為擁擠的區(qū)域，轉(zhuǎn)到其他區(qū)域進(jìn)行探索，使機(jī)器人得到合理分布。因此，加入機(jī)器人分布調(diào)整策略后，地圖的覆蓋率能夠得到有效提升，降低處于中心位置機(jī)器人被“圍困”的概率。

6 結(jié)論

在群機(jī)器人區(qū)域覆蓋問題中，涉及到較多數(shù)量的機(jī)器人，實(shí)現(xiàn)高效區(qū)域覆蓋的重點(diǎn)在于對個體機(jī)器人的有效控制以及群機(jī)器人團(tuán)隊之間的協(xié)作。本文針對群機(jī)器人區(qū)域覆蓋問題，提出激發(fā)抑制與刺激響應(yīng)相結(jié)合的AISRA算法，并通過多個仿真案例對算法的有效性加以驗(yàn)證。本文研究結(jié)論如下：

1)激發(fā)抑制模型、刺激響應(yīng)模型關(guān)注的是個體與個體、個體與環(huán)境之間的交互，AISRA結(jié)合這兩者的特點(diǎn)，群機(jī)器人在覆蓋過程中能夠同時兼顧個體與個體、個體與環(huán)境之間的交互，使群機(jī)器人在區(qū)域覆蓋過程中能夠感知到各種有效信息，在覆蓋過程中給出更加有效的控制策略，實(shí)現(xiàn)高效率區(qū)域覆蓋。

2)AISRA能夠充分發(fā)揮群體協(xié)作的優(yōu)勢，群機(jī)器人區(qū)域覆蓋問題中執(zhí)行任務(wù)的主體是群機(jī)器人，在區(qū)域覆蓋過程中需要對機(jī)器人群體加以有效的控制，利用AISRA求解該問題能夠使機(jī)器人群體發(fā)揮出群體所帶來的優(yōu)勢。

3)通過分析AISRA和群機(jī)器人系統(tǒng)的特點(diǎn)，給出了AISRA與群機(jī)器人之間的映射關(guān)系。

4)激發(fā)抑制的協(xié)調(diào)作用能使機(jī)器人個體與個體之間進(jìn)行交互、信息共享，實(shí)現(xiàn)機(jī)器人個體間的緊密協(xié)作；分布調(diào)整策略能從整體上對機(jī)器人的分布加以調(diào)整，如果機(jī)器人檢測到某區(qū)域存在數(shù)量過多的機(jī)器人，會促使機(jī)器人分散開來。

5)在仿真實(shí)驗(yàn)中，群機(jī)器人在AISRA的控制作用下能夠?qū)崿F(xiàn)個體之間的協(xié)作、調(diào)整群機(jī)器人的分布，從而有效提高區(qū)域覆蓋率，降低重復(fù)覆蓋次數(shù)，表明AISRA能夠有效提高群機(jī)器人的區(qū)域覆蓋效率。

今后的研究將從以下兩方面展開：1)進(jìn)一步對AISRA算法機(jī)理進(jìn)行進(jìn)一步研究，深入分析探討AISRA所具備的特性，將該算法應(yīng)用于群機(jī)器人系統(tǒng)的其他領(lǐng)域；2)進(jìn)一步研究如何利用AISRA減少群機(jī)器人區(qū)域覆蓋過程中的能耗。