網絡可重構的多機器人仿真系統

摘 要：根據多機器人通信網絡的特點，提出了一種多機器人通信仿真系統， 并通過一個網絡可重構的通信方式給出了該系統的實現。機器人的移動性使之組建的通信網絡可靠性很差，可重構的機器人通信方式可顯著提高網絡的通信質量。當前的多機器人仿真系統有很多，而具有通信仿真功能的較少。該仿真系統采用節點隨機停留運動模型和模塊化設計，可用于仿真多機器人通信網絡。系統還提供了與其他機器人控制算法的接口，可進行其他仿真工作。

關鍵詞：多機器人系統; 網絡可重構; 仿真系統; 簇結構

中圖分類號：TP 24文獻標志碼：A

文章編號：1001-3695(2009)06-2285-03

doi:10.3969/j.issn.1001-3695.2009.06.087

Simulation system for multi-robots based on network reconfigurable

REN Xiao-ping， CAI Zi-xing， LU Wei-wei

(School of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:

According to the characteristic of communication network of mulit-robots， presented a communication simulation system for multi-robots and realized through a network reconfigurable communication technology. The reliability of communication network was poor because of mobile character of robots， reconfigurable communication technology used on robots could remarkably improve communication quality. Nowadays there were many multi-robots simulation systems， but the number of simulation system which could provide simulating communication network was less. Random waypoint module and modularization design technology were adopted in this multi-robots simulation system， which could simulate the robots communication network. Provided interfaces for other control arithmetic， which facilitated the simulation on multi-robots system.

Key words：multi-robots system ; network reconfigurable; simulation system; cluster structure

0 引言

當前多個機器人分布式作業已經成為一個趨勢^[1]，通過多機器人的協作，可以完成單機器人難以完成的復雜作業，提高機器人系統再作業過程中的效率^[2]。它們在協作完成一項任務時，需要相互的信息融合和共享。所以，由各個個體機器人組成的群體系統，通信是必不可少的^[3]。近年來，多機器人系統的理論研究受到各國研究機構的普遍關注，現在國際上已經研究出一些成功的實驗系統，如ACTRESS、CEBOT、SWARM和MRCAS等^[3，4]。

機器人一般較為昂貴，直接在實體上進行控制算法、協助策略和通信測試的實驗投資較大。算法的合理性、有效性可以通過計算機仿真進行初步驗證，然后再通過實際的多機器人系統進行實驗驗證，因此有必要建立多機器人仿真系統用來對相關的算法進行計算機仿真驗證。目前的多機器人仿真系統，著重研究的是覓食、多目標探測、未知環境探測、地圖構建、路徑規劃、機器人足球和群體搬運等問題^[5]，對于多個機器人之間通信網絡的仿真則相對較少^[6]。本文提出的多移動機器人通信網絡仿真系統，側重于反映多個移動機器人之間的通信機制以及拓撲變化情況，并以一個可重構的多機器人通信方式實現了該系統原型。

1 多機器人通信網絡仿真系統

多機器人團隊通常在一個未知區域內執行任務，首先需要探索未知區域。進入該區域后，開始進行漫游行走，相互之間通過通信網絡進行信息的傳遞和共享。根據機器人環境下的通信網絡的需求，通信網絡仿真系統應由以下幾個模塊組成，即機器人行為模型的建立、環境模型繪制、運動仿真控制和通信網絡模塊。如圖1所示，各個模塊相互獨立，其中的虛線框是該系統預留的接口，可以添加其他機器人控制算法以及和實體機器人的通信接口。



可靠性是機器人通信網絡的重要指標之一。機器人由于移動特性或主機死機，它們之間的通信網絡隨時有可能斷開鏈接，錯誤的數據傳遞將會導致機器人作出錯誤的判斷與決策，從而導致整個機器人團隊的失敗；另外機器人管理策略的好壞也決定了整個通信網絡的通信效率。為了提高通信網絡的可靠性，在該系統中添加可重構功能，故通信模塊還包括機器人通信、簇結構的構建等。

1.1 機器人行為模型的建立

機器人行為模型主要包括機器人的分布、運動速率、運動規律以及與其他機器人的相關性，主要用于描述機器人的運動情況。采用合適的行為模型對于分析機器人通信性能和運動規律具有重要意義。

隨機停留運動模型（random waypoint）由Johnson等人提出，最大速率vmax和停頓時間tpause是模型的兩個關鍵參數，使用該模型的網絡鏈路存活時間較長，易于形成穩定的拓撲，是較常用的一種運動模型^[7]。

考慮一個由N個隨機部署的移動機器人節點形成的Ad hoc網絡，用ri表示第i個移動機器人，相應的移動機器人節點集合為R={r1，r2，…，rn}，|R|=N(N＜100)作如下假設：

a）各個移動機器人位于一個方形觀察區域A內;

b）每個節點都具有一個惟一的標志（ID）。

開始時，機器人節點ri在仿真區域內A隨機選擇一個目的地，然后機器人ri選擇以滿足在[0，vmax]內均勻分布的某個速度vi勻速移動。到達目的地后，停留tis（用ti表示機器人移動的劇烈程度；ti=0表示機器人是連續移動的）。機器人ri的移動速率vi和移動方向θi的選擇與機器人rj(i≠j)不相關。停留時間結束后，機器人ri又選擇另一個隨機目的地并向其運動。

在該種模型中，如果vmax小而ti長，則通信網絡的拓撲相對穩定；如果vmax大而ti短，通信網絡的拓撲則有較高動態性。算法流程如圖2所示。

編程實現該運動模型，由于生成的機器人運動信息量較大，故將信息存入仿真文件moving-scen.dat中，以供之后動態過程模擬時讀取，這樣不會影響模擬運行的速度。

1.2 環境模型的繪制

本文設計的多移動機器人通信網絡仿真系統，支持自定義機器人數（系統支持最多100個機器人的仿真）、機器人運動速度、仿真時間長短、機器人最大通信半徑以及機器人的運動范圍。根據已經生成了的機器人運動模型文件，接下來繪制環境模型，包括機器人的繪制和障礙物的繪制。

1）構造機器人模型 在圖形窗口中繪制機器人的形狀，可以調整機器人大小以及視圖的縮放，確定機器人的初始位置，每個機器人都有惟一的標志（ID）。由于機器人在運動過程中會移動出屏幕視野，添加了視圖移動的功能，方便用戶實時觀察節點的運行狀態。

2）障礙物的繪制 本系統可以對環境中的障礙物進行編輯、修改，如增加障礙物、改變其大小等，這樣可以應用到可添加模塊，即機器人避障和路徑規劃等。

1.3 機器人運動仿真

環境模型建立之后，接下來就是機器人動態過程的模擬。由于仿真系統是模擬機器人分布式的運行，每個機器人都是相互獨立的，只有采用多線程技術，才能最大程度地體現出這種特點^[8]。

另外設兩個全局的運動狀態結構存儲各個機器人的運動狀態以及環境信息。如圖3所示，運動仿真模塊主要有兩個線程。其中，drawRobotThread是根據機器人當前的坐標繪制新機器人線程；nodeMoveFunctionThread是不斷改變機器人運動軌跡的線程，包括機器人運動速度vi以及移動方向θi，它將改變了的機器人坐標存入robotState數據結構。由于兩個線程會同時訪問一段相同的數據區域robotState，應加互斥鎖pRobotStateLock。



系統設定了一個步進時間變量simulation_time，用于控制仿真速度；鑒于圖形界面的廣泛使用，采用進度條組件，使用者可以實時了解仿真進度；另外采用了時鐘暫停模式，可以使仿真暫時停止，觀察機器人節點的鏈路狀態。仿真系統的易用性、可視化程度高，為人機交互信息提供了最大的支持。

1.4 機器人通信模塊

通信模塊是系統的核心，在每個機器人需要發送信息時它可以立即發送，若要完成較遠距離的通信，則可以通過中間機器人進行信息轉發；在某個移動機器人脫離通信范圍的情況下，其余機器人應該能夠自適應地重新組成新的網絡，而不影響整個團隊的工作^[9]。按照上述原則，本文提出了一種網絡可重構的通信方式。

1.4.1 多機器人的分級管理

對于該系統，首先作如下說明：

a）由于機器人能量和信號發射功率的限制，每個機器人都有最大通信距離。本系統中均采用同構機器人，機器人參數相同。

b）定義每個機器人有三種狀態，即簇頭、成員和未定狀態。機器人初始化時都是未定狀態。

c）每個機器人如若屬于不同的簇結構，那么該機器人就是網關機器人（圖5中的2號機器人，它可向其他簇結構進行轉發消息）。

d）網絡重構包括簇結構重構和鏈路重構。

在大規模移動機器人組建的通信網絡中，分級管理機器人的策略可以顯著提高通信的效率。每個機器人周期性地廣播自身識別信息，其他機器人收到非自身發送的識別消息后，記錄在本機。通過這些鄰居機器人的信息，構造簇結構。簇頭機器人管理成員機器人，從而形成兩級管理結構。

構建這種簇結構的示意圖如圖4所示。1號機器人可以收到2、3、5號機器人的識別消息，根據最小ID原則，被選舉為簇頭節點，然后四個機器人會組建成一個簇結構。同樣，4、6、7組建成一個簇結構。在該圖中，6同樣也可能隸屬于1號機器人管轄，取決于6號機器人收到1和4號機器人識別信息的先后順序。

1.4.2 信息傳輸

信息傳輸是一個機器人S獲得一個到D的傳輸路線然后傳輸信息到終點D的機制。由于S和D可能相距較遠，需要中間機器人進行信息轉發。

圖5為利用簇機制進行信息傳輸的過程。S將信息發送給簇頭A，簇頭A查找D是否在本簇范圍內，如果在，直接將消息發送給D；否則就通過網關機器人2發送給相鄰簇頭B。B收到2發來的信息，它查找自己的鄰居表，發現終點D在本簇內，直接將信息轉發給D。這樣S的信息發送請求并不用在簇A范圍內向不相關的機器人洪泛廣播，節省了參與傳輸信息的機器人數量。



1.4.3 簇結構重構

簇的構建包括以下幾方面：

a）如果一個未定狀態機器人從一個簇頭收到識別信息，則該機器人會加入此簇頭，并設置自身的狀態為簇成員。

b）如果在規定時間內，機器人成員節點沒收到任何簇頭的消息，則它重新進入未定狀態。等待加入下一個簇結構。

c）如果長時間無簇頭機器人靠近，則自動變為簇頭狀態。

按照上述原則，會帶來簇結構過多的問題，簇結構重構就是為了解決該問題。當兩個簇結構移動到能互相收到對方的識別消息時，局部進行簇頭機器人的選舉，則兩個簇融合成一個簇結構。通過這種機制，可以自適應地調整機器人團隊中的簇結構規模。

1.4.4 鏈路重構

機器人的通信網絡隨時有可能斷開鏈接，當信息傳輸過程中鏈路突然斷開，會嚴重影響信息傳輸的延遲。鏈路的重構就是在鏈路斷開的地方，對鏈路進行局部修復。

舉例說明該機制的工作原理。每個機器人在收到其他機器人發送來的識別消息時，都可以組建本機的一個鄰居機器人信息列表，如表1第二列所示。在第二次廣播識別消息時，將本機的鄰居信息表也發送出去。這樣每個機器人可以獲取鄰居的鄰居信息，如表1第三列所示。

如圖6所示，信息的傳輸路徑3→4段發生了鏈路破損，此時通過表1所示的鏈路重構信息庫來修復破損的鏈路。3發現到4的鏈路不通時，通過查閱自己的鏈路重構信息庫，發現機器人4仍然是本機鄰居的鄰居。進而詢問自己的鄰居，得知2的鄰居就是4，則路線更改為3→2→4。這樣就實現了通信鏈路的重構。

2 仿真系統的實現

該系統用VC++6.0進行了相應的實現，系統的通信模塊采用網絡可重構的通信方式。圖7為該系統的前端界面。

在圖7中，用戶可以自定義仿真機器人數、最小速度和最大速度、仿真時間等數據。定義好這些參數之后，產生隨機運動場景文件，機器人位置分布如圖8所示。由于確定了機器人最大通信距離是4倍機器人半徑，從圖中可以看出，每個機器人可達的最大距離以及相鄰機器人有哪些。



啟動通信網絡之后，即開始進行簇結構的構建。如圖9所示，在初始狀態時的簇結構構造情況。虛線框表示一個簇結構，簇頭機器人和成員機器人節點見圖中標記。選擇開始仿真，機器人節點開始做隨機運動。由于有簇結構的重組，運動過程中簇結構也是不斷變化著的。

機器人節點會移出視圖范圍，可以用視圖調整按鈕移動屏幕視野，并可以調整仿真速度。圖10顯示的是機器人開始仿真時的運行效果。另外對于鏈路重構，是通信網絡隱式的優化機制，在仿真界面上并沒有顯示。



3 結束語

在多移動機器人相互協作完成任務的過程中，機器人所采用的通信方式的優劣是任務完成的保障之一。

本文通過分析現有多機器人仿真平臺對通信網絡的仿真不足，提出了一種通信網絡仿真平臺的系統設計方案，并以網絡可重構的機器人通信方式為例，對該系統進行了相應的實現。隨機停留運動模型、環境模型的建立以及可自定義仿真參數和為其他控制算法預留了接口，使該系統具有良好的人機交互功能。通過進一步編程，用戶可以在仿真系統中嵌入自己的控制算法和分析日志函數，使該仿真平臺可以方便地對通信網絡進行仿真和性能分析。在與實體機器人進行可通信編程之后，也可以實時地演示機器人的運動狀態和通信鏈路變化。

參考文獻：

[1]譚民，王碩，曹志強.多機器人系統[M].北京:清華大學出版社，2005.

[2]劉滿強，周紅莉.基于Internet的多機器人協作通信策略設計[C]//第二十屆中國2006 IT、網絡、信息技術、電子、儀表儀器創新學術會議論文集. 天津:出版者不詳，2006：31-35.

[3]熊舉峰，譚冠政，盤輝.多機器人系統的研究現狀[J].計算機工程與應用，2005，41(30):28-30.

[4]FUKUDA T， UEYAMA T， ARAI F. Communication strategy for network of cellular robotic system(CEBOT)-mastering methods for single and two tops structures[J]. Advanced Robotics， 1991(19-22):527-532.

[5]原魁，李園，房立新.多移動機器人系統研究發展近況[J].自動化學報，2007，33(8):785-791.

[6]李立坤.多機器人協作算法及仿真研究[D].哈爾濱：哈爾濱工業大學，2006.

[7]王建新，李健，朱賢曼.MANET中節點的運動模型和性能分析[J].計算機工程，2006，32(19):125-130.

[8]胡蓉，王碩，曹志強，等.基于COM技術的多移動機器人仿真系統[J].系統仿真學報，2004，16(7):1477-1480.

[9]王鎮興.移動多機器人通信網絡的研究[D].南京：南京理工大學，2006.