胡中華 趙 敏 姚 敏
南京航空航天大學,南京,210016
無人機航跡規(guī)劃是任務(wù)規(guī)劃中最為基礎(chǔ),也是最重要的部分。合理的航跡規(guī)劃將有助于無人機有效地規(guī)避威脅、縮短飛行路徑長度,提高其生存概率和作戰(zhàn)效率。無人機航跡規(guī)劃問題是一個組合優(yōu)化問題,是優(yōu)化領(lǐng)域的重要分支,主要通過對數(shù)學方法的研究尋找離散事件的最優(yōu)編排、分組或篩選等,這類問題通常隨著問題規(guī)模的擴大,求解問題的空間、時間復(fù)雜度呈指數(shù)級增長,無法用常規(guī)的方法求解。航跡規(guī)劃算法主要可以分為兩大類:一是傳統(tǒng)經(jīng)典算法;二是現(xiàn)代智能算法[1]。其中,前者主要包括動態(tài)規(guī)劃法、最速下降法、最優(yōu)控制法;后者主要有VORONOI圖搜索法、格柵搜索法、人工勢場法、神經(jīng)網(wǎng)絡(luò)法和基于模糊邏輯的航跡規(guī)劃算法等[2]。目前最常用的方法是利用VORONOI圖構(gòu)建初始可選路徑集或設(shè)置導(dǎo)航節(jié)點,然后通過智能優(yōu)化算法,選擇合適的路徑,該方法存在的缺陷是導(dǎo)航節(jié)點位置及數(shù)量的確定往往需要進行反復(fù)推敲,而VORONOI圖的構(gòu)建決定了航跡代價的優(yōu)化精度,因為螞蟻只能在VORONOI圖上尋找航跡,而不能在之外的空間搜索。此外,每當威脅場模型發(fā)生改變時,都需重新構(gòu)建導(dǎo)航節(jié)點和VORONOI圖,因此對于突發(fā)的新威脅問題,該方法適應(yīng)性不強。本文研究引入導(dǎo)引因子的蟻群優(yōu)化(ant colony optimization,ACO)算法,無需設(shè)置導(dǎo)航節(jié)點及構(gòu)建VORONOI圖,便可在自由空間自動搜索最小代價航跡,具有較強的自適應(yīng)能力[3-4]。
本文假設(shè)無人機在巡航階段保持高度和速度不變,且敵方防御區(qū)處于平坦地域,因此無人機無需考慮利用地形因素進行威脅規(guī)避機動,航跡規(guī)劃問題就可簡化為一個二維航跡規(guī)劃問題,但仍然需要考慮無人機在執(zhí)行作戰(zhàn)任務(wù)過程中的生存性和執(zhí)行任務(wù)的有效性,并且考慮規(guī)劃算法的實時性,所以仍是較為特殊的優(yōu)化問題[5]。通過對規(guī)劃空間進行直角網(wǎng)格劃分,由當前節(jié)點搜尋下一個相鄰節(jié)點,直至搜尋到目標節(jié)點,形成連接起始節(jié)點和目標節(jié)點的航跡,采用建立在網(wǎng)格圖上的代價模型及優(yōu)化算法求解最優(yōu)路線。網(wǎng)格圖中的每個節(jié)點到達相鄰節(jié)點需要通過連接相鄰節(jié)點且?guī)в袡?quán)重的有向邊。因此,算法的數(shù)據(jù)結(jié)構(gòu)是以當前節(jié)點為中心的九宮圖,共有8個相鄰節(jié)點,圖1為航跡節(jié)點i的數(shù)據(jù)結(jié)構(gòu),下一個節(jié)點必須從以其為中心構(gòu)成8個節(jié)點中選擇,其中網(wǎng)格大小G需根據(jù)實際問題規(guī)模及威脅點分布狀況進行合理設(shè)置。
圖1 節(jié)點的網(wǎng)絡(luò)結(jié)構(gòu)
由于在實際情況中常采用低于某一探測性指標,而且具有可接受航程的航路作為任務(wù)航路,因此本文采用下式所示的代價函數(shù)來描述航路的性能指標,它是按最短航路和最小可探測性航路加權(quán)方法來計算的[6]:
式中,W 為優(yōu)化目標函數(shù),可稱為廣義代價;L為航跡路徑;wt(s)為航路的威脅代價;wf(s)為航路的油耗代價;δ為系數(shù),表示根據(jù)任務(wù)安排,航路制定人員在制定航路過程中所做出的意向性選擇。
油耗代價是航程的函數(shù),威脅代價與無人機的可探測性指標相關(guān)聯(lián),而可探測性指標是根據(jù)無人機的雷達可探測概率計算的。
本文通過對雷達威脅模型進行簡化處理,認為敵方防御區(qū)域內(nèi)的各個雷達均相同且無相互聯(lián)系??紤]到雷達信號正比于1/d4(d為無人機到敵方雷達、導(dǎo)彈威脅陣地的距離),故當無人機沿網(wǎng)絡(luò)圖的第p段航跡飛行時,兩節(jié)點間的威脅代價可近似地認為正比于1/d4。本文中把該條邊劃分為5段進行計算:
式中,Lp為第p段航跡的長度;B為雷達等威脅陣地的數(shù)目;dr為第p段航跡的r(r = 1/10,3/10,5/10,7/10,9/10)處距第j個威脅點的距離。
另外,在速度一定的情況下可簡單地認為wf=L,則有wfp=Lp。
ACO算法最早用于求解旅行商問題(travel salesman problem,TSP),將算法用于航跡規(guī)劃問題存在一定的困難,主要表現(xiàn)在以下兩個方面:①航跡節(jié)點位置及數(shù)量不固定。一般的組合優(yōu)化問題,如TSP等問題,路徑的節(jié)點是固定的,因此只是幾個節(jié)點之間的組合實現(xiàn)優(yōu)化,所有的節(jié)點必須經(jīng)過且只能經(jīng)過一次,因此可以通過構(gòu)造禁忌節(jié)點集(已經(jīng)過的節(jié)點),剩下節(jié)點就是待選節(jié)點集,而航跡規(guī)劃問題是自由搜索空間,既沒有固定節(jié)點位置,也沒有固定節(jié)點數(shù)目,空間內(nèi)不存在已知的路徑節(jié)點。因此,這些因素給規(guī)劃帶來了很大的難度。②如何保證到達目標節(jié)點。TSP問題將所有節(jié)點經(jīng)過一次后,返回到起始節(jié)點,因此,目標節(jié)點就是起始節(jié)點,而航跡規(guī)劃問題的目標節(jié)點與起始節(jié)點不同,由于ACO按信息素及啟發(fā)因子構(gòu)造狀態(tài)轉(zhuǎn)移策略,根據(jù)概率進行局部搜索,能見度限于局部范圍內(nèi),因此,如何保證找到目標節(jié)點,是完成航跡規(guī)劃的關(guān)鍵問題。
本文通過合理構(gòu)造ACO算法,解決了以上兩個問題。
(1)設(shè)定航跡節(jié)點數(shù)最大允許限度。無人機存在最大航程參數(shù),即無人機在整個飛行過程中的飛行路程,受到飛機燃油和飛行時間配給的限制。記最大航跡長度為Lmax,則每一個航段距離Lp應(yīng)滿足:
根據(jù)式(3)可知,航跡節(jié)點數(shù)不能超過某范圍,這是無人機自身條件限制的。此外,由式(1)可知,航跡代價包含了油耗代價,油耗代價大的航跡可能會導(dǎo)致航跡代價增大。油耗代價也必須滿足一定的范圍,超過這個范圍認為是不可接受的。因此,盡管航跡節(jié)點不固定,但可設(shè)定最大節(jié)點數(shù),當超過最大節(jié)點數(shù)時,即認為該航跡不可行,則放棄。
(2)引入導(dǎo)引因子。常規(guī)蟻群算法的狀態(tài)轉(zhuǎn)移策略根據(jù)信息素及啟發(fā)因子按概率選擇,沒有導(dǎo)引因子,本文根據(jù)航跡規(guī)劃問題的需要,引入了目標節(jié)點信息素導(dǎo)引因子,以節(jié)點i為例,設(shè)節(jié)點i到目標節(jié)點D 的距離為diD,則導(dǎo)引因子λi=1/diD。常規(guī)狀態(tài)轉(zhuǎn)移策略中,九宮圖中8個相鄰節(jié)點的啟發(fā)因子數(shù)值相差不大,因此目標節(jié)點的局部預(yù)見性不強,尤其在算法迭代初期,節(jié)點間的信息素相差無幾,狀態(tài)轉(zhuǎn)移容易陷入盲目選擇,難以快速到達目標節(jié)點。由λi=1/diD可知,離目標節(jié)點越遠的節(jié)點,導(dǎo)引因子越大;反之,導(dǎo)引因子越小。因此狀態(tài)轉(zhuǎn)移策略中,導(dǎo)引因子的引入,可以有效減小螞蟻搜索的盲目性,使螞蟻朝著目標節(jié)點的方向搜尋航跡。
根據(jù)劃分的網(wǎng)格大小及起始點、目標點及威脅點的位置來確定規(guī)劃空間,設(shè)該空間4個點坐標 分 別 為 (xmin,ymin)、(xmax,ymin)、(xmin,ymax)、(xmax,ymax),設(shè)網(wǎng)格大小為G,則網(wǎng)格共有行數(shù)hn= (ymax-ymin)/G,共 有 列 數(shù) vn= (ymax-ymin)/G,其中,n為節(jié)點數(shù),n=hnvn,坐標為(xi,yi)的網(wǎng)格節(jié)點編號pi的計算公式為
由式(4)建立信息素矩陣τ,τ為n×n矩陣。
啟發(fā)因子主要是用來提高節(jié)點選擇的能見度,加快算法的收斂速度,使算法快速收斂于最小代價的航跡。本研究的代價主要來源于威脅代價,因此啟發(fā)因子設(shè)計為威脅代價點的倒數(shù)。
設(shè)共有B個威脅點,第j個威脅點坐標為(xj,yj),則節(jié)點i到威脅點j的威脅代價表示為
根據(jù)式(5)求出節(jié)點i到所有威脅點的代價為
節(jié)點的啟發(fā)因子等于總威脅代價的倒數(shù),即ηi=1/εi,因此當節(jié)點威脅代價小時,啟發(fā)因子大,能見度高;反之,則能見度低。啟發(fā)因子起到加速算法收斂的作用,但相對于信息素,所占比重不宜過大,否則信息素無法發(fā)揮指引作用。
設(shè)蟻群規(guī)模為m,τij(N)表示迭代N次時在節(jié)點i到j(luò)段航跡的信息素濃度。初始迭代時,各條路徑上信息素的濃度相同,設(shè)τij(0)=h(h為常數(shù))。螞蟻k(k=1,2,…,m)在運動過程中,根據(jù)各條路徑上的信息素濃度決定轉(zhuǎn)移方向,(N)表示第N代螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的概率,其計算公式如下:
其中,Tk用以記錄螞蟻k本代所走過的節(jié)點,Tk隨螞蟻不斷選擇下一個節(jié)點而做動態(tài)調(diào)整表示所有未經(jīng)過的節(jié)點,Bi表示節(jié)點i的相鄰節(jié)點集,Ak表示螞蟻k下一步待選的節(jié)點集,與一般TSP問題不同,待選節(jié)點不是剩余未經(jīng)過的全部節(jié)點k,而是由九宮圖中相鄰的節(jié)點組成的節(jié)點集(圖1),并排除已經(jīng)經(jīng)過的節(jié)點,螞蟻不斷在局部范圍內(nèi)搜索節(jié)點,最終到達目標節(jié)點,完成一次航跡。而為了保證螞蟻能最終達到目標節(jié)點,與一般ACO算法不同,本研究的狀態(tài)轉(zhuǎn)移概率引入了導(dǎo)引因子λi(N),使螞蟻搜索具有一定的方向性,即使螞蟻朝著目標節(jié)點的方向搜尋航跡,式中α、β、γ分別表示信息素、啟發(fā)因子及導(dǎo)引因子重要性程度參數(shù),仿真實踐表明β及γ取值不宜過大,否則算法容易陷入停滯。此外,對于Ak中存在的離威脅點太近的節(jié)點,通過設(shè)置啟發(fā)因子臨界值R來實現(xiàn)不選擇該節(jié)點的目的,當某節(jié)點j啟發(fā)因子ηj小于R時,令ηj為無窮小。那么選擇無窮小節(jié)點的概率幾乎為0,從而達到排除選擇該節(jié)點的目的,由此保證算法不會出現(xiàn)經(jīng)過威脅節(jié)點。
進化代數(shù)N每增加一次,各條路徑上的信息素就要揮發(fā)一次,用參數(shù)(1-ρ)表示信息素的揮發(fā)程度,所有螞蟻完成一次迭代循環(huán),各航跡段上信息素的濃度根據(jù)式(8)和式(9)作調(diào)整。
其中,Δτij(N)b表示第N次迭代中最小代價的螞蟻所對應(yīng)的航跡,區(qū)別一般算法對所有螞蟻行走的航跡進行信息素增強,本文僅考慮最小代價航跡的信息素增強,以便加快算法的收斂,但為防止某些邊上的信息素增長過快,把信息素大小的取值范圍限制在一個區(qū)間[τmin,τmax]內(nèi),以避免算法陷入停滯。
其中,Q為常數(shù),表示信息素增加強度系數(shù);WbN表示第N次迭代中最小航跡代價。Q、ρ根據(jù)求解規(guī)模確定其取值。固定迭代次數(shù)或者當解的變化不明顯時便停止計算。
為驗證算法的性能,本文采用MATLAB進行編程仿真。將航跡分成兩部分,設(shè)置一個中間過渡節(jié)點T(10,20),起始節(jié)點S到節(jié)點T時刻航跡為固定航跡,這是因為此段航跡離威脅點有較長距離,威脅代價小,幾乎可以忽略,而節(jié)點T到目標節(jié)點D時威脅代價大,因此對此部分作航跡優(yōu)化,參數(shù)見表1。
表1 威脅點、起始點及目標點坐標
算法仿真參數(shù)設(shè)置為Nmax=100、m=31、α=1、β=0.25、γ=0.5、ρ=0.1、Q=50、R=4、G=2、Lmax=30。參數(shù)Nmax表示最大迭代次數(shù),Lmax可以保證無人機航程油耗基本在允許范圍內(nèi)。圖2分別為δ=1.0、δ=0.9、δ=0.5時的最優(yōu)航跡,從圖2可以看出,最小代價航跡隨著迭代的進行不斷地進行著調(diào)整,并最終獲得全局最小代價航跡。本文ACO算法結(jié)果如表2所示,在權(quán)值系數(shù)δ取不同值的情況下,本文算法均取得較好的結(jié)果。
圖2 不同權(quán)重系數(shù)下的最佳航跡
表2 算法結(jié)果對比
本文將ACO算法應(yīng)用于無人機航跡規(guī)劃問題,通過解決兩大構(gòu)造難題,并將導(dǎo)引因子引入到狀態(tài)轉(zhuǎn)移策略當中,保證了算法的收斂速度,同時確保螞蟻最終完成航跡搜索,通過設(shè)置當前最優(yōu)路徑信息素更新策略,同時設(shè)置信息素上下限,在提高算法速度的同時,防止算法陷入局部最優(yōu)及出現(xiàn)停滯。仿真結(jié)果表明,該算法的構(gòu)造非常合理,在沒有設(shè)置導(dǎo)航節(jié)點及構(gòu)建VORONOI圖的情況下,螞蟻在自由空間自動尋找到目標節(jié)點,且收斂速度快,克服了傳統(tǒng)ACO算法航跡規(guī)劃需要預(yù)先設(shè)置導(dǎo)航節(jié)點及構(gòu)建VORONOI圖的缺點,在航跡規(guī)劃問題領(lǐng)域具有令人鼓舞的應(yīng)用前景。
[1]Eun Y,Bang H.Cooperative Task Assignment/Track Planning of Multiple Unmanned Aerial Vehicles Using Genetic Algorithms[J].Journal of Aircraft,2009,46(1):338-343.
[2]周成平,陳前洋,秦筱.基于稀疏A*算法的三維航跡并行規(guī)劃算法[J].華中科技大學學報(自然科學版),2005,33(5):42-45.
[3]高暉,陳欣,夏云程.無人機航路規(guī)劃研究[J].南京航空航天大學學報,2001,33(2):135-138.
[4]劉森琪,段海濱,余亞翔.基于Voronoi圖和蟻群優(yōu)化算法的無人作戰(zhàn)飛機航路規(guī)劃[J].系統(tǒng)仿真學報,2008,20(21):5936-5939.
[5]陳美軍,張志勝,史金飛.多約束下多車場車輛路徑問題的蟻群算法研究[J].中國機械工程,2008,19(16):1939-1944.
[6]陳謀,肖健,姜長生.基于改進蟻群算法的無人機三維航路規(guī)劃[J].吉林大學學報(工學版),2008,38(4):991-995.