基于有限狀態機的多機器人圍捕策略研究

張奇松，胡玉蘭

（沈陽理工大學 信息科學與工程學院，遼寧 沈陽 110168）

在機器人協調協作中，多機器人圍捕任務可以看作多機器人隊形控制的另一種形式。在傳統隊形控制中，有跟隨領航者法（Leader-follower）、基于行為法（Behavior-based）、虛擬結構法（Virtual structure）。其中跟隨領航者法即基于Leaderollower法和虛擬結構法的隊形控制方法，側重于傳統的控制理論，可以利用動態系統理論對編隊系統的穩定性進行分析，但是缺乏基于行為控制方法中的隊形反饋信息。為了增加基于Leader-follower方法在進行編隊控制時的實用性，這里提出一種基于有限狀態機的多機器人圍捕方案，引入隊形條件反饋信息，建立基于條件反饋機制和Leader-follower相結合的多機器人隊形控制模型實現了多機器人系統的隊形控制，并給出有限狀態機原理，定義圍捕各階段的不同狀態。

1 改進式Leader-follower隊形控制

1.1 Leader-follower基本思想

基于Leader-follower法是由Leader給定Follower的運行參數，具體的運動控制由Follower自行計算，該方法具有很好的系統可擴展性、運動策略靈活性和計算并行性。但是Leader與 Follower相對獨立，Leader不容易得到 Follower的跟蹤誤差，如果Leader運動過快可能導致落后的機器人離隊，而且整個系統對Leader機器人依賴性較大，如果Leader機器人發生故障會導致整個系統癱瘓。針對上述缺點，一些文獻提出相應的解決辦法。文獻[1]利用反饋線性化得到非完整約束機器人的軌跡跟蹤控制法則；文獻[2]平滑時變反饋控制法則構成一個開環鏈式的隊形；文獻[3]引入合作方法，即Follower的運動不僅由自身決定，還受到其他機器人的影響。

在利用傳統的Leader-follower方法控制隊形過程中，為了在避障和保持隊形之間進行協調，常常引入“虛擬機器人”概念，并將機器人的運行狀態分為正常運行模式和避障模式。當某個機器人處于避障模式時，其他機器人參考替代它的“虛擬機器人”以保證正常的運行，但如果Leader根據隊形反饋進行的調節過于頻繁，會導致整體運動不順暢，甚至可能當多個Follower同時處于避障狀態，由于Leader隊形反饋停止運動，導致系統處于死鎖狀態。對此，這里引入了隊形的條件反饋機制，如圖1所示。

圖1 隊形條件反饋的Leader-follower控制結構Fig.1 Leader-follower control structure of formation conditions feedback

1.2 條件反饋隊形控制的基本原理

條件隊形反饋的基本原理為：

1）初始時Leader接受任務T，然后根據環境信息E進行運動規劃。

2）Leader將自身的運行狀態 S=（XL，YL，VL，WL）和任務信息 T 通過公共變量區通知 Robot i（i=1，2，...，n）。

3）每個follower根據任務T計算自己在隊形中的期望位置 Pdi=（xdi，ydi）（i=1，2，...，n），結合環境信息 E，根據控制策略產生控制量，即（υi，wi）。 隊形信息 P=（P1，P2，...，Pn）被反饋給Leader，其中P1為Follower1當前位置。在正常運動時Leader不將隊形反饋信息作為自己運動的依據，依靠Follower自行調整速度來提高隊形保持率。

4）如果當個別機器人處于通信范圍邊緣時，Leader降低運動速度，使得落后機器人能夠趕上，防止Follower掉隊。在特殊情況下（等待較長時間而最遠的Follower與Leader之間的距離沒有縮短），Leader會放棄故障機器人，重新進行隊形調整。

2 多機器人圍捕策略設計

2.1 開闊隊形偵查策略

在機器人行進過程中，為了保證系統具有強的防御性能，獲得詳細的環境信息和保持近距離的通信，選擇具有向心性的隊形（像圓形、菱形）。線形隊形（縱隊和橫隊）中機器人位置非常開闊，偵查范圍廣、重復偵查區域少，所以這里使用線形隊形作為偵查隊形。

2.2 半圓形隊形預包圍策略

在開闊地帶執行圍捕任務時，圓形包圍隊形難以直接形成，因為當invader發現圍捕機器人后會改變運動軌跡，多機器人系統預先分配的包圍點便失去了作用。為此，將最后的圍捕分為兩個階段。

第1階段為扇形展開半圓形預包圍圈，如圖2所示。在圍捕任務中，機器人一般具有略強于Invader的偵查能力，所以機器人會先于Invader發現對方。最早發現Invader的機器人自動成為圍捕階段的Leader，然后其根據擬合出的Invader軌跡確定出預包圍點，并根據機器人之間的位置關系分配半圓形預包圍隊形的隊形點。因為此時重要的不再是機器人到達隊形點的先后時間，而是能夠有效地堵截Invader的逃脫方向。當Invader發現機器人后會首選轉向逃脫，此時機器人若能夠將其正前方180°的路徑全部封堵，則Invader只能反向逃脫，這樣可以為接下來圓形包圍隊形的形成爭取有利條件。

圖2 扇形展開半圓形預包圍隊形Fig.2 Sector semicircle beforehand surrounded formation

第2階段為收縮隊形并形成圓形包圍圈。為了防止Invader過早發現機器人，本文將預包圍隊形的半徑設的比較大，如果直接形成運行圓形包圍隊形，早會造成相鄰機器人之間的空隙過大，Invader可以從空隙中逃脫，導致圍捕的失敗。所以，本文設計機器人預包圍隊形首先向Invader方向收縮，然后形成圓形包圍隊形。

2.3 圍捕任務退出策略

在動態圍捕任務中，因為不能確保機器人每一次都能偵查到動態目標，所以設定兩種退出方式：1）按照偵查隊形前進N步沒有發現目標，則系統退出圍捕任務；2）發現目標后，在圍捕過程中，以要求隊形包圍Invader，并且Invader靜止，則圍捕任務完成。

3 基于有限狀態機的多機器人圍捕

3.1 圍捕有限狀態機設計

設定有限狀態機為一個三元組M=（E，Qst，φ），各變量具體含義如下：Qst={q1，q2，...，qm}為離散狀態的有限集合；E={e1，e2，...，en}為Leader指令的有限集合；φ為從一個狀態到另一個狀態的映射，可表達為 φ（qs，E）=qk∈Qst。

在系統模型中 Qst包含6種狀態：初始化（q1）、保持隊形運行（q2）、偵查（q3）、半圓隊形預圍捕（q4）、圓形隊形捕捉（q5）和退出（q6），其中在 q1、q3、q4狀態的初始時刻要完成新隊形點的分配及Leader更換。

初始時刻，機器人群體處于無序排列的狀態，Leader機器人發出啟動指令（e1），機器人首先組成指定隊形，然后向指定區域運動。在保持隊形運動過程，機器人主要任務是快速運動，此外要低頻率的進行Invader偵查。如果發現環境復雜，機器人會自行進行蛇形隊形的轉換。如果在這個階段發現Invader（e2），機器人則直接進入捕捉狀態。機器人到達指定區域（e3）后，開始轉換為比較開闊的偵查隊形。由于環境的限制，本文將捕捉結果分為 2種：1）發現 Invader（e2），則機器人進行圍捕，捕捉到 Invader后退出（e8）；2）到達偵查限制（e6）而沒有發現Invader，則系統直接退出（e8）。在圍捕的過程中可能發生Invader逃脫（e5）的情況，這是多機器人系統重新進入偵查狀態。在機器人進行捕捉過程中，最先發現Invader的機器人自動成為新的Leader，整個捕捉過程由新Leader控制。為了加快捕捉任務完成的速度，系統首先組成半圓形隊形（e4）進行預捕捉。Leader根據Invader的運動方向和運動速度預測出捕捉點，然后以捕捉點為圓心，在Invader的運動方向上形成較大半徑的半圓形包圍隊形，從而阻擋住Invader的逃脫，而且能夠較晚被Invader發現。形成半圓包圍隊形后，Leader發出圓形包圍指令（e7）。首先收縮隊形，各機器人向Invader的位置移動，Invader會選擇逃脫方向，這時各機器人在Invader周圍形成圓形包圍圈，從而徹底阻擋住Invader的逃脫路線，圍捕任務完成。

根據上述描述，機器人狀態轉換如下：φ（q1，e1）=q2，φ（q2，e2）=q4，φ（q2，e3）=q3，φ（q3，e2）=q4，φ（q4，e7）=q5，φ（q4，e6）=q6，φ（q4，e5）=q3，φ（q5，e5）=q3。

3.2 程序流程

圖3為機器人動態，圍捕程序流程圖。

從該流程圖可以看出，機器人的運行場景定為不同的狀態，在每種狀態中，機器人的功能模塊的組合順序和獲得的參數存在差別，通過有限狀態機來決定行為的映射規則。執行層由執行機構和探測模塊組成，執行機構的主要功能是將行為層的控制參數轉化為實際的物理控制量并通過硬件實施，探測模塊的主要功能是利用各種傳感器探測周圍環境并將環境信息轉化為信息處理模塊可使用的信息量。

4 仿真實例

圖3 動態圍捕流程圖Fig.3 Flow chart of dynamic seizing

仿真系統采用Visual C++語言開發，在仿真中機器人的半徑為2 cm，步長為0.5 cm，間隔時間為100 ms，本文規定隊形中Follower的位置誤差為2 cm。圖4給出了圍捕實驗中7種仿真圖。

在圍捕實驗中，Invader采用跟圍捕機器人相同的功能設置，只是在傳感器感知范圍上略微存在差別。當沒有探測到任何障礙物時，Invader為直線運動；否則，它朝向安全的方向運動。

圖4 7種仿真圖Fig.4 Seven kinds of simulation diagrams

從以上仿真圖可以看出本文根據有限狀態機原理將機器人分為 6種狀態，其中圖 4（a）～圖 4（f）分別對應初始化，保持隊形初始化、保持隊形運行、偵查、半圓隊形預圍捕、圓形隊形捕捉和退出。而圖4（g）為追捕機器人將入侵機器人圍在其中心，根據避碰原則（即入侵機器人將其他機器人視為動態障礙物）入侵機器人沒有躲避的空間，不能再移動，根據退出條件，圍捕成功，系統結束運作。

5 結 論

本文主要研究了多機器人的協作圍捕問題。為了實現圍捕任務，提出了一種基于條件反饋機制的Leader－followers隊形控制方法，同時采用有限狀態機在不同狀態之間進行切換。每種狀態的具體實現過程，都是由隊形形成和隊形保持組成，通過這種狀態轉換帶動隊形轉換的形式，將協調編隊與圍捕任務有效地結合在一起。最后通過仿真驗證了算法的有效性。

[1]Desai J P， Ostrowski J， Kumar V.Controlling formations of multiple mobile robots[C]//IEEE International conference on Robotics and Automation Belgium，1998:2864－2869.

[2]Yamaguchi H，Burdick J W.Asymptotic stabilization of multiple nonholonomic mobile robots forming group formations［C］//IEEE Int Conf on Robotics and Automation，Belgium，1998：3573－3580.

[3]Pereira G A S，Das A K，Kumar V，et a1.Formation control with configuration space constraints[C]//Proc of the IEEE/RJS Int Conf on Intelligent Robots attd Systems，Las Vegas，2003：2755－2760.

[4]程磊.多移動機器人協調控制系統的研究與實現 [D].武漢：華中理工大學，2005：37－42.

[5]劉海波，顧國昌，張國印.智能機器人體系結構分類研究[J].哈爾濱工程大學學報， 2003， 24 （6）:57－60.LIU Hai-bo，GU Guo-chang，ZHANG Guo-yin.Intelligent robot structure system classification research[J].Journal of Habin Engineering University，2003，24（6）:57－60.

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