引入導(dǎo)引因子蟻群算法的無人機二維航跡規(guī)劃

胡中華 趙 敏 姚 敏

南京航空航天大學，南京，210016

0 引言

無人機航跡規(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]。

1 航路規(guī)劃問題描述

1.1 規(guī)劃空間的表示

本文假設(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)

1.2 航路優(yō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。

2 航跡規(guī)劃問題的ACO算法構(gòu)造

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é)點的方向搜尋航跡。

2.1 信息素矩陣設(shè)計

根據(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矩陣。

2.2 啟發(fā)因子設(shè)計

啟發(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ā)揮指引作用。

2.3 狀態(tài)轉(zhuǎn)移策略

設(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é)點。

2.4 信息素更新策略

進化代數(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ù)或者當解的變化不明顯時便停止計算。

3 航跡規(guī)劃實例仿真

為驗證算法的性能，本文采用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é)果對比

4 結(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.