改進蟻群算法的多無人機沖突解脫技術研究*

揭 東 湯新民 陳濟達 李 騰

(南京航空航天大學民航學院 南京 210016)

0 引 言

無人機具有成本低、操作簡便、機動性能強等特點，在農業植保、公安警用、森林消防等多個領域得到廣泛應用[1].無人機市場規模的擴大給空域管理帶來嚴峻考驗.截至目前為止，對于無人機的運行管控策略主要是設定固定空域的方法，以避免或者嚴控其他類型的航空器進入該劃設空域中，降低安全風險.但是，由于空域資源是有限的，無人機數量陡增，因此，必須研究基于地面站的無人機沖突探測技術，給出多機沖突的解脫策略，進而保證無人機的運行安全.

國內外學者對于多無人機沖突路徑規劃問題，可細分為沖突探測與解脫路徑規劃兩部分，沖突探測方面，Reich等[2-4]從建立飛行安全間隔，以概率形式量化沖突幾率等方面開展研究；湯新民等[5-6]考慮無人機性能約束，建立機載沖突探測模型，劃分沖突告警等級；并據此給出相應解脫策略.這些研究給出了多機沖突探測的思路.對于多機解脫路徑規劃方面，目前成熟、普及度較高的算法有A*算法、人工勢場法和蟻群算法等.唐曉東等[7]假定已知無人機的目的地，引入改進open表的A*算法以降低計算復雜度，并能夠考慮無人機性能且給出解脫路徑規劃.Zhu等[8]研究了如何運用人工勢場法在動態環境中為無人機規劃沖突解脫路徑；吳學禮等[9]對于單目標單障礙物的追蹤，提出人工勢場引導進化算法.人工勢場法的優勢在于可以規劃出平滑航路，但同時容易陷入局部最優點.Dorigo[10]第一次提出了蟻群算法，通過對不同的可行路徑釋放不同量的信息素，進而控制不同路徑的信息素濃度，在最優線路中增加濃度，以逐漸搜索最優路徑.該算法擅長解決函數優化和路徑規劃問題.Sara等[11]研究了基于目標的概率和空間屬性的優化蟻群算法，有效降低了搜尋目標所需時間；Li等[12]綜合無人機性能指標，在蟻群算法的基礎上，采用人工勢場法獲取先驗值，縮短了多無人機執行任務的飛行距離；倪壯等[13]基于角度信息與精英策略改進蟻群算法，獲得了多架飛機的沖突解脫策略更優的效果.

綜上所述，目前對于多無人機路徑規劃問題，蟻群算法能夠提供路徑規劃方案，但通常只采用調向策略，沒有結合無人機靈活機動的優勢.另外，由于算法初始階段搜索量大，收斂出最優路徑的結果所需時間較長,因此，本文充分考慮無人機的性能，建立無人機飛行保護區，基于地面站對空域中飛行沖突進行探測預警.在基本蟻群算法基礎上提出加入角度信息、排序系統的改進蟻群算法，對沖突的多無人機引入聯動調速、調向策略以規劃無沖突路徑，以最小總延誤距離為目標函數，給出多機沖突情景下最優的聯動解脫策略.

1 無人機沖突探測

對基于地面站的無人機沖突探測分為三步：①為無人機設定飛行保護區，將獲取的監視數據轉換為以地面站為原點的空間坐標.②對空域中無人機按不同高度分層，對同一高度層無人機目標航跡進行分析，初篩出具有潛在沖突的目標對.③采取線性外推法對通過初篩的無人機進行具體分析計算，進一步確定沖突情況.

1.1 無人機安全間隔

對無人機建立相應的飛行保護區，以確保無人機在執行飛行任務時，有一個合理的間距，避免碰撞的風險.對于無人機的飛行保護區的構建，要依據無人機的飛行性能，包括無人機最大運行速度、執行命令做出反應的時間等；基于以上因素，飛行保護區要大于無人機自身大小.本章中保護區包含兩個要素，垂直安全間隔Dver，水平安全間隔Dhor[14].以無人機為中心的保護區模型見圖1.

圖1 無人機飛行保護區

1.2 基于線性外推法的沖突預判算法

利用WGS84坐標轉局部空間直角坐標系的方法，建立以地面基站為原點的本地直角坐標系；通過坐標轉換方法，將空域內的無人機經緯度和速度轉換為相對地面站的位置矢量和速度矢量.不同高度的無人機對應不同的二維平面.

1) 沖突初篩 對處于一個二維平面的N架無人機，對于其中的任意一架無人機，需要判斷N-1次.對于所有的無人機，理論上需要判斷N(N-1)/2次.而實際情況中，存在很多目標與自身相距很遠，在一段時間內不可能存在沖突.因此，設定距離的閾值，可以減少探測的次數，提高沖突探測的效率.

在二維平面內，設定水平距離閾值RTA，當水平間隔大于閾值.則過濾該目標.RTA設置為

RTA=2TA·νmh+Dhor

(4)

式中：TA為設定的預警時間；vmh為目標最大的水平飛行速度；Dhor為目標保護區的水平間隔.

線性外推法適用于線性運動的對象，算法基于兩機當前的位置與速度矢量，計算在預警時間[0,TA]內，兩對象之間是否有小于安全水平間隔及安全高度間隔的可能，即是否有相撞的可能.

2) 水平方向上的沖突預警探測 在水平方向上，假設判斷的兩對象分別為a，b，根據建立的局部坐標系a的水平標坐標為(vax,vay) ，水平速度為(vax,vay) ，b的水平標坐標為(vb,vb).平速度為(vbx ,vby).以下給出關于a，b在水平面內飛行相對狀態的幾個定義.

定義1a,b之間的真實距離為

(5)

定義2入侵機b相對無人機a的x軸方向速度

Δvbx=vbx-vax

(6)

定義3入侵機b相對無人機a的y軸方向速度

Δvby=vby-vay

(7)

水平方向上沖突探測步驟如下.

步驟1根據無人機速度信息，求相對速度ΔV，若|ΔV|=0，進入步驟2，若|ΔV|≠0，進入步驟3.

步驟2計算水平間隔Dab(0)與安全間隔Dhor為比較，當Dab(0)

步驟3按照水平間隔計算公式

Dab(t)=

解出Dab(0)

2 多機沖突解脫建模

2.1 基本蟻群算法應用建模

對基于地面站的多機沖突解脫規劃問題進行簡化建模：

1) 無人機具有較好的機動性能，在空中甚至可以懸停，但由于懸停過程中功耗遠遠大于工作功耗，因此假定無人機在沖突發生時，不采用懸停策略，可以采用三種調速策略，即低速、中速、高速.

2) 假定無人機在執行解脫策略時，可以采用三種調向機動策略，即保持原航向，向左偏航 30°和向右偏航30°.

3) 假定無人機都裝備ADS-B監視設備，可以獲得無人機每個時間點的位置、速度和高度信息，無人機的目標位置已知.

將n架無人機沿當前位置與其目標位置劃分成l步，往前推進過程中，無人機有三種航向策略以及三種速度策略，由假設可知，當一架無人機從t-1時刻的A位置在t時刻運動到B位置，則在t+1時刻，該無人機可能到達的位置C共有9種可能，見圖2.C1，C2，C3分別為保持高速、中速、低速左偏航 30°抵達位置，C4，C5，C6為保持高速、中速、低速沿原航向抵達的位置，C7，C8，C9為保持高速、中速、低速沿右偏航 30°所抵達的位置，9種可能路徑為BC1，BC2…，BC9.當前無人機位置、速度矢量矩陣表示為Ak[x,y,θ,v]，下一步無人機矩陣為

Ak+1=[x+vtcosθ′,y+vtsinθ′,θ′,v′]

(9)

圖2 無人機路徑選擇

基于以上三個條件假設，對空域中所有無人機進行沖突探測，當滿足沖突條件時，可以采用調節無人機航向和速度的方式改變軌跡，在解脫沖突前提下，保證偏離的距離最短.

將無人機i運行k步后的三維坐標表示為Aki；算法的目標函數為

(10)

目標函數要求f最小，也就是要沖突解脫中無人機偏離原目標的距離越短，Delayi為無人機i在此次航向改變中帶來的延誤距離，無人機產生的延誤距離可以表示為l步后位置Ali(xi,yi)與目的地坐標Bi(Xi,Yi)之間距離，表達式為

Delayi=‖Ali-Bi‖

(11)

表達式展開為

Delayi=‖Ali-Bi‖=

(12)

為使沖突解脫過程合理，在機動過程中，加入最小水平間隔約束條件，即要求每一時刻，空域中無人機兩兩之間需要保持最小水平間隔，假設無人機i(xi,yi)和j(xj,yj)為

(13)

式中：δ為無人機運行時的最小安全間隔.

針對前文的假設和定義，對空域中的n架無人機開展蟻群算法的地基沖突解脫計算.

首先計算無人機在時刻t通過某一段路徑k至另一空間位置的概率Pk(t)為

(14)

式中：τk(t)為t時刻路徑k的信息素值.該值在一次迭代完成后更新，更新的表達式為

τk(t+1)=(1-ρ)τk(t)+Δτk(t)，0<ρ<1

(15)

式中：τk(t+1)為t+1時在k段航跡上的信息素值；ρ為信息素值的衰減系數；1-ρ為信息素存留系數；Δτk(t)為此次迭代過程中該段路徑k所獲得的信息素總量.

對蟻群算法運行過程中信息素分布的問題，通常采用的模型有三種，計算表達式為

1) ant cycle system模型.

式中：Q為一只螞蟻每次循環能夠產生的信息素之和，是一個常量；Li為螞蟻i走過的總路程.

2) ant density system模型.

(17)

3) ant quantity system模型.

式中：di為螞蟻i經過該段的路程.

由表達式可知各個模型考慮的范圍不同， ant density system模型均為從螞蟻經過路程進行考慮；ant quantity system模型與ant cycle system模型分別從局部和整體考慮了螞蟻經過路程，進而分配信息素濃度，本文要從全局優化的角度考慮，得出延誤最小的路徑，因此，采用ant cycle system釋放模型，當路徑越短，每次迭代過程中獲得的信息素增量越多.

依據ant cycle system模型的計算表達式，信息素釋放量Δτk(t)表達式為

(19)

式中：Q為一架無人機走完全程留下的信息素總量；f為所有無人機最終延誤距離之和.

確定目標函數、約束條件、路徑選擇方式以及信息素釋放方法后，基本蟻群算法的運行流程見圖3.

圖3 蟻群法執行流程

2.2 改進蟻群算法應用建模

1) 角度信息的引入 無人機在某一時刻t對下一時刻目標的選擇過程中，基本蟻群算法唯一依據為下一節點信息素占所有可行節點信息素總量的比重，比重與選擇節點的幾率成正比.在此基礎上，約束無人機在選擇下一節點時考慮節點t+1與起點連線同終點與起點連線之間的夾角，增大選擇較小夾角節點的概率，見圖4.

圖4 優選夾角示意圖

S，D兩點分別為無人機起始點和目的地，無人機在時刻t有九個節點可供選擇，將可供選擇的節點與起始點連線，起始點與目標點連線，兩線構成的夾角越小，則增加其被選擇的概率，該例中，選擇節點F，構成的夾角α最小，因此在選擇下一節點過程中增大節點F被選中的概率.

2) 基于排序的螞蟻系統引入 引入基于排序的蟻群系統，每次迭代完成，對所有批次計算出的目標函數值f進行排序，f值越小，排名越靠前，僅在排序前γ的無人機經過路徑釋放信息素，在不錯過最優解的情況下，保證較優路徑有更多的信息素疊加，加快算法的收斂速度，更快得出最優解.

信息素更新公式為

τk(t+1)=(1-ρ)τk(t)+Δτ*k(t),0<ρ<1

(20)

(21)

式中：f為一批無人機最終延誤距離之和；pk為排名前k的路徑集合；Δτ*k(t)引入排序后一次迭代中無人機在路徑k上所釋放信息素之和.

引入角度信息和排序螞蟻系統后的，總結蟻群算法的運行可以分為5步：

步驟1對蟻群算法運行過程中需要用到的變量和參數賦初值，模擬無人機的數量M=N×m、各節點起始信息素φ、揮發因子ρ、最大循環迭代次數Cmax、無人機每次循環信息素釋放總和Q、迭代代數起始值k.

步驟2將M架無人機分成N組，m批次，放置在N個不同的出發點，以權值的方式，加入角度選擇的因素，結合信息素濃度，求出通向下一目標的幾率，按該幾率進行隨機選擇，引導無人機完成l步節點選擇.

步驟3按照應滿足無人機最小安全間隔約束條件式(13)，來約束每一批無人機節點的選擇，若選擇的路徑不滿足約束條件，則該批無人機重新選擇，并不再同時選該路徑組合，以保證任意時刻任意無人機，與其它無人機之間無沖突發生.

步驟4計算各無人機走完路徑后與目標點的間距，由式(10)來計算每批次無人機目標函數值f，并且對一次循環中目標函數值進行比較，得出最小目標函數值，對最小目標函數值由小到大排序，記錄排前γ的值，同時根據改進的信息素釋放表達式，更新各節點上的信息素濃度.

步驟5若循環數小于設定的最大迭代次數，回到步驟2，迭代繼續進行；否則，停止迭代，給出解脫路徑.

3 多機沖突解脫仿真

3.1 基本蟻群算法仿真

根據上述建模，設計仿真場景；設定在18 km×18 km的空域范圍中，存在如下四架無人機，分別為U1，U2，U3，U4；4架無人機的起始狀態見表1.

表1 無人機起始狀態

將無人機從起始點接近目標點的過程按距離分解為固定步數20步；無人機可以采取三種飛行速度5,10,15 m/s；圖5為無人機以當前狀態運行的路徑，因此，采用基本蟻群算法，加入排序系統的改進蟻群算法，加入排序系統、角度信息的改進蟻群算法分別進行沖突解脫仿真.仿真過程中，設置無人機總數M=80、分成4組，ρ=0.3，Q=100、最大迭代次數Cmax=200.

圖5 仿真方案設計圖

對基于地面站的多無人機沖突問題，采用基本蟻群算法仿真，算法規劃出的沖突解脫路徑見圖6.

圖6 基本蟻群算法解脫路徑規劃

由圖6可知，通過該算法，多機之間的沖突狀況得到解脫，但最終各無人機距離目標位置遠，解脫路徑規劃的質量低；產生結果的原因是，通過起始沖突路徑選擇不僅運算量大，低質量的先驗路徑結果導致基本蟻群算法最終收斂于局部最優解，而非全局最優解；因此，對算法進行改進，加入角度信息、排序系統，以減小方位的偏差，減少計算量，縮短計算時間，并驗證改進算法的效果.

3.2 改進蟻群算法仿真

保證較優路徑有更多的信息素疊加，加快算法的收斂速度，更快得出最優解.圖7為解脫路徑規劃結果，改進算法目標函數值優于基本蟻群算法，通過引入排序系統、角度信息的改進算法產生的延誤大大減小.

圖7 改進蟻群算法沖突解脫結果

在多架無人機沖突解脫過程中，無人機需要保持最小間隔，無人機解脫過程中無人機之間的實時距離見圖8，此時UAV2與UAV3在運行到第14步時距離最小為1.58 km，大于最小間隔，滿足沖突解脫過程中最小間隔要求.

圖8 無人機兩兩之間距離

對兩種算法各仿真30次，并記錄采用不同算法所產生的f值，每3次取其中最小值最終延誤長度見圖9.由圖9可知，改進蟻群算法降低了最終總延誤距離.

圖9 沖突解脫算法最終延誤距離

在仿真過程中，每種算法仿真30次，并記錄采用不同算法計算所用時間，選取其中最小的10做記錄.可見改進蟻群算法減少了計算時間.

表2 優化算法計算時間

3.3 無人機優先調配

根據無人機在空中等待的時長，與無人機運行的優先等級，確定無人機是否需要優先調配.通過增加優先調配無人機結果在最優目標中的比重，使系統保證需優先調配的無人機保持較優方案，見圖10.在仿真過程中，增加了UAV1、UAV2的優先等級，保證其優先到達目的地的情況下，對解脫路徑進行仿真，結果顯示，可以實現無人機的沖突解脫，優先保證的無人機能夠在仿真過程中得到更優的路徑規劃，在按規劃路線完成運行后距離目標點越近，而其它的無人機在與目標點距離上做出犧牲.進行多次仿真，取平均計算完成時間為28.4 s，與本文的優化算法差別不大，取平均延誤距離為13.3 km，較無優先情況增加了13%，因此可以看出此方法，能夠在犧牲少量整體優化效果的前提下有效實現優先無人機優先路徑規劃.

圖10 無人機優先調配解脫結果

4 結束語

針對空域中無人機運行可能出現的多機沖突狀況，本文提出了一種平面內線性外推的沖突探測的方法，確定可能存在的多機沖突情況，基于基本蟻群算法，加入排序系統與角度信息，考慮無人機的速度調整策略與航向調整策略，以總延誤距離最小為優化目標，規劃無人機沖突解脫的路徑.通過案例分析，可以得到，基本蟻群算法能夠為多架無人機沖突解脫提供方案，但是，總延誤距離大，計算時間長；經過本章提出的改進蟻群算法，提高了計算效率，收斂出最優化目標路徑所需時間減少了43.9%，且最終總延誤距離減少了58.4%.