許琴琴

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

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

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

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

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

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

2)零勢(shì)能域問題。當(dāng)飛行器置身于零勢(shì)能域的環(huán)境中時(shí)，將不知道如何運(yùn)動(dòng)，陷入局部極小點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將目標(biāo)視為點(diǎn)電荷，則飛行器Xi與目標(biāo)位置Xo之間的引力場(chǎng)為

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

定義引力為引力場(chǎng)的負(fù)梯度

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

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

定義斥力為斥力場(chǎng)的負(fù)梯度:

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

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

4 仿真實(shí)現(xiàn)

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

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

2架飛行器的起始點(diǎn)位置為(0，0)，(0，100)，目標(biāo)分別為(100，100)，(100，0)。2架飛行器的潛在沖突點(diǎn)為(50，50)?？紤]到飛行器的保護(hù)區(qū)范圍為20，為了有充裕的時(shí)間選擇最好的路徑以最短的時(shí)間避過撞機(jī)風(fēng)險(xiǎn)，那么2架飛行器在進(jìn)入保護(hù)區(qū)之前就必須開始避障算法，因此假定2架飛行器從起始點(diǎn)開始引入避障算法。實(shí)驗(yàn)仿真后的結(jié)果如圖2所示。

圖2 仿真結(jié)果

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

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

表1 算法性能比較

5 結(jié)束語

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

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

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

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

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

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

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

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

［5］鄧?yán)倮?張獻(xiàn).改進(jìn)的蟻群算法在灌區(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ò)動(dòng)態(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é)報(bào):自然科學(xué)版，2011(4):65－69.