基于Shape Theory 和Flocking的多智能體編隊機動控制

何嘉誠，姚其峰，代小林，宮大為，孫旭紅

（電子科技大學 機械與電氣工程學院，成都611731）

多智能體編隊機動控制是驅動一組具有特定形狀的編隊完成旋轉、放縮和平移運動，在城市搜救、資源探測、集群作戰和環境感知[1-3]等諸多實際應用中發揮了重要作用。

目前的編隊機動控制方法主要包括基于相對位移、基于相對距離和基于相對角度的三類算法[4]。這三類算法分別使用智能體之間相對位移、相對距離和相對角度作為約束條件，以此來定義多智能體編隊的隊形[5-8]。用來定義目標編隊的約束條件的不變性對于編隊的機動控制有著重要的影響。基于相對位移的算法能有效地追蹤時變平動的目標編隊[9]，卻不能實現編隊的放縮和旋轉運動。基于相對距離的編隊機動控制算法能夠實現編隊的平動和旋轉，但是不能實現編隊的放縮運動[10]。基于相對角度的編隊控制算法能夠實現編隊的放縮和平動，但是不能實現編隊旋轉運動。

為了提高編隊機動控制的性能，近些年來，學者們提出了一些新的定義編隊隊形的方法。例如質心坐標法[11]，應力矩陣法[6]，復拉普拉斯矩陣法[7]。使用這些理論作為定義編隊隊形的約束條件，提高了編隊約束條件的不變性。然而，上述方法都沒有被用于控制大規模的編隊運動[12-13]。

Shape Theory 是學者提出來的一種用來定義編隊的簡單方法[14]，它是指去除編隊的旋轉、放縮和平移后保留下的幾何信息。因此，當編隊進行旋轉、放縮和平移時編隊的幾何信息是恒定的。Shape Theory已經被用于定義目標編隊的隊形，但是它在解決編隊的機動控制方面仍然具有很大的潛力。

本文采用基于Shape Theory 和Flocking 算法[15]來解決編隊機動控制問題。先假設到達目標位置的可行路徑是已知的，在可行路徑上以一定的步長選取路徑點，然后以每個路徑點為中心設置正方形的限制區域；再利于基于Shape Theory 的編隊隊形控制算法從初始位置開始依次在每個限制區域中計算出滿足隊形約束的目標編隊的位置； 最后使用Flocking 算法驅動智能體依次奔向這些目標編隊，直到智能體運動到目標位置。

1 理論基礎

本節主要講述涉及到本文提出的編隊機動控制算法的理論基礎，主要包括Flocking 算法[15]和Shape Theory 理論[12]。

1.1 Flocking 算法

Flocking 算法是一種由生物集群行為而啟發的分布式算法，它是多智能體集群行為的一種表現式。這種集群行為是通過智能體之間的簡單的交互來完成的，該算法不使用全局信息。這種集群行為主要通過以下3 種規則構建：

避免碰撞智能體之間會保持一定的距離，當距離過近時智能體之間會產生排斥力；當距離過遠時智能體之間會產生吸引力。

向中心聚集智能體會向周圍的群體靠近。

速度一致性每個智能體的速度與周圍所有智能體的平均速度保持一致。

文獻[15]為分析和設計分布式Flocking 算法提供了理論框架，在無障礙物和目標的環境中，該算法中每個智能體的控制輸入由三部分組成：

當環境中有目標為智能體導向時，每個智能體i 的控制輸入包含兩個部分，其中：

式中：Ni表示智能體i 的鄰居的個數。Φα（z）是由下面函數定義的功能函數：

式中：rα和dα是α-lattice 的常參數；Φ（z）是一個具有參數a，b，c 的非均勻的s 形函數，是一個數值從0 到1 均勻變化的bump 函數，其定義如下：

式（2）的另一些參數定義如下：‖qj－qi‖σ表示連接qj和qi的向量的σ-norm。σ-norm 的定義如下所示：

式中：nij是連接qi和qj直線上的向量，且ε∈（0，1）是σ-norm 的一個參數。最后，aij（q）定義如下所示：

式中：c1和c2是正整數。

使用Flocking 算法進行目標跟蹤，每個移動的智能體i 使用ui作為控制輸入。

1.2 Shape Theory

Shape Theory 是一種新的定義編隊的方法。假設在二維歐幾里得空間中有個n 智能體，給定目標編隊的隊形：

2 問題分析

在闡述問題前，先對多智能體系統做如下假設：

a）多智能體系統包含n 個可移動智能體，所有智能體在長為l，寬為w 的二維區域內運動。

b）通信能力：每個智能體能夠通過通信網絡和其鄰居智能體傳遞信息。

c）探測能力：每個智能體的探測范圍是一個圓心為其所在位置，半徑為r 的圓。智能體能夠探測到其探測范圍內的所有鄰居智能體。

d）動力學特性：考慮到智能體之間避碰的情況下，每個智能體之間的運動控制是獨立的。qi，pi∈R2分別表示智能體的位置和速度，智能體的運動特性可以由下式表示：

編隊的機動控制問題是控制一組智能體在保持編隊隊形的情況下進行旋轉、放縮和平移運動。智能體之間要避免碰撞，且在復雜的環境中能夠適應環境的變化。多個智能體從初始位置開始，并以一定的隊形運動到目標位置，這個過程主要應解決3 個問題：①編隊隊形形成，多個智能體形成給定的編隊隊形；②設置限制區域，以一定的步長沿著可行路徑設置多個限制區域，以實現編隊的運動；③編隊變換，編隊在運動的過程中需要調整編隊的形狀或者大小來適應環境的變化。

3 問題求解

3.1 編隊隊形形成

文獻[12]將Shape Theory 用于定義編隊的隊形，進而將編隊的隊形控制問題轉化為凸優化問題。文獻[14]使用遞歸神經網絡求解文獻中的凸優化問題，提高了形成目標編隊的速度。

式中：P 為編隊的初始位置；Q 為目標編隊的位置；A 為編隊的隊形約束矩陣；α 為編隊的放縮倍數；Φ為預先設定的限制區域。

式（13）是一個非光滑的凸優化問題，文獻[14]使用遞歸神經網絡模型來求解該優化問題，其模型如下所示：

其求解結果如下所示：

其中γ=（?T‖P－Q‖）T，且

通過求解常微分方程（15），可以得到滿足約束條件的目標編隊坐標

3.2 設置限制區域

本文先假設已知一條從初始位置到目標位置的可行路徑。在可行路徑上以步長k 為間隔，均勻地選取一系列的路徑點，再以路徑點為中心設置正方形的限制區域。其示意圖如圖1所示。在每個限制區域中，通過使用遞歸神經網絡模型（14）求解非光滑的凸優化問題（13），便可求出在每個限制區域中目標編隊Qj（j 表示限制區域的數量）。值得注意的是Q1的初始是隨機設置的，Qj（j=2，…，m）的初始位置為Qj-1。

圖1 在路徑點上設置限制區域Fig.1 Set a restricted area on waypoints

3.3 編隊變換

為了提高多智能體編隊對環境的適應能力，尤其是通過狹窄空間的過程中，需要調整編隊的隊形（如編隊的放縮倍數或形狀）來適應環境的變化。

我們采用與編隊形成類似的方案，假設已知具有特性形狀的初始編隊P，要變換成目標編隊Q，只需使用遞歸神經網絡模型（14）求解問題（13）即可。本文采用的編隊變換的方法與編隊形成的區別主要是初始編隊的形狀不同（編隊形成過程中其初始形狀是不規則的；編隊變換過程中其初始形狀是規則的）。

3.4 算法流程

本文提出的算法偽代碼如下：

開始

（1）設定編隊初始位置P 和目標隊形S；

（2）根據已知路徑設置步長k 和路徑點；

（3）根據路徑點設置限制區域；

（4）for j=1 to m do

使用公式（15）依次求解Qj；

end

（5）for j=1 to m do

其中error 智能體形成過程中智能體的實際位置與目標位置之間的穩態誤差。distance 為一個略大于error 的常數。通過調節distance 的大小能夠改變編隊速度的平滑性。

4 系統仿真

本章節進行了一個編隊機動控制的仿真實驗，來驗證本文所提出算法的可行性。

我們采用一個具有11 個智能體組成的二維編隊，且智能體的動態特性如式（12）所示。本次仿真的目的是使多個智能體在保持給定隊形的前提下，順利地避開障礙物并到達目標位置。編隊的目標隊形如圖2所示。使用Matlab 軟件的ODE 工具箱來求解微分方程（15），β 的值設置為20[14]、步長k=50、distance=3.0、編隊的旋轉角度和放縮倍數分別為2π 和12。在次仿真實驗中，如果qi=pi，就令?‖pi－qi‖2=0。令s（t）＝（qT（t），μ（t）T）代表遞歸神經網絡的狀態向量。

圖2 編隊的目標隊形（每一個圓代表一個智能體）Fig.2 Shape of expected formation（dots represent agents）

本仿真首先假設一條已知的可行路徑，如圖3中的實線所示； 并以相應的步長k 設置限制區域；五角星為編隊的終點，其結果如圖3所示。根據上文的算法偽代碼，本文使用Matlab 軟件對該軟件進行仿真，其結果如圖4所示。

圖3 可行路徑及限制區域規劃（空心矩形表示編隊的限制區域；直線代表可行位置；五角星為目標位置；黑色矩形為障礙物）Fig.3 Plan optimal paths and restricted areas（hollow rectangle indicates the restricted area of the formation，straight line represents the feasible position，pentagram is the target position；the black rectangle is the obstacle）

圖4 編隊機動控制仿真（黑色的圓表示智能體運動過程中不同時刻的位置；曲線表示智能體的運動軌跡）Fig.4 Simulation of formation maneuver control（black circles in the figure indicate the position of the agent at different times during the movement of the agent，curve represents the movement track of the agent）

圖4展示了使用本文提出的算法得到的編隊機動控制仿真結果。從圖4中可以看出該算法能夠控制智能體先形成給定的目標編隊，并能使智能體在保持隊形的情況下順利通過障礙物，并到達指定位置。

5 結語

本文將基于Shape Theory 的編隊隊形控制算法應用于解決多智能體的編隊機動控制問題。在給定的可行路徑上，以一定的步長依次從初始位置到目標位置設定路徑點； 再分別以這些路徑點為中心，設置正方形的限制區域，使用遞歸神經網絡分別求解多智能體在每個限制區域中的目標編隊的位置。最后使用Flocking 算法使智能體依次奔向這些目標編隊，從而到達目標位置。最后，通過仿真實驗驗證了該算法的有效性。