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

許琴琴

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

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

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

1 傳統(tǒng)勢場法存在的問題

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

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

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

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

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

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

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

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

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

2 引入蟻群算法的優(yōu)缺點

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

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

3 組合優(yōu)化方案設(shè)計

鑒于傳統(tǒng)勢場法和蟻群算法的優(yōu)缺點，筆者考慮將兩者結(jié)合進行解脫航跡的優(yōu)化。

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

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

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

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

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

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

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

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

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

最后根據(jù)航路性能指標計算最短航路:

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

傳統(tǒng)蟻群算法在柵格化的整個劃定空域?qū)ふ易顑?yōu)路徑，對于大規(guī)模問題求解具有收斂緩慢的缺點，因此在狀態(tài)轉(zhuǎn)移時，考慮引入勢場法，根據(jù)勢場法計算的合力方向縮小蟻群算法的可選空域，從而加快收斂時間。

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

其中katt為引力增益系數(shù)。

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

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

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

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

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

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

4 仿真實現(xiàn)

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

圖1 組合優(yōu)化算法流程

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

圖2 仿真結(jié)果

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

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

表1 算法性能比較

5 結(jié)束語

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

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

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

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

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

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

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

［4］楊劍峰.蟻群算法及其應(yīng)用研究［D］.杭州:浙江大學(xué)，2007.

［5］鄧蕾蕾;張獻.改進的蟻群算法在灌區(qū)渠系優(yōu)化配水中的應(yīng)用研究［J］.安徽農(nóng)業(yè)科學(xué)，2011(31):19330－19332，19360.

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

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

［8］李明.蟻群算法在土地利用結(jié)構(gòu)優(yōu)化模型中的應(yīng)用［J］.安徽農(nóng)業(yè)科學(xué)，2011(14):8461 －8462.

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

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