基于響應閾值的群機器人地圖創(chuàng)建探索策略

閻 靜，曾建潮，張國有

(太原科技大學計算機科學與技術學院，復雜系統(tǒng)與計算智能實驗室，太原030024)

隨著群智能研究的發(fā)展，群機器人系統(tǒng)受到了越來越多研究者的關注，這主要是由于群機器人系統(tǒng)除了具有多機器人系統(tǒng)的并行性、魯棒性和柔性等優(yōu)點外[1]，還有其自身特有的優(yōu)點，如機器人結構的簡單性、個體數量的伸縮性和同構性等。迄今為止，群機器人研究已積累了若干基準任務[2]，如:隊形分布[3]、搬運、圍捕、搜索和地圖創(chuàng)建等問題。在這些任務當中，地圖創(chuàng)建特別引人關注，它是移動機器人導航和智能機器人真正實現自主的最重要條件之一[4]。現實生活中當地震、礦難等突發(fā)性事件發(fā)生時，需要快速獲得災難現場的準確環(huán)境信息，為救援工作贏得時間，這時群機器人地圖創(chuàng)建就能發(fā)揮作用。機器人地圖創(chuàng)建中有很多問題需要解決，如:測量誤差的減少、問題規(guī)模的估計、地圖創(chuàng)建的一致性問題、環(huán)境中動態(tài)事物的處理和地圖創(chuàng)建過程中的探索策略等[5]。本文基于黃蜂群的響應閾值模型設計了一個群機器人地圖創(chuàng)建的探索策略。

1 算法的生物學背景

群機器人研究起源于生物學的啟發(fā)，通過對社會性昆蟲如螞蟻、白蟻和黃蜂等觀察，人們發(fā)現這些社會性昆蟲雖然個體都很簡單，但通過個體之間的協(xié)作，整個群體可以完成復雜的任務，并且當它們面對多項需要完成的任務時，會自動調節(jié)資源分配和參與這些任務的個體數量[6]，這一現象被Bonabeau等人用黃蜂群響應閾值模型來解釋，描述為公式(1)。在公式(1)中S是與某一任務相關的刺激強度，響應閾值θ是一個內部變量，對S做出響應，可以通過公式(1)計算出任務被執(zhí)行的概率[7]。

本文基于響應閾值模型提出的探索策略很好的滿足了群機器人系統(tǒng)的要求。群機器人系統(tǒng)具有以下特征:(1)該系統(tǒng)應該包括大量的個體[8];(2)系統(tǒng)沒有中央協(xié)調機制，群中的機器人具有同構性[9];(3)群體中的機器人能力有限;(4)個體機器人具有有限的感知能力和通訊能力[10]。基于上述特征，算法的設計必須滿足群體規(guī)模的伸縮性、個體的自治性和個體功能的簡單性等要求。如果機器人攜帶各種傳感器，如激光雷達、聲納和攝像頭等設備將搜集到的相鄰路徑信息作為任務的刺激強度，并根據機器人自身的響應閾值就可決定對任務的參與傾向，提高地圖創(chuàng)建的效率，同時也可滿足群機器人系統(tǒng)的特征要求。

2 算法響應函數及前提假設

根據黃蜂群的響應閾值模型所提出的算法響應函數如下:

公式(2)中Sj是頂點j的任務量度相當于任務的刺激強度，θi是機器人i的響應閾值，αi是調節(jié)因子(0＜α＜1)，Sj的具體公式表示如下:

公式(3)中Uk表示頂點j的未訪問路徑數量，Ck表示頂點j的已訪問路徑數量，β表示調節(jié)因子(0＜β＜1)。由公式(2)可以看出，當機器人所在頂點的相鄰頂點如果包含的未訪問路徑數量較多時，該頂點Sj值就大，機器人訪問該頂點的概率就大;如果相鄰頂點的未訪問路徑較少，該頂點Sj值就小，相應機器人訪問該頂點的概率就小。這樣機器人會以較大概率訪問含未訪問路徑較多的相鄰頂點，從而提高了地圖創(chuàng)建的效率。

本文算法實現對機器人的功能要求如下:(1)有限感知能力:感知判斷環(huán)境中的頂點和邊;(2)環(huán)境頂點和邊的標識能力:機器人能對工作環(huán)境中的頂點或邊進行特征信息的提取和保存;(3)標識的識別能力:機器人能夠對所處環(huán)境的特征信息與機器人的內部表示進行匹配;(4)全局通信能力:機器人能夠進行廣播通信，同時這種直接通信是異步進行的[11]，但這種通信并不用來對機器人間的行為進行協(xié)調;(5)較準確的測距能力。

機器人需要維護的信息包括:(1)所創(chuàng)建的地圖Mat=(V，L);(2)頂點權值信息數組Value[]:保存相臨頂點由公式(2)計算出的權值;(3)探測邊集合E:機器人首先將探測到的頂點邊進行臨時標識后，存放在集合E中，這里稱為臨時邊。

3 探索策略算法描述

3.1 機器人狀態(tài)

機器人的運動是一個可離散化的連續(xù)過程，根據機器人狀態(tài)的變化可分成若干關鍵點，將所有狀態(tài)連續(xù)起來便形成一個過程[12]。本文構造了一個有限狀態(tài)自動機來對單機器人的狀態(tài)進行描述，有限狀態(tài)自動機(finite automaton，FA)M是一個五元組:M=(Q，∑，δ，q0，F)。

有限狀態(tài)自動機模型中各變量的具體實現如下:(1)狀態(tài)的有窮集合Q={WaitState，Recognition-State，MarkState，MoveState，MapAdditionState，Search-State，SelectState}。集合Q由七種狀態(tài)構成，分別是:等待狀態(tài)(WaitState)、識別狀態(tài)(RecognitionState)、標識狀態(tài)(MarkState)、地圖信息添加狀態(tài)(MapAdditionState)、搜索狀態(tài)(SearchState)、選點狀態(tài)(Select-State)和移動狀態(tài)(MoveState)。(2)可接受的輸入集合∑ ={RecognizeVisited，RecognizeNoAccess，FindT-empEdge，FindNothing，Markdid，MapUpdate，JudgeEqual，JudgeNoEqual，MoveNewVertex，SlectNewVertex}。集合∑包含了機器人在地圖創(chuàng)建過程中遇到的物理事件，包括:①RecognizeVisited:頂點已被訪問;②RecognizeNoAccess:頂點未被訪問;③FindTempEdge:有臨時邊被找到;④FindNothing:臨時邊未被找到;⑤Markdid:頂點和邊都被做了標記;⑥MapUpdate:地圖更新完畢;⑦JudgeEqual:集合E和集合L相等;⑧JudgeNoEqual:集合E和集合L不相等;⑨MoveNewVertex:新頂點被訪問;⑩SlectNewVertex:新的訪問頂點被選出。(3)轉移函數δ是Q×∑→Q的一個映射，被有限狀態(tài)自動機識別。(4)起始狀態(tài)q0={RecognitionState}。(5)結束狀態(tài)F={Wait-State}。具體狀態(tài)轉換圖見圖1。

圖1 機器人有限狀態(tài)自動機狀態(tài)轉換圖Fig.1 The finite state automata state transition figure of robot

3.2 探索策略描述

結合圖1對本文探索策略描述如下:機器人首先進入識別狀態(tài)判斷該節(jié)點是否被訪問，如已被訪問就進入地圖信息添加狀態(tài)，否則進入節(jié)點標識狀態(tài);在地圖信息添加狀態(tài)，機器人將節(jié)點信息和來時邊的信息(包括路徑長度)一起添加到所創(chuàng)建地圖Mat=(V，L)中，加入L中的是按節(jié)點標識命名的正式邊，同時修改E中的臨時邊改成正式邊，完成后通知其它機器人進行地圖信息更新;而機器人在節(jié)點標識狀態(tài)會對節(jié)點和邊進行標識，并將邊進行臨時標識后加入E中，完成后機器人進入地圖信息添加狀態(tài)，將頂點信息和來時邊的信息(包括路徑長度)一起添加到地圖中，通知其它機器人進行信息更新，地圖更新完畢后，機器人進入未訪問邊搜索狀態(tài)，在此狀態(tài)機器人將搜索一條臨時邊作為下一訪問路徑，此時機器人會面臨三種情況:(1)機器人找到了一條臨時邊:機器人會進入移動狀態(tài);(2)機器人未找到臨時邊，但此時集合E不等于集合L:機器人會進入選點狀態(tài)，機器人通過響應函數計算出相鄰邊的響應值，按響應值依概率選擇下一條訪問路徑;(3)機器人未找到臨時邊，且集合E和集合L相等:機器人認為地圖創(chuàng)建完成進入等待狀態(tài)。當機器人進入移動狀態(tài)后，機器人會移動到下一訪問頂點進行訪問，此時機器人會重新進入節(jié)點識別狀態(tài)。

4 仿真實驗

4.1 實驗方案

圖2 群機器人地圖創(chuàng)建仿真拓撲地圖Fig.2 The building simulation topology map of swarm robot map

采用JavaSe設計的仿真平臺對提出的算法進行仿真實驗，用多線程模擬群機器人的并行訪問，實驗方案制訂如下，仿真環(huán)境用帶權拓撲地圖描述，見圖2，在該地圖中共包含有20個頂點和39條邊，邊長一共是991個單位距離長度。實驗中分別用2、4、6、8和10個數量的機器人進行實驗，這里假設機器人勻速運動，運動的速度是單位距離/單位時間，實驗對每個數量的機器人都進行20次實驗，最后取平均值，按響應閾值的不同實驗分三組進行，實驗中其他參數設置如下，公式(2)中的α=0.016(0＜α ＜1)，公式(3)中的 β=0.6.

4.2 評價指標

(1)總覆蓋長度:機器人在地圖創(chuàng)建完成后所走過的路徑總長度，包括機器人重復走過的路徑;(2)覆蓋時間:機器人完成地圖全覆蓋所需的時間，這里用總覆蓋長度比機器人數來表示覆蓋時間;(3)覆蓋率:機器人所創(chuàng)建地圖的路徑長度與工作環(huán)境的路徑長度之比，這里所計量的路徑長度不包括重復路徑。

4.3 實驗結果

機器人按照不同響應閾值進行仿真實驗后，將實驗結果平均值列為表1和表2，表中機器人創(chuàng)建地圖的覆蓋率都是100%.

表1 20次實驗總覆蓋長度平均值表Tab.1 Experiment 20 times total coverage length average table

表2 20次實驗總覆蓋時間平均值表Tab.2 Experiment 20 times total coverage time average value table

4.4 實驗結果分析

由表1可以看出當機器人數量較少時，如機器人的數量是2個或4個的時候，表中響應閾值θ=10的總覆蓋長度比θ=0.31的大，卻比θ=0.62的要大，這可以解釋為閾值設置的大小在機器人較少數量的情況下對總覆蓋長度的影響不明顯，而當機器人的數量大于6個的時候，由表1可以看出θ=0.31和θ=0.62的總覆蓋長度明顯少于θ=10的總覆蓋長度，這也可以解釋為當機器人的數量較多時，響應閾值的設置對地圖創(chuàng)建效率的影響較大，且響應閾值設置的較小時效果較好。由表2可知當機器人的響應閾值分別設置為θ=0.31、θ=0.62和θ=10時，隨著機器人數量的增加，機器人地圖創(chuàng)建所用的覆蓋時間也隨之下降，這說明隨著機器人數量的增加，機器人整體的探索距離并沒有增加，這也就是說算法滿足了群機器人系統(tǒng)的伸縮性要求，當機器人地圖創(chuàng)建的覆蓋時間降低時，也就意味著通過增加機器人的數量，提高了群機器人創(chuàng)建地圖的效率。

5 結論

通過實驗結果可以看出，本文算法很好的滿足了群機器人系統(tǒng)的伸縮性，實驗結果表明當響應閾值設置的較小時效果較好，并且機器人的數量越多受響應閾值的影響越大。本文中的仿真實驗是在一個特定的加權拓撲地圖上進行的，下一步研究需要對實驗地圖的規(guī)模和種類進行擴充，另外算法中群機器人的探索效率還會受到很多因素的影響，如任務調節(jié)因子的設置，地圖中頂點和邊的數量等，以及這些參數之間的相互關系，這些都需要進一步的研究。

[1]譚民，范永，徐國華.機器人群體協(xié)作與控制的研究[J].機器人，2001，23(2):179-181.

[2]薛頌東，曾建潮.群機器人研究綜述[J].模式識別與人工智能，2008，21(2):183-185.

[3]諶海燕，曾建潮.基于PSO的多機器人編隊控制[J].太原科技大學學報，2009，30(5):28-31.

[4]蔡自興，賀漢根，陳虹.未知環(huán)境中移動機器人導航控制研究的若干問題[J].控制與決策，2002，17(4):385-390.

[5]THRUN S.Robotic Mapping:A Survey[R].Technical Report CMU-CS-02-111.School of Computer Science Carnegie Mellon U-niversity Pittsburgh，USA，2002，:3-5.

[6]張國有，曾建潮.基于黃蜂群算法的群機器人全區(qū)域覆蓋研究[J].模式識別與人工智能，2011，24(3):433.

[7]BONABEAU ERIC，THERAULAZ GUY，DENEUBOURG JEAN_LOUIS.Fixed Response Thresholds and the Regulation of Division of Labor in Insect Societies[J].Bulletin of Mathematical Biology，1998，60:753-756.

[8]SAHIN E.Swarm Robotics:From Sources of Inspiration to Domains of Application[C]//Proc of the SAB Workshop on Swarm Robotics.Santa Monica，USA，2004:10-20.

[9]BALCH T.Hierarchic Social Entropy:An Information Theoretic Measure of Robot Group Diversity[J].Autonomous Robots，2000，8(3):209-238.

[10]王海.群機器人技術進展[C]//中國自動化學會第二十五屆青年學術年會論文集，沈陽:東北大學出版社，2010:2-4.

[11]李進，薛頌東，曾建潮，等.群機器人目標搜索中的通信模式研究[J].太原科技大學學報，2011，32(4):15-19.

[12]王旭陽，呂恬生，徐兆紅，等.類人機器人復雜運動的狀態(tài)轉換規(guī)劃方法研究[J].中國機械工程，2007，18(6):659-662.