虛擬信息素在群體機器人目標搜索中的應用

鄭超學，雷 斌，韓 曉

（1.武漢科技大學機械自動化學院，湖北 武漢 430081；2.武漢科技大學機器人與智能系統(tǒng)研究院，湖北 武漢 430081）

1 引言

目標搜索和路徑規(guī)劃是指在已知或未知的環(huán)境中，移動機器人能自主地搜尋到目標位置，并找到從起點到終點的最短路徑。在空間探測、惡劣環(huán)境搜救等場景中，使用單個移動機器人作業(yè)不僅存在工作效率有限、續(xù)航能力差等問題，還存在依賴單個機器人的性能、系統(tǒng)抗干擾能力差的問題。

相比于功能強大的復雜單機器人，群體機器人具有冗余性、同構性、簡單性以及分布式的特點[1]，硬件復雜度較低，設計相對簡單，消除了單點故障，提升了系統(tǒng)的魯棒性和靈活性，但同時增加了算法設計的復雜度。在目標搜索與路徑規(guī)劃領域，蟻群覓食行為給了相關研究者很好的啟發(fā)。在仿生蟻群覓食行[2]的相關研究中，如何模擬蟻群信息素是一個難點，目前主要解決方案有氣味或FRID 標簽[3]等外部痕跡法、機器人通信渠道法[4]、布置的傳感器網(wǎng)絡法[5]、可展開的信標或機器人鏈[6]。文獻[7]中將MSAPF算法與SRPSO 算法結合，通過仿真驗證了算法在目標搜索與路徑規(guī)劃中的有效性。文獻[8]通過采用最近鄰搜索策略，結合兩組螞蟻相互協(xié)作的方式，提高了最優(yōu)路徑的搜索效率。文獻[9]使用群體機器人分布式搜索算法結合FRID 標簽在實現(xiàn)在未知環(huán)境中搜索目標物。文獻[10]提出一種適用于移動機器人自組織網(wǎng)絡的蟻群算法路由協(xié)議。文獻[11]中對比了CPFA 和DDSA 兩種蟻群機器人覓食算法在任務空間分布、有無障礙物和食物回報率三個方面的性能。此外，改進蟻群算法[12]在路徑規(guī)劃領域已有許多研究成果。

上述應用群體機器人在目標搜索和路徑規(guī)劃的算法中，相關研究大多處于理論推導和軟件仿真階段。在實際應用中，由于信息素痕跡難以實施和檢測，通信通道會產(chǎn)生嚴重的自干擾，布置傳感器網(wǎng)絡具有很大的局限性，可展開的信標和機器人鏈當前實施難度很大。當前的主要問題是，如何模擬螞蟻釋放的信息素，給一群小型的簡單機器人編程，使它們具備基本的運行功能和交互功能，進而可以用小型可編程的群體機器人作為實驗載體，驗證相關理論和算法的實用性與可靠性。

為解決此問題，在借鑒自然界中蟻群覓食的行為后，提出一種基于虛擬信息素的仿生蟻群目標搜索方案。首先，基于虛擬信息素，開發(fā)一種雙向交互的紅外線編碼虛擬信息素系統(tǒng)，通過仿真和實驗測試了虛擬信息素系統(tǒng)的可靠性；其次，設計制作出一種結構簡單的雙驅動輪式群體機器人來搭載上述虛擬信息素系統(tǒng)；最后，使用該群體機器人完成目標搜索和路徑規(guī)劃實驗。實驗結果表明，虛擬信息素系統(tǒng)能夠模擬自然界的化學信息素，使仿生群體機器人經(jīng)過協(xié)作搜索到目標物，群體機器人經(jīng)過一定時間的運動之后，能夠構建出一條從出發(fā)點到目標物的近似最短路徑。

2 虛擬信息素系統(tǒng)開發(fā)

這里提出了一種用虛擬信息素系統(tǒng)來模擬自然界化學物質信息素的方案，虛擬信息素系統(tǒng)，如圖1所示。

圖1 虛擬信息素系統(tǒng)通訊示意圖Fig.1 Communication Diagram of Virtual Pheromone System

該虛擬信息素系統(tǒng)由多個信標中繼器、CAN模塊和紅外收發(fā)裝置組成，各信標中繼器能夠獨立模擬螞蟻沉積的信息素，并將信息素傳遞給其他經(jīng)過的螞蟻，CAN模塊用于采集所有信標中繼器的數(shù)據(jù)，紅外收發(fā)裝置用于傳遞信息素。各信標中繼器之間不能進行通信，將所有信標中繼器的數(shù)據(jù)收集至PC端后，即可觀察整個信息素系統(tǒng)的工作情況。

2.1 虛擬信息素

虛擬信息素是指機器人之間進行信息交互的一種介質，其本質是一種特定編碼的紅外線收發(fā)系統(tǒng)，實驗過程中機器人通過該系統(tǒng)進行信息交互。與化學信息素不同，虛擬信息素將機器人轉化為嵌入在環(huán)境中的分布式計算網(wǎng)格。該網(wǎng)格可以用來計算關于環(huán)境的非局部信息，例如最短路徑和阻塞點，這些非局部信息對于每個機器人來說，在不同位置，不同時刻，從環(huán)境中獲取的信息都是不一樣的。將這種仿生技術應用于群體機器人中，并通過實驗驗證該技術可行性，進而可擴展到大型、異構的群體機器人。

2.2 目標搜索算法

模擬蟻群的覓食行為，設計了一種仿生群體智能搜索算法。螞蟻在覓食過程中能夠感知周圍環(huán)境中的信息素濃度，并向信息素濃度高的方向移動，運動過程中螞蟻只能沿正前方180°范圍內的方向移動，并加強所經(jīng)過路徑上的信息素濃度，因此較多的螞蟻會以更大概率選擇信息素濃度高的路徑運動，通過多次往返巢穴和食物，蟻群最終獲得最短路徑。

為使螞蟻找到食物后能順利返回巢穴，此處定義兩種信息素，一種為從巢穴出發(fā)后釋放的巢穴信息素，簡稱為H信息素，用于引導巢穴位置；另一種為找到食物后釋放的食物信息素，以下簡稱為F信息素，用于引導食物位置。

為描述算法過程并簡化模型，建立離散時間模型，各信標中繼器可看做環(huán)境中的每一個信息素節(jié)點。設螞蟻i在t時刻在環(huán)境中釋放的信息素濃度τi(t) ∈(0，100)，螞蟻在遠離巢穴的過程中，釋放H信息素的濃度也會減小。

設螞蟻每一步運動的距離相等，螞蟻移動速度為v，設螞蟻i運動步數(shù)為Si，螞蟻每移動一步其釋放信息素濃度減小σ，信息素節(jié)點j在t時刻的信息素濃度為τj(t)，每間隔時間T就有一只螞蟻從巢穴出發(fā)尋找食物，螞蟻更新信息素的頻率為f，環(huán)境中信息素揮發(fā)的速度為λ，E1表示螞蟻的集合，E2表示信息素節(jié)點的集合，集合E1*表示信息素節(jié)點下一時刻可以選擇傳遞信息素的螞蟻集合，E2*表示螞蟻下一時刻可以選擇獲取信息素濃度的節(jié)點的集合，則有E1*?E1，E2*?E2。螞蟻的信息素更新方式為：

節(jié)點的信息素更新方式為：

螞蟻在t時刻選擇的下一步要前往的目標節(jié)點為：

在初始狀態(tài)下，當?shù)谝恢晃浵亸某惭ǔ霭l(fā)尋找食物時，τ1(0)=100，τj(0)=0，j∈E。

τj(t+1)=0 時螞蟻隨機選擇下一步的方向移動，在式（2）中，若{(τj(t) -λ/f)，τj(t)}，i∈E1*，j∈E2*中出現(xiàn)相等且最大元素，此時螞蟻隨機選擇其中一個最大元素對應的節(jié)點方向移動。

仿生蟻群覓食的程序流程，如圖2所示。螞蟻在未知的環(huán)境中尋找食物，最初環(huán)境中沒有任何信息素，第一只螞蟻離開巢穴后隨機游走尋找食物，并在游走過程中釋放H信息素，隨著螞蟻遠離巢穴，其釋放的H信息素濃度也隨之降低，環(huán)境中的節(jié)點能夠記錄信息素，經(jīng)過的時間越長，節(jié)點記錄的信息素濃度越低。經(jīng)過時間T后，第二只螞蟻離開巢穴尋找食物，首先螞蟻搜索F信息素，然后再搜索H信息素，由于此時環(huán)境中沒有F信息素，螞蟻會朝著H信息素濃度較高的地方運動，同時第二只螞蟻也會在環(huán)境中釋放H信息素，第二只螞蟻釋放的H信息素會加強環(huán)境中被經(jīng)過的節(jié)點信息素濃度。那么，對于距離越短的路徑，經(jīng)過的螞蟻就會更多，信息素濃度也會高于其他路徑，被其他螞蟻選中的概率也越大，通過這種正反饋作用，蟻群在迭代中逐漸獲得最短路徑。

圖2 覓食程序流程圖Fig.2 Flow Chart of Foraging Procedure

3 仿生群體機器人實驗平臺設計

為了驗證基于虛擬信息素的目標搜索算法的正確性和實用性，設計了一套實驗平臺，該實驗平臺主要由控制模塊、虛擬信息素傳遞模塊、數(shù)據(jù)收集模塊和運動模塊四個部分組成。

3.1 控制模塊

控制模塊采用的是100引腳的STM32F103VET6芯片，該芯片具有32 位Cortex-M3 內核，512K Flash，64K SRAM，并且該芯片還支持豐富的通訊方式，包括兩個SPI，兩個I2C，五個USART，一個USB，一個CAN，充分滿足本設計中對于機器人通信的需求，并且還有利于制作調試和功能擴展。

3.2 虛擬信息素傳遞模塊

機器人采用一種具備方向識別功能的紅外收發(fā)模塊來傳遞信息素，機器人和信標中繼器都具備紅外收發(fā)的功能，各接收和發(fā)射模塊相互獨立。機器人搭載均布八個紅外接收管的紅外接收裝置，如圖3（a）所示。機器人選擇信息素濃度最大的方向運動。機器人底部搭載一個紅外發(fā)射管，紅外發(fā)射管在運動路徑上釋放信息素。這種虛擬信息素方案既能模擬自然界的信息素狀況，又便于實施。

信標中繼器采用一種雙層圓錐結構的外殼，如圖3（b）所示，內側安裝紅外接收裝置，接收機器人發(fā)射的虛擬信息素，外側安裝2個紅外發(fā)射裝置發(fā)射虛擬信息素，圓錐結構限制了虛擬信息素的收發(fā)范圍，使機器人只能在以信標中繼器中心為圓心、半徑為310mm的范圍內與信標中繼器進行信息交互。

圖3 信息素傳遞模塊Fig.3 Pheromone Transfer Module

3.3 數(shù)據(jù)收集模塊

每個中繼器上串聯(lián)CAN模塊觀測信息素系統(tǒng)的運行狀況。CAN通訊協(xié)議可以掛載多個通訊節(jié)點，節(jié)點上的信號經(jīng)過總線傳輸?shù)絇C端，可以通過中繼器增強負載，因此使用CAN 模塊收集虛擬信息素系統(tǒng)的數(shù)據(jù)滿足設計要求。

3.4 運動模塊

運動模塊使用全鋼精密微型齒輪的GA12-N20 減速馬達，該減速馬達使用銅質減速箱，尾部自帶消火電容提高運動靈敏度。電機驅動采用L298N電機驅動芯片控制機器人減速馬達，具備高壓、大電流雙全橋驅動，滿足小型化、大電流的設計要求，運動模塊其他部件通過3D打印制作?；谏鲜瞿K化設計的機器人外形呈圓柱形，直徑約80mm，高度約70mm，如圖4所示。

圖4 機器人示意圖Fig.4 Robot Schematic

4 仿生覓食與路徑規(guī)劃實驗

實驗環(huán)境由一塊（1200×1200）mm 的鋼化玻璃和16 個均勻分布的信標中繼器組成，信標中繼器粘貼在玻璃下表面，機器人在玻璃上表面運動。實驗環(huán)境還包括群體機器人起點和目標物，假設機器人起點為蟻群的巢穴，目標物為需要搜索的食物。群體機器人的任務就是像螞蟻尋找食物一樣搜索目標，某個機器人在發(fā)現(xiàn)目標后，將目標位置通過虛擬信息素傳遞給其他機器人，如果經(jīng)過一定時間后，從起點出發(fā)的機器人沿起點到目標之間的固定路線運動，那么群體機器人就完成了仿生蟻群的目標搜索與路徑規(guī)劃任務。

4.1 測試參數(shù)與指標

4.1.1 測試參數(shù)

完成實驗環(huán)境構建后，此處確定幾個相關測試參數(shù)。

（1）機器人密度：機器人的數(shù)量除以實驗區(qū)域面積，得出機器人平均密度，在實驗中使用3個機器人，因此機器人的平均密度為2.083個/m2；

（2）起點與目標之間距離：將起點與目標之間的距離無量綱化，定義距離等于起點與目標之間的長度距離除以測試區(qū)域平均邊界距離。起點與目標分別位于正方形測試環(huán)境的對角點，因此起點與目標之間的距離為141.4%；

（3）運行時間：將機器人的運行時間無量綱化，定義運行時間等于機器人運動的步數(shù)。通過硬件編程設置機器人每一步都以相同速度運動一個自身尺寸的長度距離，在MATLAB仿真中，一個機器人穿越起點到目標之間25次后，可以遍歷整個地圖環(huán)境，機器人的直徑為80mm，因此，機器人遍歷整個地圖環(huán)境需要530步；

（4）機器人通信半徑：將機器人通信半徑無量綱化，定義通信半徑=虛擬信息素發(fā)射范圍半徑/機器人半徑。在硬件設計中，群體機器人與信標中繼器之間的通信半徑直接影響機器人的搜索效率，在（1200×1200）mm的環(huán)境中均勻布置了16個信標中繼器，信標中繼器之間距離為300mm，為了使每個機器人在搜索過程中至少能同2個信標中繼器進行虛擬信息素交互，在硬件編程中設置機器人通信半徑為7.5。

4.1.2 測試指標

為了衡量基于虛擬信息素的目標搜索算法的性能，下面將使用兩個測試指標：

（1）搜索到目標物的機器人數(shù)量：在經(jīng)過530 步運行之后，整個群體中搜索到目標物機器人的數(shù)量及所占比例，即搜索成功率；

（2）虛擬信息素系統(tǒng)運行狀況：虛擬信息素系統(tǒng)的運行狀況反映了機器人構建路徑的結果，通過上位機在PC端查看每個中繼器的運行狀況，即可得出整個群體機器人構建路徑的可靠性和效率。

4.2 實驗結果

在1200mm*1200mm 的測試環(huán)境中，使用三個機器人搜索目標，起點位于左下角，目標位于右上角，環(huán)境中無障礙物。在機器人找到目標或越過環(huán)境邊界后，就將機器人放置在起點重新啟動，每個機器人的總運動時間為530步長。

機器人運行的“步數(shù)-距離”關系，如圖5所示。實驗過程中機器人1重啟了5次，機器人2和機器人3重啟了3次。機器人1在搜索過程中的隨機性最大，越過實驗邊界4次，并且搜索范圍相對較小，這是由于在前期環(huán)境中沒有任何信息素的情況下，搜索隨機性很大，導致機器人在某個信標周圍來回運動或越過邊界，當環(huán)境中已經(jīng)存在信息素后，機器人的搜索范圍會進一步擴大，搜索速度加快。從圖5可看出，在經(jīng)過530步運行之后，機器人共出動11次，共有5次搜索到了目標，即有45%的機器人能夠搜索到目標，并且，越到后期搜索的成功率越高。而在隨機游走的實驗中，出動相等數(shù)量的機器人只有1次能夠搜索到目標，顯然基于虛擬信息素的仿生覓食方案性能遠遠優(yōu)于隨機游走。

圖5 機器人運行的“步數(shù)-距離”關系圖Fig.5 “Step-Distance”Diagram of Robot Operation

群體機器人在10步、100步、300步和500步時的運行狀態(tài)如圖6所示。在搜索過程中，前期會存在一些隨機性，機器人會以類似漫游的狀態(tài)在環(huán)境中搜索目標，但是隨著虛擬信息素系統(tǒng)迭代次數(shù)增加，在后期的搜索中機器人會表現(xiàn)出很強的目標性，機器人不會再運動到距離目標很遠的位置了。經(jīng)歷530步之后，虛擬信息素系統(tǒng)工作狀況，如表1所示。起點位于第一行第一列，目標位于第四行第四列，從系統(tǒng)運行狀況來看，從左下角到右上角信息素呈現(xiàn)明顯的遞減趨勢，而左上角和右下角幾乎沒有檢測到相關信息素，這說明整個虛擬信息素系統(tǒng)經(jīng)過迭代后，機器人的運行路徑趨于穩(wěn)定，最短路徑的收斂狀況良好。

表1 虛擬信息素系統(tǒng)運行狀況Tab.1 Virtual Pheromone System Operation

圖6 實驗結果Fig.6 Experimental Results

通過觀察群體機器人最后的運行狀況，以及表1所示的虛擬信息素系統(tǒng)，得出群體機器人系統(tǒng)構建的最短路徑，如圖7所示。經(jīng)測量其長度為1382mm。而本實驗中的最短路徑即為從起點到終點的一條直線，其長度為1280mm，機器人從起點到目標的信息素濃度與圖示的最短路徑基本吻合，其長度差距在7.9%以內。經(jīng)過530步運動之后，機器人所構建的最優(yōu)路徑與實際最短路徑仍然存在差距，分析可知，這是由于實驗中的機器人依賴信標中繼器去獲得路徑，但是機器人在多個信標引導下依然存在犯錯的概率，而且，由于最短路徑是一條直線，而實驗所得路徑必然是由多段線組成，因此實驗所得路徑只會逼近最短路徑。

圖7 群體機器人構建的最短路徑Fig.7 The Shortest Path for Swarm Robot Construction

5 結語

基于蟻群覓食行為，提出了一種基于虛擬信息素的仿生蟻群目標搜索與路徑規(guī)劃方案，并將虛擬信息素應用于小型機器人之間通信交互。實驗表明，虛擬信息素方案能夠很好地模擬自然界中的蟻群信息素，為機器人提供通信渠道。然后，設計了一套獨特的硬件系統(tǒng)，通過實驗驗證了這種仿生虛擬信息素的可行性。整個系統(tǒng)的的運行狀況和最終結果證明了虛擬信息素在解決目標搜索與路徑規(guī)劃問題中的實用性與可行性。