基于信標的多Agent系統(tǒng)及其移動規(guī)則研究

楊志娟，楊陽，楊會建

（長春理工大學 電子信息工程學院，長春 130022）

在多Agent系統(tǒng)研究中，研究員試圖發(fā)現(xiàn)或發(fā)明群體行為的控制機制，將這種機制應用于控制大規(guī)模數(shù)量的簡單Agent，使大規(guī)模數(shù)量的簡單Agent能夠像生物界中的群體生物一樣，自組織的表現(xiàn)出群體智能行為，比如蟻群覓食、魚群鳥群的列隊前進、蟑螂聚集選擇棲息地等。群體Agent系統(tǒng)及其表現(xiàn)出的群體智能行為可用于完成現(xiàn)實世界的任務，比如執(zhí)行搜索、探測、救援、運輸、地圖構(gòu)建等。目前群Agent系統(tǒng)以控制方式不同可分為集中式控制和分布式控制兩種形式。

集中式控制是指由一種或多種復雜的Agent控制其他Agent來完成相應的操作。這種單一的系統(tǒng)管理方式存在著大量的缺陷，如低效率、低擴展性、網(wǎng)絡擁塞嚴重、系統(tǒng)核心管理Agent隨著網(wǎng)絡規(guī)模的擴展壓力不斷增加。

相對于集中式控制出現(xiàn)的種種問題，分布式控制系統(tǒng)通過Agent之間的相互作用來實現(xiàn)整體性的正常運行。這些相互作用可通過簡單的規(guī)則來實現(xiàn)，如Agent的近鄰個體信息（例如雷諾的三個規(guī)則“群中心”，“避障”和“速度匹配”）。這樣，系統(tǒng)占用更少的資源，具有更好的魯棒性，從而提高整體的工作性能。

以上兩種方式中的Agent之間都是采用數(shù)字通信的方法來處理協(xié)調(diào)個體行為的問題，在一般情況下是有效的，但對于大系統(tǒng)來說，該方法則會存在一些問題，因為數(shù)字通信可能會出現(xiàn)通信失敗，這些失敗的通信可能會導致系統(tǒng)的惡化。為確保系統(tǒng)能夠正常運行，需要更多的控制和增加硬件機制，這樣就增加了Agent的復雜性，使系統(tǒng)的可靠性也大大降低，且系統(tǒng)的擴展性能變得較差等。

本文提出一種新型的、基于信標的多Agent系統(tǒng)。模塊間僅通過信標檢測的方式來進行信息交互，設計出的新型Agent系統(tǒng)不僅能實現(xiàn)現(xiàn)有系統(tǒng)的功能，且由于模塊間的信息交互方式簡單，硬件電路的復雜度降低，出現(xiàn)故障的概率將減小，系統(tǒng)的可靠性將得到增強，同時也降低了系統(tǒng)的成本。

1 基于信標的多Agent系統(tǒng)

該系統(tǒng)中的Agent之間是通過發(fā)射/接收簡單的無線信標方式進行信息交互的。原理是Agent間通過發(fā)射/接收吸引和排斥兩種類型的信標使系統(tǒng)正常運行。其中吸引信標用于資源分配（吸引Agent去指定的地方，如目標物所在位置），排斥信標用來控制Agent的分布和密度，避免Agent模塊在移動過程中發(fā)生碰撞。由于Agent之間僅通過信標檢測的方式來進行通信，系統(tǒng)的擴展性將得到提高。

1.1 Agent模塊

系統(tǒng)中的Agent擬采用可移動模塊，模塊中主要包含一對無線節(jié)點、控制模塊、傳感器、電機驅(qū)動模塊、電機和電源等。圖1所示為Agent的結(jié)構(gòu)框圖。

每個Agent配備一對無線節(jié)點，分別在可移動模塊的左、右兩側(cè)，且規(guī)定右無線節(jié)點為主節(jié)點，主要用于發(fā)射/接收排斥信標和吸引信標，左無線節(jié)點為從節(jié)點，主要用于接收排斥信標和吸引信標。右無線節(jié)點發(fā)射的信標強度為確定值，在傳輸過程中信標的強度將降低，左、右無線節(jié)點由于距離源點的距離不同，左、右接收到的信標強度有差距。

傳感器用來檢測及發(fā)現(xiàn)目標物，從而確定目標物所在的位置。針對不同的任務，可添加不同的傳感器，如檢測平面區(qū)域內(nèi)的積水區(qū)時，則采用濕度傳感器，在模塊移動過程中，傳感器實時地檢測周圍的環(huán)境并發(fā)現(xiàn)目標物。

電機是選用兩個電機分別控制移動模塊的兩邊車輪，控制器通過產(chǎn)生兩路可調(diào)型的PWM波，通過電機驅(qū)動芯片來控制兩邊電機的轉(zhuǎn)速來實現(xiàn)Agent的轉(zhuǎn)彎以及直行等移動狀態(tài)。

控制器根據(jù)無線節(jié)點接收到的信標類型及左、右信標強度之差作出Agent移動方向的判定來產(chǎn)生兩路PWM波輸出，同時實時處理傳感器輸入的信號，未發(fā)現(xiàn)目標物時，控制右無線節(jié)點只發(fā)射排斥信標，一旦發(fā)現(xiàn)目標物信號，控制器首先使Agent停在該位置，同時使右無線節(jié)點從只發(fā)射排斥信標的狀態(tài)，轉(zhuǎn)為間接性的發(fā)射兩種信標，這樣在保證不發(fā)生碰撞的情況下，所有Agent向檢測出的目標物位置靠攏，來更好地完成所要實現(xiàn)的功能。

1.2 多Agent系統(tǒng)

系統(tǒng)主要是由多個Agent模塊組成，在規(guī)定區(qū)域內(nèi)，各自按照自身的移動路徑移動且配備的傳感器實時檢測周圍環(huán)境發(fā)現(xiàn)目標物，同時以一定的頻率發(fā)射排斥信標來防止與其他Agent發(fā)生碰撞。當其中一個Agent發(fā)現(xiàn)目標物后，將發(fā)射吸引信標來告知其他Agent模塊，其他Agent接收到吸引信標后，將終止自身的移動路徑，不斷地根據(jù)接收到的左、右吸引信標之差值的判定方式向目標物方向移動，最終對目標物進行實行必要的包圍、攔截等任務。發(fā)現(xiàn)目標物的Agent可根據(jù)自身的路徑回溯功能，在任務完成后，使系統(tǒng)的所有Agent都回到出發(fā)位置。

圖1 Agent模塊的結(jié)構(gòu)圖

在研究初期，僅在較小的范圍內(nèi)進行驗證，先采用固定航點信標導航的方式對Agent在固定區(qū)域內(nèi)進行導航。固定航點以序列的形式在區(qū)域內(nèi)均勻排列，發(fā)射信標對Agent進行導航，當Agent靠近固定航點時，下一個序列的航點將發(fā)射導航吸引信標，此時Agent將向下一個航點信標方向移動，以此類推，Agent將按固定航點的導航路徑在區(qū)域內(nèi)移動，并實行目標物的檢測及其相關(guān)任務的完成。

2 Agent移動規(guī)則

由于新型Agent之間是通過信標檢測的方式實現(xiàn)的，但具體的移動規(guī)則還需細化分析。

2.1 Agent的信標

Agent模塊配備的一對無線節(jié)點，分別在模塊的左、右兩側(cè)，根據(jù)模塊兩側(cè)的無線節(jié)點接收到的信標強度和類型不同來實現(xiàn)相應的功能。主要的工作原理是根據(jù)左、右兩個無線節(jié)點源點的距離不同，將兩側(cè)的信標強度作差和求和運算，控制器根據(jù)運算值及信標類型作出判定，Agent模塊以一定的頻率重復上述運算，最終實現(xiàn)與其他Agent處于安全狀態(tài)的情況下，向目標物位置方向靠攏。

Agent的排斥信標只對在一定范圍內(nèi)的Agent有反應，如圖2所示，以ρ為半徑的圓表示Agent的防撞范圍。每個Agent之間要保持ρ距離的足夠空間，才能確保Agent的正常運行。距離ρ與Agent的最小半徑旋轉(zhuǎn)半徑Γ有關(guān)，進一步的可以認為直接與Agent的運動速度有關(guān)。

圖2 Agent間的防碰撞的最小區(qū)域圖

而吸引信標是找到目標物后Agent發(fā)射的一種類型的信標，來引導其他Agent向目標物位置靠攏。

2.2 Agent接收的信標強度算法

定義接收到的信標強度公式為：式中，Iy,i是在位置xi的Agenti接收到的y型的信標強度，包含排斥信標col和tar兩種類型的信標即 y∈{ }

col,tat，Ay是發(fā)射y型信標強度，該系統(tǒng)共有n個Agent，發(fā)射的同類型的所有信標具有相同的強度，該值可設置為常數(shù)，在計算該公式可被視為過程中可做常數(shù)處理。下面是利用兩個橫向天線的方向靈敏性，能得出左、右天線的信號強度，這樣可分別求出到左、右天線的距離：

若Agent將接收到的每個碰撞信標區(qū)分時，則需要在調(diào)制方案中進行必要的處理。假設Agent的排斥信標是可區(qū)分的，上述的算法將會簡化些，但由于是多個Agent模塊同時運行，要分別對接收到的數(shù)據(jù)先進行處理，再對處理后的數(shù)據(jù)運算，這將增加硬件電路的結(jié)構(gòu)，相對而言，復雜度大大提高。同樣的，可參照求排斥信標的總和方法來求吸引信標強度。而不將n個排斥信標進行區(qū)分。在一般情況下，該算法是適用的，但這種簡化方式存在一定的弊端，由于所求的是排斥信標的強度之和，Agent會可能做出錯誤的轉(zhuǎn)彎判定。下面舉例論證，假如有兩個Agent在Agent A的左邊距離100，排斥信標處于打開狀態(tài)，Agent A的排斥范圍為ρ=80。那么根據(jù)接收到的Agent A的天線強度值將（錯誤地）判定Agent在排斥范圍內(nèi)，Agent A將向右轉(zhuǎn)彎，可能會不立即發(fā)生碰撞。這種情況至少在原理上是有可能發(fā)生的，當有大量的Agent在右側(cè)上且不在排斥范圍內(nèi)，左側(cè)的Agent在排斥范圍內(nèi)，但其信標強度低于一側(cè)的信標強度之和，其排斥信標強度的和值使得A向左側(cè)方向上進入Agent的軌跡，其軌跡也在碰撞范圍內(nèi)，原理上這種情況可能會發(fā)生碰撞，但在實際操作中，這種情況是不可能發(fā)生的，其中有兩個原因：第一，因為Agent通常相隔的距離最小為ρ，信標強度下降與距離的平方成正比，距離遠的Agent的影響是可以忽略不計的，只有少量臨近的Agent能夠決定A的判定；第二，Agent不必在所有時間都打開排斥信標，可以以一定的頻率發(fā)送脈沖。那么兩個或多個脈沖在同一時間發(fā)生的概率將會很低，即使他們同時出現(xiàn)，短時間以后將再次出現(xiàn)間隔，則Agent可以做出正確的決定。因此對于信標接收器，要分辨出不同的Agent信標是沒有必要的。

2.3 Agent信號處理算法

具體的轉(zhuǎn)動方向是根據(jù)兩個方向天線接收到的信標強度決定的，天線位于Agent的兩側(cè)，方向與運動方向相反（η，和-η），且與該Agent的速度矢量垂直。由于Agent的轉(zhuǎn)彎半徑與轉(zhuǎn)彎方向（左和右）無關(guān)，通過左、右方向天線的簡單強度比較，來判定是向左轉(zhuǎn)還是向右轉(zhuǎn)。將左、右天線之間的信號強度和與差進行定義：其中 Sy,i和 Dy,i表示Agenti的左、右天線y型信號強度的和與差。其中Sy,i是用來確保在接收到有用信標情況下，做出的判定。且在y=col的類型下，只有Agent在滿足的情況，分別用左、右天線信號的強度Li和Ri求出Dcol,i，進一步的說明只有在滿足上述條件下，Scol,i和Dcol,i才有意義。Agent的導向控制原理如：當 Scol,i＞0且 Dcol,i＞0時，Agent執(zhí)行向右轉(zhuǎn)的命令；當 Scol,i＞0且 Dcol,i≤0時，Agent執(zhí)行向左轉(zhuǎn)的命令；當這兩個條件都不滿足時，則當Star,i＞0且Dtar,i＞0時，Agent執(zhí)行向左轉(zhuǎn)的命令；當Star,i＞0且 Dtar,i≤0時，Agent執(zhí)行向右轉(zhuǎn)的命令；若上述條件都不滿足時，Agent執(zhí)行沿原方向直走的命令。

2.4 Agent移動算法仿真

首先通過仿真來驗證出上述所講的信號處理算法進行了仿真，仿真環(huán)境為MATLAB軟件。方案是：首先隨機產(chǎn)生四組數(shù)據(jù)，每組的數(shù)據(jù)長度為10，分別作為接收到的左側(cè)排斥信號強度，右側(cè)排斥信號強度，左側(cè)吸引信號強度和右側(cè)吸引信號強度。設置的排斥信號強度臨界值為5，當左側(cè)或右側(cè)排斥信號強度大于臨界值時，將計算出左側(cè)排斥信號強度與右側(cè)排斥信號強度和與差值，若小于臨界值時，則計算出左側(cè)吸引信號強度與右側(cè)吸引信號強度和與差值。仿真出的圖形如圖3所示。

圖3 新型Agent對接收到的信號處理算法的仿真驗證

通過圖3的仿真圖可看出當接收到的任一側(cè)的排斥信標強度大于臨界值5時，控制器將會計算出排斥信標的和與差，當兩側(cè)的排斥信標強度都小于5時，控制器將會計算出吸引信標的和與差，再分別根據(jù)計算出的和與差的數(shù)值及信號類型作出相應的判定。

在仿真過程中，選用的計數(shù)次數(shù)為10次，相應的是十次的轉(zhuǎn)彎判定，將對應的判定結(jié)果存放于矩陣action中，每一列為一次仿真判定。每列中第一行為1時，表示Agent向右轉(zhuǎn)彎；第二行為1時，表示Agent向左轉(zhuǎn)彎；第三行為1時，表示Agent處于排斥范圍外，且沒接收到吸引信號的情況下，Agent保持直走的狀態(tài)。

如圖3所示，首先對序列1進行分析，左側(cè)的排斥信標強度大于臨界值5，則計算出兩側(cè)排斥信標強度的和與差，如圖可看出吸引信標強度之和與差都為0，表示未計算。兩側(cè)信標之和大于0，確保信號準確存在，左側(cè)與右側(cè)的排斥信標強度之差大于0，說明左側(cè)離排斥信標較近，Agent模塊向右轉(zhuǎn)彎，矩陣action的第一列為[1 0 0]T，表示執(zhí)行向右轉(zhuǎn)彎判定，與理論要求一致。對序列2進行分析，兩側(cè)的排斥信標都小于臨界值5，則計算出兩側(cè)吸引信標的和與差，如圖2所示，排斥信標的和與差都為0，表示未計算。左側(cè)與右側(cè)的吸引信標強度只差大于0，右側(cè)距離Agent的距離較近，Agent應向左轉(zhuǎn)彎，矩陣action的第二列為[0 1 0]T，表示執(zhí)行向左轉(zhuǎn)彎的判定，與理論一致。對序列3進行分析，兩側(cè)的排斥信標都小于臨界值5，則計算出兩側(cè)吸引信標的和與差，如圖2所示，排斥信標的和與差都為0，表示未計算。左側(cè)與右側(cè)的吸引信標強度只差小于0，右側(cè)吸引信標距離Agent較近，Agent應向右轉(zhuǎn)彎，矩陣action的第3列為[1 0 0]T，表示執(zhí)行向右轉(zhuǎn)彎的判定，與理論一致。下面可按此方式來一一驗證。

根據(jù)所得出的兩組類型信號的和與差，判定出Agent模塊是向左轉(zhuǎn)彎，向右轉(zhuǎn)彎或直走的狀態(tài)。在仿真算法中，轉(zhuǎn)彎的決策通過矩陣的形式表示，矩陣內(nèi)容如：

3 結(jié)束語

現(xiàn)有的多Agent系統(tǒng)，模塊間通信采用的是數(shù)字通信方式。相對而言硬件電路較復雜，且可靠性不高?；谝陨显?，本文提出一種新型的多Agent系統(tǒng)，模塊間僅通過信標檢測的方式進行信息交互。對系統(tǒng)的運行原理進行了詳細的描述。并對Agent模塊的移動規(guī)則進行主要的分析及研究，通過仿真來進一步進行了驗證。而且現(xiàn)如今無線網(wǎng)絡的發(fā)展已趨于成熟化，將這一技術(shù)應用到多Agent系統(tǒng)中，進行了多方向的融合，應用領域廣泛，具有很好的研究價值。

［1］謝學科.多Agent交互協(xié)作研究及系統(tǒng)模擬［D］.西安：西北工業(yè)大學，2005.

［2］何飛.基于Pi-演算的Agent交互模式研究［D］.太原：太原理工大學，2007.

［3］金士堯，黃紅兵，范高俊.面向涌現(xiàn)的多Agent系統(tǒng)研究及其進展［J］.計算機學報，2008，31（6）：881-894.

［4］陳丹，林金朝.無線定位系統(tǒng)及其發(fā)展趨勢［J］.山西電子技術(shù)，2006，7（6）：12-13.

［5］瞿雷.Zigbee技術(shù)及應用［M］.北京：北京航空航天大學出版社，2007：132-147.

［6］彭瑜.低功耗、低成本、高可靠性、低復雜度的無線電通信協(xié)議ZigBee［J］.自動化儀表，2005，26（5）：1-4.