管祥民 呂人力

(中國民航管理干部學(xué)院民航通用航空運(yùn)行重點(diǎn)實(shí)驗(yàn)室1) 北京 100102)(浙江建德通用航空研究院2) 杭州 310025)

0 引 言

人工勢(shì)場法在過去的20年間被廣泛的運(yùn)用于運(yùn)動(dòng)機(jī)器人導(dǎo)航，實(shí)時(shí)規(guī)避障礙物，其在線的避障有很強(qiáng)的魯棒性，能夠處理比較復(fù)雜的環(huán)境.然而，其運(yùn)用在飛行器沖突探測和解脫方面并沒有像機(jī)器人領(lǐng)域那么廣泛，除了機(jī)器人領(lǐng)域比較活躍以外，另外一個(gè)可能的原因是飛行器運(yùn)動(dòng)模型的限制.Tomlin等[1]將該方法沿用到?jīng)_突解脫領(lǐng)域，基本思路是建立基于勢(shì)力和渦流場(potential and vortex field methods)的運(yùn)動(dòng)規(guī)劃來產(chǎn)生沖突解脫的機(jī)動(dòng)策略.力場法用相對(duì)比較簡單的力學(xué)方程，得到連續(xù)的沖突解脫路徑，但是其隱含的一個(gè)假設(shè)是飛行器能夠隨著不斷變化的力場進(jìn)行連續(xù)的機(jī)動(dòng)，或者飛行器的速度能夠在很大的范圍內(nèi)變化，這和實(shí)際都是不符的.在轉(zhuǎn)彎角度有限制的情況下，算法產(chǎn)生極端“不實(shí)際”的解.

在基于進(jìn)化算法的沖突解脫方面，Durand等[2]利用遺產(chǎn)算法建立了一個(gè)簡單的神經(jīng)網(wǎng)絡(luò)，在解決兩機(jī)間的短期沖突能得到滿意的結(jié)果，可靠性和計(jì)算效率都比較高.解決沖突解脫的神經(jīng)網(wǎng)絡(luò)可以通過遺傳算法進(jìn)行訓(xùn)練，不必知道初始最優(yōu)解就可以得到適合的解脫路徑，將遺傳算法所得到的每一代結(jié)果代入神經(jīng)網(wǎng)絡(luò)中，使得神經(jīng)網(wǎng)絡(luò)的適應(yīng)性得到提高.但是神經(jīng)網(wǎng)絡(luò)法對(duì)多于兩架飛行器的沖突拓展十分困難.三機(jī)沖突比兩機(jī)沖突的學(xué)習(xí)適應(yīng)性差，而且在三機(jī)以上沖突的情景中，神經(jīng)網(wǎng)絡(luò)的規(guī)模呈指數(shù)級(jí)增加學(xué)習(xí)非常困難.文獻(xiàn)[3]中基于遺傳算法的沖突探測和解脫方法已經(jīng)用于NASA Langley 研究中心的試驗(yàn)項(xiàng)目Airborne User Traffic Intent Information(AUTRII)，應(yīng)用于飛行的爬升、轉(zhuǎn)彎、下降階段未來6～25 min內(nèi)沖突預(yù)測和解脫.不僅可以用于飛行器之間沖突解脫，也可以用于危險(xiǎn)區(qū)域(如SUA和雷雨云)的規(guī)避.由于在設(shè)計(jì)適應(yīng)度函數(shù)的時(shí)候靈活性比較大，可以滿足操作人員不同情況下的不同優(yōu)化目標(biāo)(最小時(shí)間延誤，或者是最小航向角的改變等等)[4-9].

基于人工勢(shì)場法等分布式方法,計(jì)算速度快，但可能會(huì)產(chǎn)生不切實(shí)際的解；基于進(jìn)化算法等集中式方法可靠性高，但是計(jì)算量大，響應(yīng)速度較慢，實(shí)時(shí)性差.本文結(jié)合人工勢(shì)場法與蟻群算法的優(yōu)點(diǎn)提出改進(jìn)混合沖突解脫方法，利用人工勢(shì)場法迅速得到近似可行的沖突解脫路徑，然后將方案調(diào)整、編碼得到“權(quán)威螞蟻”，由“權(quán)威螞蟻”衍生“權(quán)威蟻群”，利用“權(quán)威蟻群”始化信息素矩陣，基于蟻群算法，求得含有飛行規(guī)劃約束的解脫方案.并通過與傳統(tǒng)的人工勢(shì)場法與蟻群算法進(jìn)行比較，驗(yàn)證了改進(jìn)算法在時(shí)效性和可行性上的優(yōu)點(diǎn).

1 混合人工勢(shì)場與蟻群算法

1.1 利用人工勢(shì)場法得到初始路徑

將沖突解脫問題進(jìn)行巧妙的轉(zhuǎn)換，將目的地看作正電荷，所有飛機(jī)看作負(fù)電荷.這樣，異種電荷互相吸引的作用保證了每架飛機(jī)會(huì)飛往目的地，而同種電荷互相排斥的作用則保證了不會(huì)發(fā)生飛行沖突.通過合理構(gòu)造正負(fù)電荷的電場，將其化為物理學(xué)問題，對(duì)各飛機(jī)受力分析，確定運(yùn)動(dòng)軌跡,見圖1.具體來說，假設(shè)有N架飛機(jī)，第i架飛機(jī)的位置為xi=(xi,yi).

圖1 受力分析

為了確保飛機(jī)能飛往目的地，目的地xdi=(xdi,ydi)會(huì)激發(fā)引力場勢(shì)場函數(shù)

(1)

目標(biāo)點(diǎn)產(chǎn)生的引力

Fa(xi,xdi)=-Ua(xi,xdi)=-(xi-xdi)

(2)

為了避免和飛機(jī)j碰撞，飛機(jī)j會(huì)激發(fā)斥力場Ur(xi,xj),

(3)

式(3)為了保證遇到?jīng)_突時(shí)飛機(jī)都能向同一方向轉(zhuǎn)彎，引入與斥力場相切的渦旋場

(4)

將上述三個(gè)力場疊加，就可以得到多機(jī)情況下動(dòng)態(tài)的路勁規(guī)劃方程：

kviFv(xi,xj))j=1，2，…，m，i≠j

(5)

斥力和渦旋力在[0,1]間取值，其大小可控制解脫路徑的弧度.將牽引力歸一化是為了使其和斥力、渦旋力的量級(jí)一致，這樣其大小就和飛機(jī)到目的地的距離無關(guān)，僅指示去往目的地的方向.斥力系數(shù)kri、渦旋系數(shù)kvi用來控制斥力、渦旋力影響速度的權(quán)重.

圖2 人工勢(shì)場流程圖

1.2 “權(quán)威”螞蟻

勢(shì)場法每步的航向由目的地的引力和其他飛機(jī)的斥力共同決定，這就使得其航向偏轉(zhuǎn)在實(shí)數(shù)范圍內(nèi)取值；按照航向偏轉(zhuǎn)只能取0°，±30°這三個(gè)離散的值.為了使人工勢(shì)場的結(jié)果能順利編碼，有必要將人工勢(shì)場的規(guī)劃結(jié)果做適當(dāng)?shù)慕?事實(shí)上，只要確定了每架飛機(jī)解脫過程中每步的航向，解脫方案就唯一確定.如果飛機(jī)沿著之前的航向飛行與勢(shì)場法要求的航向的偏差在容許誤差(15°)內(nèi)，則沿原航向飛行，反之做相應(yīng)的調(diào)整.

近似后的航跡就可以按照之前約定的方式順利編碼，就可以得到“權(quán)威螞蟻”的覓食路徑.

1.3 “權(quán)威蟻群”

為了避免單次近似所帶來的偶然誤差，盡可能的全面地表征勢(shì)場法得到的解脫軌跡，借鑒遺傳算法基因變異的相關(guān)理論，由這只“權(quán)威螞蟻”衍生“權(quán)威蟻群”.

假設(shè)“權(quán)威螞蟻”的路徑X=(x1,x2,…，xN*K)，xi∈{-1 1 0}，X的N×K個(gè)分量亦可看作該路徑的基因.進(jìn)行變異操作，隨機(jī)選取其中若干分量，對(duì)每個(gè)分量，令其等概地向另外兩種可取值變異.然后，對(duì)變異后產(chǎn)生的新個(gè)體進(jìn)行安全性檢驗(yàn): 將變異后的x解碼，檢驗(yàn)其對(duì)應(yīng)的解脫方案是否滿足安全性要求.如果滿足安全性要求(即沒有飛行沖突)，就認(rèn)為成功衍生了另一只“權(quán)威螞蟻”.重復(fù)這樣的操作，可以得到“權(quán)威蟻群”.

1.4 初始化信息素矩陣

每一只“權(quán)威螞蟻”會(huì)根據(jù)解碼后對(duì)應(yīng)解脫方案的延誤，在其路徑上適當(dāng)分泌信息素，而使路徑上每一節(jié)點(diǎn)的信息素得到更新.更新方程為：τij(t+1)=(1-ρ)τij(t)+Q/S.

將“權(quán)威蟻群”的所有螞蟻按上述方程更新它們經(jīng)過的節(jié)點(diǎn)的信息素，就完成了初始化信息素矩陣的工作.

1.5 蟻群算法

利用蟻群算法解決沖突解脫問題，兩個(gè)難點(diǎn)：①如何將沖突解脫方案映射為螞蟻覓食路徑，即編碼問題；②定義怎樣的路徑為找到食物，即優(yōu)化目標(biāo)問題.鑒于此，下面將分三個(gè)部分闡述利用蟻群算法求解沖突解脫問題的流程.

1.5.1編碼

為了在保證精度的情況下盡快獲得計(jì)算結(jié)果，算法設(shè)定仿真步長為10 km，即每10 km更新一次航路點(diǎn)，這樣，就可以將任意一架進(jìn)入扇區(qū)的飛機(jī)的解脫過程離散化為K步.在每一步中，飛機(jī)保持一定的速度和航向，在進(jìn)入每一步之前飛機(jī)的航向能做出調(diào)整，見圖3.

考慮到民用飛機(jī)在巡航階段正常飛行，一般沒有大角度轉(zhuǎn)彎或轉(zhuǎn)向飛行.做出如下假設(shè)：飛機(jī)在解脫過程中只能選擇三個(gè)飛行方向，即保持原有航向，左轉(zhuǎn)30°，右轉(zhuǎn)30°.這種假設(shè)除了簡化搜索空間，還可以減少飛行員的反應(yīng)時(shí)間，使其更好地執(zhí)行沖突解脫方案.

綜上，假設(shè)N架飛機(jī)在解脫過程中分為K步進(jìn)行調(diào)整，將每步的調(diào)整方式用1(代表右轉(zhuǎn)30°)，-1(左轉(zhuǎn)30°)，0(保持原航向)編碼，則每一種解脫方案被編碼為一個(gè)N×K維的向量X=(x1,x2,…，xN*K)，xi∈{-1 1 0} (每k個(gè)分量對(duì)應(yīng)一架飛機(jī)的解脫軌跡).

圖3 離散化的解脫航跡

假設(shè)螞蟻要穿越一個(gè)3×NK的迷宮，從第一列運(yùn)動(dòng)到最后一列覓食，每一列有三個(gè)節(jié)點(diǎn)供螞蟻選擇.這樣，螞蟻的每一條覓食路徑就對(duì)應(yīng)上文所述的編碼向量，進(jìn)而對(duì)應(yīng)一個(gè)沖突解脫方案，至此我們完成了編碼的工作，見圖4.

圖4 編碼機(jī)制

1.5.2優(yōu)化目標(biāo)

為了保障飛行安全，任意時(shí)刻、任意兩架飛機(jī)間的距離大約最小安全間距σ(20 km).對(duì)于離散化的沖突解脫過程，需要滿足的約束條件為：|A′i-B′i|>σ，i=1,2,…,k(|A′i-B′i|表示第i步A、B兩架飛機(jī)的直線距離).

那么，當(dāng)螞蟻路徑所對(duì)應(yīng)的解脫航跡滿足上述安全性的要求時(shí)，就可以認(rèn)為該螞蟻找到了食物，從而會(huì)在該路徑上分泌一定量的信息素來引導(dǎo)后續(xù)螞蟻，否則，則認(rèn)為該路徑為無效路徑，螞蟻不會(huì)分泌信息素.

滿足安全性的條件下，為了評(píng)價(jià)不同的解脫方案，定義飛機(jī)的延誤Si.這里，假定每架飛機(jī)解脫過程飛行的距離和預(yù)設(shè)的飛行距離保持不變.具體來說，假定按照飛行計(jì)劃，A飛機(jī)由A0飛往Ak是200 km的飛行距離，那么解脫方案也只規(guī)劃200 km的飛行軌跡.為了規(guī)避沖突，A必須在飛行過程中進(jìn)行航向的調(diào)整，這樣飛行200 km后，A就不能到達(dá)Ak，而是落在了與其相近的A′k.將二者的距離定義為飛機(jī)在該種解脫方案下的延誤：Si=|A′k-Ak|.為了順利達(dá)到目的地，飛機(jī)要補(bǔ)償飛行Si，顯然，為了規(guī)避沖突而帶來的額外運(yùn)營成本、航班延誤都和Si正相關(guān)，故而可以選擇它作為評(píng)價(jià)解脫方案的指標(biāo).

定義解脫方案的延誤S為所有飛機(jī)的延誤的和，即S=∑Ni=1Si.S越小說明解脫方案越優(yōu)秀，映射到蟻群算法中，可以認(rèn)為該方案所對(duì)應(yīng)的螞蟻路徑找到了更多的食物，從而會(huì)在該路徑上分泌更多的信息素.

1.5.3迭代尋優(yōu)

模擬螞蟻?zhàn)越M織過程、程式化地迭代尋優(yōu)，如下幾個(gè)參數(shù)直接決定螞蟻路徑.

1) “迷宮”每個(gè)節(jié)點(diǎn)的信息素τijτij為第j列第i個(gè)節(jié)點(diǎn)的信息素.每當(dāng)有成功覓食的螞蟻經(jīng)過該節(jié)點(diǎn)時(shí)，螞蟻就會(huì)根據(jù)路徑譯碼后對(duì)應(yīng)的解脫方案的延誤適當(dāng)分泌信息素，而使該節(jié)點(diǎn)的信息素得到更新.更新方程為

τij(t+1)=(1-ρ)τij(t)+Q/S

(6)

式中：ρ為揮發(fā)系數(shù)，取值介于0到1，表征上一代螞蟻留下的信息素的揮發(fā)速度；S為前文定義的解脫方案的延誤.已分析過，S越小，解脫方案越優(yōu)秀，故而要求螞蟻分泌的信息素越多，二者存在負(fù)相關(guān)的關(guān)系.本文取反比來近似.Q為增益系數(shù).將螞蟻每次迭代分泌的信息素調(diào)整到合適的量級(jí).

2) 螞蟻的轉(zhuǎn)移概率PijPij為螞蟻第j步選擇第i個(gè)節(jié)點(diǎn)的概率，設(shè)定螞蟻選擇每個(gè)節(jié)點(diǎn)的概率和該節(jié)點(diǎn)信息素的強(qiáng)度成正比，就有：Pij=τij/∑3i=1τij

經(jīng)過“權(quán)威蟻群”初始化信息素后，第一代螞蟻選擇每一節(jié)點(diǎn)的概率和該節(jié)點(diǎn)信息素的強(qiáng)度成正比，即：Pij=τij/∑3i=1τij.由于“權(quán)威蟻群”根據(jù)人工勢(shì)場法得到的解脫方案調(diào)整而來，利用其初始化信息素后能引導(dǎo)大量螞蟻找到不發(fā)生沖突的安全路徑，這樣就避免了基本蟻群算法在初期沒有信息素的指引，完全隨機(jī)探測，得到大量無效路徑的問題.

如前文所述，處于無效路徑的螞蟻不會(huì)分泌信息素，只有確保飛行安全的前提下，螞蟻才會(huì)根據(jù)延誤量在各自路徑上適當(dāng)分泌信息素，以此來引導(dǎo)后續(xù)螞蟻，進(jìn)而形成信息素的正反饋來加快解的收斂.利用“權(quán)威蟻群”初始化信息素保證了蟻群初期就能迅速搜索到安全路徑，讓其快速進(jìn)入“正反饋”過程，這無疑會(huì)極大加快算法的收斂速度.

2 實(shí)驗(yàn)分析

2.1 場景描述

在經(jīng)典對(duì)飛場景下，所有的飛飛行器均勻分布在同一個(gè)圓周上，該圓的半徑為100 n mile，每架飛行器將沿著一條直線飛行.顯然，如果沒有進(jìn)行沖突解脫調(diào)控，沖突將發(fā)生在圓周的中心點(diǎn)上.雖然這種極端情況似乎不太可能在現(xiàn)實(shí)中發(fā)生，但它可以洞察在極端情況下，算法在復(fù)雜的飛行器沖突解脫場景中處理問題的性能和效率.經(jīng)典對(duì)飛場景見圖5.

圖5 經(jīng)典對(duì)飛場景示意圖

2.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)將采用四個(gè)主要指標(biāo)來評(píng)估飛行器沖突解脫方案的質(zhì)量即：沖突概率，計(jì)算時(shí)間，可行性，以及系統(tǒng)效率.

沖突概率是評(píng)價(jià)飛行器沖突解脫方案系統(tǒng)安全性的一個(gè)重要指標(biāo)，為

(7)

式中：Cj為第j個(gè)飛行器的沖突數(shù)；n為飛行器的總數(shù).

考慮到飛行器在高速飛行時(shí)需要實(shí)時(shí)解決飛行沖突，以確保飛行安全.有效縮短計(jì)算時(shí)間是不同的算法需要解決的重要問題.

引入?yún)?shù)算法的平均計(jì)算負(fù)荷，可表示為

(8)

式中：m為實(shí)驗(yàn)重復(fù)次數(shù)；Tj為第j次實(shí)驗(yàn)所需要的時(shí)間.

在某些飛行器沖突解脫方案中，有些方案的航向改變量可能太大，超出了飛行器機(jī)械性能可以實(shí)施的范圍，記為一次不可行點(diǎn).

可行性可以表示為

F=∑ni=1fi

(9)

式中：fi為第i架飛行器在飛行器沖突解脫方案不可行點(diǎn)的數(shù)量；F為用來評(píng)估一個(gè)飛行器沖突解脫方案可行性的參數(shù).

系統(tǒng)效率為

(10)

式中：Si為第i個(gè)飛行器延誤；Sdi為第i個(gè)飛行器的預(yù)設(shè)步長.顯然，當(dāng)所有的飛行器沿預(yù)定的航跡飛行時(shí)，SE=1；當(dāng)涉及的參與沖突飛行器的數(shù)量增加時(shí)，SE將會(huì)相應(yīng)減少.

2.3 經(jīng)典對(duì)飛場景下解脫方案對(duì)比

由于所有的飛行器都會(huì)在同一時(shí)間通過圓的中心，每架飛行器必須改變它的航跡，以避免沖突.

在經(jīng)典對(duì)飛場景中，改進(jìn)算法與其他方法的性能參數(shù)對(duì)比見表1.由表1可知，改進(jìn)后的算法的優(yōu)越性隨著飛行器數(shù)量的增長得到更好地體現(xiàn).盡管改進(jìn)后算法的性能參數(shù)并不是都是最好的，但他們與最好的性能差別并不是特別大.在實(shí)際情況下，改進(jìn)算法的每一個(gè)解都是可行的，符合實(shí)際工程應(yīng)用的要求，即獲得“不是最好的，但最有效的”解決方案.

表1 經(jīng)典場景下人工勢(shì)場法、蟻群算法的和改進(jìn)算法性能參數(shù)對(duì)比

注：CL-計(jì)算時(shí)間；F-可行性；SE-系統(tǒng)效率；CP-沖突概率.

在經(jīng)典對(duì)飛場景下，比較三種算法的計(jì)算時(shí)間、可行性、系統(tǒng)效率和沖突概率的對(duì)比圖見圖6.

圖6 三種算法在經(jīng)典對(duì)飛場景下的對(duì)比

由圖6a)可知，當(dāng)飛行器架數(shù)超過12架后，蟻群優(yōu)化算法的計(jì)算時(shí)間已經(jīng)超過60 s，不符合沖突解脫實(shí)時(shí)性的要求.雖然人工勢(shì)場法的計(jì)算時(shí)間略小于改進(jìn)算法，但兩者算法計(jì)算時(shí)間相差不大，都符合沖突解脫時(shí)的實(shí)時(shí)性需求.

由圖6b)可知，人工勢(shì)場法不符合可行性要求.在改進(jìn)算法中，飛行器只能選擇三個(gè)飛行方向，即保持原來的方向不變，左轉(zhuǎn)30°或右轉(zhuǎn)30°.這個(gè)假設(shè)可以保證確改進(jìn)算法得到的飛行器沖突解脫方案是可行的.此外，該假設(shè)不僅減少了搜索空間，也減少飛行員所需的反應(yīng)時(shí)間，使飛行器沖突解脫方案的更容易實(shí)施.

由圖6c)可知，改進(jìn)算法的系統(tǒng)效率明顯高于基本的蟻群優(yōu)化算法，但略低于人工勢(shì)場法.由圖6d)可知，蟻群優(yōu)化算法的沖突概率遠(yuǎn)高于人工勢(shì)場法和改進(jìn)算法.

人工勢(shì)場法在計(jì)算時(shí)間較短、系統(tǒng)效率和沖突的概率較低，但算法的可行性欠佳不能應(yīng)用于實(shí)際場景.蟻群優(yōu)化算法的性能也不理想.改進(jìn)后的算法在所有四個(gè)指標(biāo)(即計(jì)算時(shí)間、可行性、系統(tǒng)效率和沖突概率)上均符合實(shí)際場景的需求，并有著較好的速度與效率.

3 結(jié)束語

基于人工勢(shì)場法等分布式方法雖然計(jì)算速度快，但可能會(huì)產(chǎn)生不切實(shí)際的解；基于進(jìn)化算法等集中式方法可靠性高，但是計(jì)算量大，響應(yīng)速度較慢，實(shí)時(shí)性差.本文結(jié)合人工勢(shì)場法與蟻群算法的優(yōu)點(diǎn)提出改進(jìn)混合沖突解脫方法，利用人工勢(shì)場法迅速得到近似可行的沖突解脫路徑，將方案調(diào)整、編碼得到“權(quán)威螞蟻”，由“權(quán)威螞蟻”衍生“權(quán)威蟻群”，利用“權(quán)威蟻群”始化信息素矩陣，基于蟻群算法，求得含有飛行規(guī)劃約束的解脫方案.并通過與傳統(tǒng)的人工勢(shì)場法與蟻群算法進(jìn)行比較，驗(yàn)證了改進(jìn)算法在時(shí)效性和可行性上的優(yōu)點(diǎn).