一種組合飛行器沖突解脫算法

許琴琴

(重慶大學 自動化學院，重慶 400044)

飛行器的沖突解脫是指飛行器即將遭遇障礙物威脅時，綜合考慮飛行器機動性能、威脅環境、碰撞概率、飛行時間等約束因素，尋找一條規避障礙物的最優和可行的飛行軌跡。隨著我國經濟的迅猛發展，以及 IT和電子商務的快速發展，我國的民用航空運輸業也進入了高速發展時期，航空運輸量增長迅猛。專家預測，未來中國私人飛機的市場規模將會以25%速度遞增。在我國空域有限的情況下，理想的沖突探測和解脫得顯得更加迫切。

解決飛行沖突的目的是防止航空器在空中相撞，保證飛行安全。國內外對該問題的研究大致分為幾種方法:非結構網格法、神經網絡法、遺傳算法、幾何法、矢量法、粒子群法、人工勢場法、智能解脫法等。筆者發現上述方法中人工勢能法是最直接有效的方法，但是因為勢場法的關聯參數的最佳調配方案的確定原則不夠明晰，以及勢場法應用于實際后存在的一些缺點，同時考慮到一些因為舒適和經濟等現實條件而要求的角度和速度的限制等，很多學者對該方法進行了改進。筆者考慮引入其他更成熟的思想來彌補勢場法的缺點，同時取長補短，從而更好地解決問題。蟻群算法(ACA)是近幾年提出的一種新型模擬進化算法。目前，這種方法已成功地解決了旅行商(TSP)問題、Job—shop調度問題、二次指派問題等組合優化問題，顯示出蟻群算法解決這類問題的優越性。本文通過研究相關文獻，結合我國的空域現狀以及有關管制規定，通過對勢場法的研究和改進，引入蟻群算法。兩者組合的優化算法不僅解決了勢場法的很多缺點，同時彌補了蟻群算法收斂性緩慢以及容易出現停滯現象等缺陷，具有更快發現較好解的能力。通過仿真實驗，驗證了該方法的可行性和有效性。

1 傳統勢場法存在的問題

通過研究人工勢能法，發現勢能法簡化了周圍復雜的環境條件，不用考慮飛行器的狀態，不用考慮沖突類型，只要飛行器1落于飛行器2的影響區內，即受到飛行器2勢場影響從而偏航解脫。但是在對應用背景進行深入分析后發現，引入勢場法后存在如下問題［1－3］:

1)忽略了環境因素(飛行器的機動性能、天氣因素、碰撞概率等)等對飛行器的影響。

2)零勢能域問題。當飛行器置身于零勢能域的環境中時，將不知道如何運動，陷入局部極小點。

3)目標點附近飛行器不可達問題。當飛行器向目標靠近時，距離障礙物越來越近，吸引力減小，斥力增大，飛行器受到排斥而不能達到目標，飛行器在目標前面產生擺動現象，使得飛行器無法到達目的點。

4)可能存在的角度變換過大問題。會引起飛行器內人員的不舒適感以及其他可能的安全隱患。

5)飛行器安全間隔沒有納入考慮。

6)多架飛行器同航跡沖突問題。此時勢場法產生的合力方向仍然是在原來的方向上，并未做任何改變，甚至要求飛行器向后退，而這些都是不合情理的。

7)飛行器速度和沖突類型的影響。

空域內各個飛行器速度不同，如果不加以區別，也不能很好地進行解脫。

2 引入蟻群算法的優缺點

蟻群算法是20世紀90年代發展起來一種模仿螞蟻群體行為的新的智能優化算法［4－6］。該算法引入正反饋并行機制，具有較強的魯棒性、優良的分布式計算機制、易于與其他方法結合等優點。將蟻群算法應用于空中交通沖突解脫的優點是，引入“狀態參數”表示天氣、交通復雜度等諸多不確定因素對空中交通的影響，引入代價函數描述解脫航路的性能指標，根據滿足“合理路徑”的條件規劃出包含不確定因素影響的“虛擬路徑”，并比較計算出的各種解脫路徑的“虛擬路徑”長度，從諸多“合理路徑”中優選出最佳路徑。

蟻群算法是一種確定性狀態空間搜索算法，計算開銷大、收斂速度慢一直是學者比較關注的問題［8－10］。蟻群算法受起止點位置和障礙分布的影響，環境復雜時螞蟻容易陷入不可行點，甚至出現路徑迂回和死鎖。蟻群算法容易出現停滯現象，即搜索進行到一定程度后，所有螞蟻搜索到的解完全一致，不能對空間進行進一步搜索，不利于發現更好的解。

3 組合優化方案設計

鑒于傳統勢場法和蟻群算法的優缺點，筆者考慮將兩者結合進行解脫航跡的優化。

在所定義的飛行器系統中，有m個飛行器，所研究第i個飛行器任意時刻位置矢量為Xi(xi，yi，zi)(i∈{1，2，3，…，m})，目標點為 Xo(xo，yo，zo)(o∈{1，2，3，…，m})，計劃航線為從起點到目標點的直線。其余m－1個飛行器都為第i個飛行器的潛在沖突障礙。設定第j個障礙飛行器位置矢量用 Xj(xj，yj，zj)(j∈{1，2，3，…，m －1}且 j≠i)表示，所研究飛行器跟目標點的距離為dio，所研究飛行器與潛在沖突飛行器的距離為dij，飛行器保護區半徑為rpro，影響區半徑為reffect。

劃定飛行器避障空域范圍為R×R，柵格化該范圍。在第i個飛行器的位置點放置n個螞蟻，每只螞蟻使用一定的狀態轉移規則從一個狀態轉移到另一個狀態，直到最終達到目標點，完成一條候選航路。

狀態轉移規則類同于基本蟻群算法。螞蟻在運動過程中，根據各條邊上的信息量以及路徑的啟發信息來計算狀態轉移概率。表示在t時刻螞蟻k由元素i(導航點)轉移到元素j(導航點)的狀態轉移概率。

式中:allowedk表示螞蟻下一步允許選擇的導航點;α為信息啟發因子，表示軌跡的相對重要性，反映了螞蟻在運動過程中所積累的信息在螞蟻運動過程中所起的作用，其值越大，螞蟻越傾向于選擇其他螞蟻經過的路徑，螞蟻間的協作性越強;β為期望啟發因子，表示能見度的相對重要性，反映了螞蟻在運動過程中啟發信息在螞蟻選擇路徑中的重視程度。

ηij(t)為啟發函數，考慮人們對合理航路可能考慮的幾個因素:路徑最短，代價最小，時間最小，跟計劃航線不能偏航太遠等。其表達式為

其中:φ(i)與需要考慮的幾種因素相對應;λi是上述幾個因素權衡值，可以取。希望解決與約束因素問題同時出現的路徑最優問題，但是當只出現其中1個或幾個約束時，算法仍然成立。例如當考慮路徑最短時 λ1=1，λ2=λ3=λ4=0，，此時啟發函數與傳統蟻群算法相同，式中dij表示相鄰2個導航點之間的距離。對螞蟻k而言，dij越小，則 ηij(t)越大(t)也越大，該啟發函數表示螞蟻從導航點i到導航點j的期望程度。

一旦所有螞蟻完成了各自候選航路的選擇過程，必須對各邊上的信息素做一次全面的更新，其更新規則為

螞蟻 k(k=1，2，3，…，m)在運動過程中根據各條路徑上的信息量決定其轉移方向，信息素更新規則:

式中:Wk表示螞蟻k選擇的航路的廣義代價;We代表當前最小的航路代價。信息素更新的目的是分配更多的信息素到具有更小威脅代價的航路邊上。

最后根據航路性能指標計算最短航路:

其中:l表示航路長度;W表示廣義代價函數;wt表示航路威脅代價;wf表示航路油耗代價;k表示傾向性選擇。

傳統蟻群算法在柵格化的整個劃定空域尋找最優路徑，對于大規模問題求解具有收斂緩慢的缺點，因此在狀態轉移時，考慮引入勢場法，根據勢場法計算的合力方向縮小蟻群算法的可選空域，從而加快收斂時間。

將目標視為點電荷，則飛行器Xi與目標位置Xo之間的引力場為

其中katt為引力增益系數。

定義引力為引力場的負梯度

其他的相關飛行器視為障礙物，為避免飛行器Xi和其他飛行器Xj之間的沖突，將其他飛行器也視為點電荷，由其他飛行器中飛行器Xj形成的斥力勢場函數為

其中:krep為斥力增益系數，并且分布于一定范圍;(Xi－ Xj)為飛行器 Xi到 Xj距離;rpro，reffect分別為保護區和影響區設定值。由公式可以看出，2架飛行器距離越近，特別是當Xi靠近Xj保護區邊緣時，勢場達到無限大，阻止了一個飛行器進入其他飛行器保護區的可能性。

定義斥力為斥力場的負梯度:

設合力方向與 x，y，z軸所成角度為 α、β、γ，則有

此即得到飛行器在勢場作用下到下一位置點的移動方向。應用組合優化算法的流程如圖1所示。

4 仿真實現

為驗證該方法的有效性，本文采用2機沖突解脫任務來測試算法的性能，并與傳統蟻群算法以及勢場法相比較。為了比較的公平性，本文算法和蟻群算法以及勢場法采用相同的群體規模(4架飛行器，60只螞蟻)，而且在每組測試中均迭代相同的次數。同時為了簡化沖突環境，考慮飛行器的計劃航線為直線。在每個測試實例中，以圖形化的方式給出了這3種方法生成的最優路徑以及所需時間的比較，并對解的分布性能以及散布范圍等作了比較。

圖1 組合優化算法流程

2架飛行器的起始點位置為(0，0)，(0，100)，目標分別為(100，100)，(100，0)。2架飛行器的潛在沖突點為(50，50)。考慮到飛行器的保護區范圍為20，為了有充裕的時間選擇最好的路徑以最短的時間避過撞機風險，那么2架飛行器在進入保護區之前就必須開始避障算法，因此假定2架飛行器從起始點開始引入避障算法。實驗仿真后的結果如圖2所示。

圖2 仿真結果

圖2(a)、(b)表示其中一架飛行器按照計劃路線飛行，另一架飛行器按照解脫方案進行解脫后的路線，圖2(c)表示2架飛行器同時執行解脫后的路線。實驗結果比較如表1所示。

從圖2可以看出，采用人工勢能法與蟻群算法相結合，規劃出的軌跡能夠有效地避免沖突，使飛行器安全有效地執行飛行任務。

表1 算法性能比較

5 結束語

勢能法是比較成熟的路徑規劃算法，特別在機器人領域。近些年相關研究人員考慮將其引入到飛行器沖突解脫中來。采用勢能法進行飛行器沖突解脫需要的環境信息較少，目的性比較明確，計算量少，易于實現實時控制，但是由于算法本身的缺陷，在引入實際應用的過程中出現了很多缺點，本文在前人研究的基礎上，將蟻群算法與勢場法結合，仿真表明，二者結合具有以下特點:

1)利用勢場法規劃的路徑動態約束蟻群尋址的有效范圍，可以幫助蟻群算法更好更快地收斂，彌補了傳統蟻群算法首次搜索路徑范圍過大而導致的計算量大的缺陷。

2)最優路徑的選取是眾多螞蟻的合作被搜索到的，并成為大多螞蟻所選擇的路線，這一過程具有協同性。

3)可以將飛行器飛行環境中很多不確定因素比如天氣因素、機動性能等體現在啟發因子中，更貼近實際情況。

［1］Michael A，Goodrich.Potential Fields Tutorial［Z］.［S.l.］:［s.n.］，2003.

［2］郭茜.改進人工勢場法在解決飛行沖突問題中的應用［J］.交通與計算機，2008(5):21 －25.

［3］黃興華.基于改進人工勢場法的移動機器人路徑規劃［J］.計算機應用，2010(6):45 －48.

［4］楊劍峰.蟻群算法及其應用研究［D］.杭州:浙江大學，2007.

［5］鄧蕾蕾;張獻.改進的蟻群算法在灌區渠系優化配水中的應用研究［J］.安徽農業科學，2011(31):19330－19332，19360.

［6］崔建國，鄭新起，邱楠，等.基于EMD包絡譜的飛行器健康診斷［J］.壓電與聲光，2009(6):807 －809.

［7］陶紅艷.無線傳感器網絡動態分簇路由BWAS的算法研究［J］.壓電與聲光，2011(1):155－160.

［8］李明.蟻群算法在土地利用結構優化模型中的應用［J］.安徽農業科學，2011(14):8461 －8462.

［9］侯文英，秦馳越.基于蟻群算法鮮活農產品配送路徑優化研究［J］.安徽農業科學，2009(1):109－110.

［10］王越，黃麗豐.一種基于無相交搜索策略的蟻群算法［J］.重慶理工大學學報:自然科學版，2011(4):65－69.