基于飛蛾信息素尋偶機制的無人機集群協同搜索

劉云昊，鄧亦敏，段海濱，魏 晨

(北京航空航天大學 自動化科學與電氣工程學院， 北京 100083)

無人化、智能化和集群化是無人機(unmanned aerial vehicle, UAV)發展的必然趨勢[1]。目前，無人機集群越來越多地用于協同搜索中。無人機集群協同搜索，指的是在未知環境或者有先驗信息條件下，多無人機系統通過去中心化自組網信息共享、分布式決策和協調運動控制，實現快速區域覆蓋或者鎖定目標位置[2]。在未知環境條件下，協同搜索策略主要是規劃路徑以實現區域覆蓋，常見的方法有Voronoi區域覆蓋、精確單元覆蓋、多邊形覆蓋和不相交區域覆蓋四類[3]；在有目標先驗信息條件下，通常通過在線規劃的方式進行協同目標搜索，常見的方法有概率圖法[4-5]、信息素圖法[6-8]、收益圖法[9-10]等。然而這些研究大多以區域覆蓋率作為搜索任務的評價指標，針對移動目標的研究較少。

自然界中的生物個體利用簡單的規則，形成了魯棒性高、自適應程度高、可擴展性高的自組織行為[1]。飛蛾，昆蟲綱鱗翅目昆蟲，在其尋偶過程中，成年雌性飛蛾分泌釋放性信息素，引誘雄蟲前來交配[11]。針對飛蛾通過性信息素感知視距之外的異性并自發飛行至異性位置的尋偶行為的研究已經取得了一定進展。Groot等[12]發現由于環境的影響，飛蛾的性信息素存在著數量和質量的種間差異。Justus等[13-14]研究表明當處于低濃度均勻信息素環境時雄性粉斑螟蛾更傾向于逆風飛行，而高濃度均勻信息素環境中則會更傾向于選擇側風飛行；當粉斑螟蛾處于非均勻的信息素羽流中時，則會選擇與風向成一定角度飛行。Zweerus等[15]證明了雌性綠角翅夜蛾會根據性信號來評估雄性個體，并且通過遠離的方式來拒絕交配。Hosseini等[16]發現雄性的綠角翅夜蛾會釋放雄性信息素來排斥同性個體。Nakano等[17]研究表明雄性亞洲玉米螟會在接近雌性個體后依據信息素濃度對雌性進行定向。飛蛾依靠信息素的尋偶行為與無人機的搜索任務類似，因此這種飛蛾信息素尋偶機制對于無人機集群協同目標搜索有一定的借鑒意義。

本文面向無人機集群對移動目標的協同搜索，提出了一種基于飛蛾信息素尋偶機制的分布式集群協同搜索方法，并在無人機平臺上進行了外場飛行試驗。

1 問題描述

假設N架無人機對固定區域內的某一移動目標進行搜索，目標位置和目標的移動策略未知，無人機集群網絡拓撲為全連通。當某一無人機滿足對移動目標位置鎖定條件時，認為協同搜索任務完成。

1.1 搜索區域建模

假設搜索區域為長和寬分別為L和W的矩形。對搜索區域用邊長為l的方形進行網格化，如圖1所示。定義Ex=W/l為x軸方向網格數，Ey=L/l為y軸方向網格數。以i行、j列網格的編號(i,j)代表網格中心點坐標(xi,yj)，其映射關系如式(1)所示。網格化后的搜索區域映射到信息素圖，初始輪次信息素任意網格的信息素數值ρi,j為0。

(1)

圖1 搜索區域示意Fig.1 Search area diagram

1.2 無人機和目標建模

忽略無人機和目標的高度變化，將無人機和目標簡化為二維場景區域內的質點[5]，并認為無人機和目標移動完成后位于所在網格的中心點上。以第n(1≤n≤N)架無人機所在網格的編號表示無人機n的位置Pn；以目標t所在網格的編號表示目標的位置Pt。考慮無人機和目標的運動速率限制，每一輪次無人機和目標只能從當前網格移動到相鄰的網格，如圖2所示。

圖2 無人機可移動范圍示意Fig.2 UAV reachable range diagram

以(δn(x)(k),δn(y)(k))表示無人機n第k輪次的運動策略，考慮搜索區域的邊界限制，其滿足約束：

(2)

則無人機n第k+1輪的位置可以用式(3)計算：

(3)

設定無人機n鎖定目標t的位置的條件為Pt在無人機n的單輪次可移動范圍內，即：

(4)

1.3 搜索設備建模

假設目標搜索設備的最大搜索距離為Dr，在Dr范圍內，可以得到目標t相對無人機n的距離dn,t和角度θn,t。dn,t和θn,t的計算公式如下：

(5)

其中，d(n,t)r和θ(n,t)r表示目標t相對無人機n的真實距離和角度；δd∈(0,1)為距離誤差限比例；δθ∈(0,π]為角度誤差限；Nr～N(0,0.5)為隨機數。通過式(5)，目標搜索設備得到的距離dn,t在d(n,t)r±d(n,t)rδd范圍內和得到的角度θn,t在θ(n,t)r±δθ范圍的概率為95%。

2 仿飛蛾信息素尋偶機制的集群搜索建模

模仿飛蛾的信息素尋偶機制，建立飛蛾信息素尋偶行為模型，并映射到無人機的集群協同搜索中。將雌性飛蛾映射為目標t，雄性飛蛾映射為無人機n。數字信息素數值ρi,j的正負分別對應飛蛾雌性信息素的吸引作用[11]和雄性信息素的排斥作用[16]。信息素圖按照飛蛾信息素的揮發、傳播、分泌機制進行更新，無人機基于雄性飛蛾基于信息素的尋偶行為機制進行運動策略的選擇。

2.1 仿飛蛾信息素揮發機制建模

自然環境中，飛蛾釋放的信息素會隨著時間不斷揮發，從而濃度不斷降低。模仿這一現象，定義吸引信息素揮發因子v+(v+>0)和排斥信息素揮發因子v-(v-<0)[6]。仿飛蛾信息素的揮發機制，對于全局信息素圖中的任意網格，其信息素數值按照式(6)實現更新：

(6)

v+和v-的數值與信息素圖的累計效應負相關，類似于PID控制中積分控制項，可以消除搜索過程的穩態誤差、提高搜索精度。合理設置v+和v-的數值，可以實現無人機在快速跟蹤和精準搜索間的平衡。

2.2 仿飛蛾雌性信息素傳播機制建模

雌性飛蛾分泌釋放雌性信息素，雌性信息素隨風在一定范圍內傳播，引誘雄性飛蛾前往交配[11]。模仿飛蛾雌性信息素傳播機制，定義目標t釋放吸引信息素ρt(ρt>0)。考慮目標搜索設備的性能限制，定義以無人機n所在位置Pn為圓心、以dn,t+dn,tδd為半徑Rn、角度范圍在[θn,t-δθ,θn,t+δθ]的扇形區域為吸引信息素傳播區域ROPn。ρt沿著ROPn的弧線向圓心方向傳播，如圖3所示。

圖3 吸引信息素傳播區域Fig.3 Attract pheromone propagation range

將ROPn映射到信息素圖中，當網格中心坐標(xi,yj)位于ROPn內時，認為該網格受到吸引信息素傳播的影響[7]，按照式(7)所示的飛蛾信息素傳播機制對網格的信息素數值ρi,j進行更新：

(7)

其中，d(i,j),n為網格(i,j)的中心位置相對無人機n所在網格的中心位置的距離。

2.3 仿飛蛾雄性信息素分泌機制建模

在雄性飛蛾的尋偶過程中，雄性飛蛾分泌的雄性信息素會抑制其他雄性的飛行，從而在求偶過程中起到排斥競爭雄性的作用[16]。模仿飛蛾雄性信息素分泌機制，無人機釋放排斥信息素ρu(ρu<0)標記訪問過的網格點，排斥其他無人機，提高搜索效率。以無人機n所在網格及其鄰近網格作為排斥信息素ρu的可影響區域。可影響區域內的網格的信息素數值按式(8)更新：

ρi,j=ρi,j+ρu

(8)

2.4 信息素圖的風向建模

(9)

逆風方向θn(u)和側風方向θn(c)的計算公式如下：

(10)

逆風方向θn(u)和側風方向θn(c)的合成方向θn(u+c)的計算公式如下：

(11)

2.5 仿飛蛾信息素尋偶行為機制建模

模仿飛蛾信息素的尋偶行為機制[13-14]，當無人機n處于均勻信息素場時，說明目標t的吸引信息素穩定地傳播到無人機n所在位置。此時若局部信息素濃度低，說明目標t與無人機n距離較遠，則無人機n選擇逆風飛行，接近目標t所在區域；若局部信息濃度高，說明目標t與無人機n距離較近，則無人機n選擇側風飛行，跟隨目標運動方向。當處于非均勻信息素場時，說明在當前區域，目標t的吸引信息素的傳播并不穩定。此時無人機n選擇與風成一定角度飛行，在接近目標位置的同時，離開不穩定區域。在無人機n的可移動范圍內，如果信息素數值最大值maxρn所在網格為無人機n所在網格，或者maxρn與ρPn接近時，認定無人機n處于均勻濃度信息素場中；否則認為無人機n處于非均勻濃度信息素場中。定義信息素濃度常數ρf，如果maxρn低于ρf，認為無人機n處于低濃度信息素場中；否則認為無人機n處于高濃度信息素場中。無人機n按照算法1選擇飛行方向θn。

算法1 無人機飛行方向選擇

無人機n選擇的飛行方向θn與運動策略(δn(x),δn(y))的映射關系可由表1得到。

表1 飛行方向與運動策略的映射Tab.1 Mapping of flight direction and motion strategy

2.6 無人機集群避撞策略

無人機集群協同搜索過程中所有可能的碰撞情況，如圖4所示,可以歸為三類：規劃位置重合(見圖4 (a))；規劃至另一無人機的當前位置(見圖4 (b)～(c))；規劃路線交叉(見圖4 (d))。

(a)規劃位置重合 (b)規劃至另一無人位置(a)Planning location coincidence (b)Plan to the locattion of another UAV

(c)規劃至雙方位置 (d)規劃路線交叉(c)Plan to bot lacations (d)Planning route crossing圖4 無人機機間碰撞情況Fig.4 Collision between UAVs

需要說明的是，由于分布式集群中機間通信的異步特性，即使無人機n規劃離開當前位置，另一架無人機規劃至無人機n當前位置(見圖4 (b))仍被認為是有碰撞風險的情況。

定義cn(f)為碰撞標志常數，通過算法2，無人機n判斷本機的運動策略是否會與其他無人機發生碰撞。

算法2 無人機碰撞判斷

當cn(f)≥3時，認為無人機n的運動策略(δn(x),δn(y))會引發碰撞，因此將其運動策略修改為(0,0)，即

(12)

在同步通信的無人機集群中，當無人機集群內所有個體完成碰撞判斷和運動策略修改后，便可以避免集群內無人機的碰撞。而在分布式無人機集群中，無人機的機間通信往往是異步的，因此設計了如圖5所示的無人機集群避撞策略。

圖5 無人機集群避撞策略Fig.5 Collision avoidance strategy of UAV swarm

當無人機得到本輪的運動決策后，并不立即執行，而是先將自己的運動策略廣播到集群中；T為無人機的等待時間，T大于無人機接收消息的周期，在此期間無人機仍在接收其他無人機的消息。因此，如果由于無人機集群異步通信導致本輪次第一次碰撞判斷時未發現碰撞情況，可通過等待T時間后的第二次碰撞判斷來避免。

2.7 目標逃逸策略

假設目標搭載和我方無人機相同性能的搜索設備，在Dr范圍內，可得到無人機n相對目標t的距離dt,n和角度θt,n，其數值按式(5)計算。考慮目標的逃逸行為，給出如算法3所示的目標移動策略。計算出目標的逃逸方向θt(e)，然后通過表1的映射關系可以得到目標的移動策略(δt(x),δt(y))。

算法3 目標移動策略

根據社會力模型，認為目標受到無人機和區域邊界的斥力ft,uav和ft,b，目標根據受到的斥力和選擇運動方向。為避免斥力抵消引起“陷阱”和ft,uav與ft,b反向導致目標t向無人機方向飛行等不合理情況的發生，引入側向力ft(c)進行修正。

3 仿飛蛾信息素尋偶機制的集群搜索實現流程

圖6 仿飛蛾信息素尋偶機制的搜索實現流程Fig.6 Search process based on moth pheromone courtship

4 仿真實驗

4.1 仿真實驗設計

仿真實驗參數如表2所示。為說明本文所提方法的有效性，將基于飛蛾信息素機制的協同目標搜索方法和基于螞蟻信息素機制[18]的方法進行對比。針對動態目標搜索場景，在螞蟻信息素方法的仿真流程中，增大吸引信息素揮發因子v+至1.5，作為一種改進螞蟻信息素方法，以驗證2.1節的結論。

表2 仿真實驗參數Tab.2 Simulation experiment parameters

分別使用基于螞蟻信息素機制的基本螞蟻信息素方法、增大v+之后的改進螞蟻信息素方法和基于飛蛾信息素尋偶行為機制的飛蛾信息素方法在相同場景下進行100次仿真實驗，并記錄仿真數據結果進行分析。當仿真輪次k≥300時，認為無人機集群沒有搜索到目標，本次仿真搜索失敗。

4.2 仿真結果分析

100次仿真實驗的數據對比如圖7所示。基本螞蟻信息素方法的仿真實驗，搜索成功率只有44%，在成功搜索到目標的實驗里，平均搜索輪次為132.41，搜索輪次的標準差為74.99。增大v+的改進螞蟻信息素協同搜索方法平均搜索輪次為83.41，有效搜索輪次的標準差為25.77；而基于飛蛾信息素尋偶機制的協同搜索方法平均搜索輪次為53.87，標準差為1.889 1。基于飛蛾信息素尋偶機制方法的搜索所用的平均輪次最少，且擁有最小的標準差，體現出更高的搜索效率和穩定性。

圖7 仿真實驗結果對比Fig.7 Comparison of simulation results

取三種方法的最后一次仿真實驗，仿真路徑對比如圖8所示，最終形成的信息素圖歸一化之后如圖9所示。從圖中可以看出：基本螞蟻信息素方法，無人機集群最終形成的信息素圖中高數值區域與無人機整體移動路徑基本重合，說明其信息素圖能很好地反映出目標的整體移動態勢，但也增大了過去目標位置信息在無人機運動決策時的影響，因此在對移動目標搜索時的效率較差。增大v+的改進螞蟻信息素方法，信息素圖的高數值區域較小，說明其更多反映了目標的實時態勢；但是高數值區域與目標最終位置區域存在較大誤差，說明該方法很難抑制傳感器誤差給運動決策帶來的影響。而飛蛾信息素方法得到的信息素圖，高數值區域與無人機整體移動路徑基本重合，說明其信息素圖能很好地反映出目標的整體移動態勢，而且該方法基于飛蛾信息素尋偶機制，結合實時信息進行運動策略選擇，因此具有更高的效率和穩定性。

(a) 基本螞蟻信息素方法(a) Basic ant pheromone method

(b) 改進螞蟻信息素方法(b) Improved ant pheromone method

(c) 飛蛾信息素尋偶方法(c) Moth pheromone courtship method圖8 螞蟻和飛蛾信息素方法搜索路徑對比Fig.8 Contrast of path in ant and moth pheromone methods

(a) 基本螞蟻信息素方法(a) Basic ant pheromone method

(b) 改進螞蟻信息素方法(b) Improved ant pheromone method

(c) 飛蛾信息素尋偶方法(c) Moth pheromone courtship method圖9 螞蟻和飛蛾信息素方法信息素圖對比Fig.9 Contrast of pheromone map in ant and moth pheromone methods

仿真結果表明，在移動目標的搜索問題上，通過適當提高吸引信息素揮發因子v+，可以增強螞蟻信息素方法對移動目標搜索場景的適應性；而本文的基于飛蛾信息素尋偶機制的集群協同搜索方法具有更高的效率和穩定性。

5 外場飛行試驗

以四旋翼無人機作為基于飛蛾信息素尋偶機制的集群搜索方法的飛行驗證平臺，如圖10所示。

圖10 四旋翼無人機框架結構Fig.10 Quadrotor UAV frame structure

四旋翼無人機上搭載自組網無線通信設備(數傳)，通過自定義通信協議實現集群間的信息交互。在自駕儀的Ardupilot源碼基礎上編寫基于飛蛾信息素尋偶機制的無人機集群目標搜索程序。

5.1 外場飛行試驗場景設計

飛行試驗場景與第4節中的仿真場景一致。使用3架無人機作為我方無人機，1架無人機作為目標，在固定區域內對所提基于飛蛾信息素尋偶機制的集群搜索方法進行試驗。因為搭建的四旋翼無人機平臺上沒有可以感知目標的搜索設備，所以在搜索過程中敵我雙方也要進行通信，以獲取對方的位置信息，并分別根據式(5)和式(9)計算出含誤差的對方距離和角度。

考慮到無人機本身的定位誤差，為保證飛行試驗安全，對無人機進行分層處理。分別設置我方3架無人機和1架目標無人機的飛行高度為14 m、12 m、10 m和8 m，在計算距離時，不考慮高度差帶來的影響。取等待時間T為1 s，線程1和線程2的運行周期為0.25 s，進行飛行試驗。

5.2 外場飛行試驗結果分析

基于飛蛾信息素尋偶機制的無人機集群搜索飛行試驗的數據結果如圖11所示；無人機和目標的飛行路徑如圖12所示。我方3架無人機起飛之后，通過本文所提的方法對敵方1架無人機進行搜索，目標無人機按照本文提出的目標移動策略進行逃逸。從經緯度數據和路徑圖可以看出，目標雖然有逃脫我方無人機搜索范圍的趨勢，但是最終仍被無人機3鎖定位置。飛行試驗最后形成的信息素圖如圖13所示，可以反映出目標的整體移動過程。被鎖定時無人機和目標的外場實拍如圖14所示。

(a) 外場飛行試驗緯度數據(a) Latitude data in outdoor flight verification

(b) 外場飛行試驗經度數據(b) Longitude data in outdoor flight verification圖11 無人機和目標的經緯度數據Fig.11 Longitude and latitude data of UAV and target

圖12 外場飛行試驗中無人機和目標的移動路徑Fig.12 Path of UAV and target in outdoor flight verification

圖13 外場飛行試驗的信息素圖Fig.13 Pheromone map in outdoor flight verification

圖14 無人機集群協同搜索外場飛行試驗Fig.14 Outdoor flight verification of UAV swarm search

外場飛行試驗結果表明，在實際應用場景中，本文提出的基于飛蛾信息素尋偶機制的無人機集群搜索方法可以在目標搜索設備具有一定誤差的情況下快速鎖定目標的具體位置，具有一定的實用意義。

6 結論

針對可移動目標搜索問題，本文受自然界中飛蛾啟發，提出了一種基于飛蛾信息素尋偶機制的無人機集群協同搜索方法。該方法模仿雄性飛蛾在不同信息素場中的行為特點，使無人機在逆風飛行、側風飛行和與風向成一定角度飛行三種方案中進行選擇；考慮無人機集群的避撞約束，設計了異步通信條件下的分布式避撞策略。仿真實驗的結果表明了本文所提方法在對單個可移動目標搜索時的有效性和穩定性。飛行試驗的結果驗證了本文所提方法的實用性。

下一步將繼續深入研究飛蛾信息素尋偶機制，開展針對更大規模無人機集群的多移動目標搜索研究和飛行試驗。