胡中華 趙 敏 姚 敏

南京航空航天大學(xué)，南京，210016

0 引言

無(wú)人機(jī)航跡規(guī)劃是任務(wù)規(guī)劃中最為基礎(chǔ)，也是最重要的部分。合理的航跡規(guī)劃將有助于無(wú)人機(jī)有效地規(guī)避威脅、縮短飛行路徑長(zhǎng)度，提高其生存概率和作戰(zhàn)效率。無(wú)人機(jī)航跡規(guī)劃問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題，是優(yōu)化領(lǐng)域的重要分支，主要通過(guò)對(duì)數(shù)學(xué)方法的研究尋找離散事件的最優(yōu)編排、分組或篩選等，這類(lèi)問(wèn)題通常隨著問(wèn)題規(guī)模的擴(kuò)大，求解問(wèn)題的空間、時(shí)間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)，無(wú)法用常規(guī)的方法求解。航跡規(guī)劃算法主要可以分為兩大類(lèi)：一是傳統(tǒng)經(jīng)典算法；二是現(xiàn)代智能算法[1]。其中，前者主要包括動(dòng)態(tài)規(guī)劃法、最速下降法、最優(yōu)控制法；后者主要有VORONOI圖搜索法、格柵搜索法、人工勢(shì)場(chǎng)法、神經(jīng)網(wǎng)絡(luò)法和基于模糊邏輯的航跡規(guī)劃算法等[2]。目前最常用的方法是利用VORONOI圖構(gòu)建初始可選路徑集或設(shè)置導(dǎo)航節(jié)點(diǎn)，然后通過(guò)智能優(yōu)化算法，選擇合適的路徑，該方法存在的缺陷是導(dǎo)航節(jié)點(diǎn)位置及數(shù)量的確定往往需要進(jìn)行反復(fù)推敲，而VORONOI圖的構(gòu)建決定了航跡代價(jià)的優(yōu)化精度，因?yàn)槲浵佒荒茉赩ORONOI圖上尋找航跡，而不能在之外的空間搜索。此外，每當(dāng)威脅場(chǎng)模型發(fā)生改變時(shí)，都需重新構(gòu)建導(dǎo)航節(jié)點(diǎn)和VORONOI圖，因此對(duì)于突發(fā)的新威脅問(wèn)題，該方法適應(yīng)性不強(qiáng)。本文研究引入導(dǎo)引因子的蟻群優(yōu)化（ant colony optimization，ACO）算法，無(wú)需設(shè)置導(dǎo)航節(jié)點(diǎn)及構(gòu)建VORONOI圖，便可在自由空間自動(dòng)搜索最小代價(jià)航跡，具有較強(qiáng)的自適應(yīng)能力[3－4]。

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

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

本文假設(shè)無(wú)人機(jī)在巡航階段保持高度和速度不變，且敵方防御區(qū)處于平坦地域，因此無(wú)人機(jī)無(wú)需考慮利用地形因素進(jìn)行威脅規(guī)避機(jī)動(dòng)，航跡規(guī)劃問(wèn)題就可簡(jiǎn)化為一個(gè)二維航跡規(guī)劃問(wèn)題，但仍然需要考慮無(wú)人機(jī)在執(zhí)行作戰(zhàn)任務(wù)過(guò)程中的生存性和執(zhí)行任務(wù)的有效性，并且考慮規(guī)劃算法的實(shí)時(shí)性，所以仍是較為特殊的優(yōu)化問(wèn)題[5]。通過(guò)對(duì)規(guī)劃空間進(jìn)行直角網(wǎng)格劃分，由當(dāng)前節(jié)點(diǎn)搜尋下一個(gè)相鄰節(jié)點(diǎn)，直至搜尋到目標(biāo)節(jié)點(diǎn)，形成連接起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的航跡，采用建立在網(wǎng)格圖上的代價(jià)模型及優(yōu)化算法求解最優(yōu)路線。網(wǎng)格圖中的每個(gè)節(jié)點(diǎn)到達(dá)相鄰節(jié)點(diǎn)需要通過(guò)連接相鄰節(jié)點(diǎn)且?guī)в袡?quán)重的有向邊。因此，算法的數(shù)據(jù)結(jié)構(gòu)是以當(dāng)前節(jié)點(diǎn)為中心的九宮圖，共有8個(gè)相鄰節(jié)點(diǎn)，圖1為航跡節(jié)點(diǎn)i的數(shù)據(jù)結(jié)構(gòu)，下一個(gè)節(jié)點(diǎn)必須從以其為中心構(gòu)成8個(gè)節(jié)點(diǎn)中選擇，其中網(wǎng)格大小G需根據(jù)實(shí)際問(wèn)題規(guī)模及威脅點(diǎn)分布狀況進(jìn)行合理設(shè)置。

圖1 節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)

1.2 航路優(yōu)化指標(biāo)

由于在實(shí)際情況中常采用低于某一探測(cè)性指標(biāo)，而且具有可接受航程的航路作為任務(wù)航路，因此本文采用下式所示的代價(jià)函數(shù)來(lái)描述航路的性能指標(biāo)，它是按最短航路和最小可探測(cè)性航路加權(quán)方法來(lái)計(jì)算的[6]：

式中，W 為優(yōu)化目標(biāo)函數(shù)，可稱為廣義代價(jià)；L為航跡路徑；wt（s）為航路的威脅代價(jià)；wf（s）為航路的油耗代價(jià)；δ為系數(shù)，表示根據(jù)任務(wù)安排，航路制定人員在制定航路過(guò)程中所做出的意向性選擇。

油耗代價(jià)是航程的函數(shù)，威脅代價(jià)與無(wú)人機(jī)的可探測(cè)性指標(biāo)相關(guān)聯(lián)，而可探測(cè)性指標(biāo)是根據(jù)無(wú)人機(jī)的雷達(dá)可探測(cè)概率計(jì)算的。

本文通過(guò)對(duì)雷達(dá)威脅模型進(jìn)行簡(jiǎn)化處理，認(rèn)為敵方防御區(qū)域內(nèi)的各個(gè)雷達(dá)均相同且無(wú)相互聯(lián)系?？紤]到雷達(dá)信號(hào)正比于1／d4（d為無(wú)人機(jī)到敵方雷達(dá)、導(dǎo)彈威脅陣地的距離），故當(dāng)無(wú)人機(jī)沿網(wǎng)絡(luò)圖的第p段航跡飛行時(shí)，兩節(jié)點(diǎn)間的威脅代價(jià)可近似地認(rèn)為正比于1／d4。本文中把該條邊劃分為5段進(jìn)行計(jì)算：

式中，Lp為第p段航跡的長(zhǎng)度；B為雷達(dá)等威脅陣地的數(shù)目；dr為第p段航跡的r（r ＝ 1／10，3／10，5／10，7／10，9／10）處距第j個(gè)威脅點(diǎn)的距離。

另外，在速度一定的情況下可簡(jiǎn)單地認(rèn)為wf＝L，則有wfp＝Lp。

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

ACO算法最早用于求解旅行商問(wèn)題（travel salesman problem，TSP），將算法用于航跡規(guī)劃問(wèn)題存在一定的困難，主要表現(xiàn)在以下兩個(gè)方面：①航跡節(jié)點(diǎn)位置及數(shù)量不固定。一般的組合優(yōu)化問(wèn)題，如TSP等問(wèn)題，路徑的節(jié)點(diǎn)是固定的，因此只是幾個(gè)節(jié)點(diǎn)之間的組合實(shí)現(xiàn)優(yōu)化，所有的節(jié)點(diǎn)必須經(jīng)過(guò)且只能經(jīng)過(guò)一次，因此可以通過(guò)構(gòu)造禁忌節(jié)點(diǎn)集（已經(jīng)過(guò)的節(jié)點(diǎn)），剩下節(jié)點(diǎn)就是待選節(jié)點(diǎn)集，而航跡規(guī)劃問(wèn)題是自由搜索空間，既沒(méi)有固定節(jié)點(diǎn)位置，也沒(méi)有固定節(jié)點(diǎn)數(shù)目，空間內(nèi)不存在已知的路徑節(jié)點(diǎn)。因此，這些因素給規(guī)劃帶來(lái)了很大的難度。②如何保證到達(dá)目標(biāo)節(jié)點(diǎn)。TSP問(wèn)題將所有節(jié)點(diǎn)經(jīng)過(guò)一次后，返回到起始節(jié)點(diǎn)，因此，目標(biāo)節(jié)點(diǎn)就是起始節(jié)點(diǎn)，而航跡規(guī)劃問(wèn)題的目標(biāo)節(jié)點(diǎn)與起始節(jié)點(diǎn)不同，由于ACO按信息素及啟發(fā)因子構(gòu)造狀態(tài)轉(zhuǎn)移策略，根據(jù)概率進(jìn)行局部搜索，能見(jiàn)度限于局部范圍內(nèi)，因此，如何保證找到目標(biāo)節(jié)點(diǎn)，是完成航跡規(guī)劃的關(guān)鍵問(wèn)題。

本文通過(guò)合理構(gòu)造ACO算法，解決了以上兩個(gè)問(wèn)題。

（1）設(shè)定航跡節(jié)點(diǎn)數(shù)最大允許限度。無(wú)人機(jī)存在最大航程參數(shù)，即無(wú)人機(jī)在整個(gè)飛行過(guò)程中的飛行路程，受到飛機(jī)燃油和飛行時(shí)間配給的限制。記最大航跡長(zhǎng)度為L(zhǎng)max，則每一個(gè)航段距離Lp應(yīng)滿足：

根據(jù)式（3）可知，航跡節(jié)點(diǎn)數(shù)不能超過(guò)某范圍，這是無(wú)人機(jī)自身?xiàng)l件限制的。此外，由式（1）可知，航跡代價(jià)包含了油耗代價(jià)，油耗代價(jià)大的航跡可能會(huì)導(dǎo)致航跡代價(jià)增大。油耗代價(jià)也必須滿足一定的范圍，超過(guò)這個(gè)范圍認(rèn)為是不可接受的。因此，盡管航跡節(jié)點(diǎn)不固定，但可設(shè)定最大節(jié)點(diǎn)數(shù)，當(dāng)超過(guò)最大節(jié)點(diǎn)數(shù)時(shí)，即認(rèn)為該航跡不可行，則放棄。

（2）引入導(dǎo)引因子。常規(guī)蟻群算法的狀態(tài)轉(zhuǎn)移策略根據(jù)信息素及啟發(fā)因子按概率選擇，沒(méi)有導(dǎo)引因子，本文根據(jù)航跡規(guī)劃問(wèn)題的需要，引入了目標(biāo)節(jié)點(diǎn)信息素導(dǎo)引因子，以節(jié)點(diǎn)i為例，設(shè)節(jié)點(diǎn)i到目標(biāo)節(jié)點(diǎn)D 的距離為diD，則導(dǎo)引因子λi＝1／diD。常規(guī)狀態(tài)轉(zhuǎn)移策略中，九宮圖中8個(gè)相鄰節(jié)點(diǎn)的啟發(fā)因子數(shù)值相差不大，因此目標(biāo)節(jié)點(diǎn)的局部預(yù)見(jiàn)性不強(qiáng)，尤其在算法迭代初期，節(jié)點(diǎn)間的信息素相差無(wú)幾，狀態(tài)轉(zhuǎn)移容易陷入盲目選擇，難以快速到達(dá)目標(biāo)節(jié)點(diǎn)。由λi＝1／diD可知，離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)的節(jié)點(diǎn)，導(dǎo)引因子越大；反之，導(dǎo)引因子越小。因此狀態(tài)轉(zhuǎn)移策略中，導(dǎo)引因子的引入，可以有效減小螞蟻搜索的盲目性，使螞蟻朝著目標(biāo)節(jié)點(diǎn)的方向搜尋航跡。

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

根據(jù)劃分的網(wǎng)格大小及起始點(diǎn)、目標(biāo)點(diǎn)及威脅點(diǎn)的位置來(lái)確定規(guī)劃空間，設(shè)該空間4個(gè)點(diǎn)坐標(biāo) 分 別 為 （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é)點(diǎn)數(shù)，n＝hnvn，坐標(biāo)為（xi，yi）的網(wǎng)格節(jié)點(diǎn)編號(hào)pi的計(jì)算公式為

由式（4）建立信息素矩陣τ，τ為n×n矩陣。

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

啟發(fā)因子主要是用來(lái)提高節(jié)點(diǎn)選擇的能見(jiàn)度，加快算法的收斂速度，使算法快速收斂于最小代價(jià)的航跡。本研究的代價(jià)主要來(lái)源于威脅代價(jià)，因此啟發(fā)因子設(shè)計(jì)為威脅代價(jià)點(diǎn)的倒數(shù)。

設(shè)共有B個(gè)威脅點(diǎn)，第j個(gè)威脅點(diǎn)坐標(biāo)為（xj，yj），則節(jié)點(diǎn)i到威脅點(diǎn)j的威脅代價(jià)表示為

根據(jù)式（5）求出節(jié)點(diǎn)i到所有威脅點(diǎn)的代價(jià)為

節(jié)點(diǎn)的啟發(fā)因子等于總威脅代價(jià)的倒數(shù)，即ηi＝1／εi，因此當(dāng)節(jié)點(diǎn)威脅代價(jià)小時(shí)，啟發(fā)因子大，能見(jiàn)度高；反之，則能見(jiàn)度低。啟發(fā)因子起到加速算法收斂的作用，但相對(duì)于信息素，所占比重不宜過(guò)大，否則信息素?zé)o法發(fā)揮指引作用。

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

設(shè)蟻群規(guī)模為m，τij（N）表示迭代N次時(shí)在節(jié)點(diǎn)i到j(luò)段航跡的信息素濃度。初始迭代時(shí)，各條路徑上信息素的濃度相同，設(shè)τij（0）＝h（h為常數(shù)）。螞蟻k（k＝1，2，…，m）在運(yùn)動(dòng)過(guò)程中，根據(jù)各條路徑上的信息素濃度決定轉(zhuǎn)移方向，（N）表示第N代螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率，其計(jì)算公式如下：

其中，Tk用以記錄螞蟻k本代所走過(guò)的節(jié)點(diǎn)，Tk隨螞蟻不斷選擇下一個(gè)節(jié)點(diǎn)而做動(dòng)態(tài)調(diào)整表示所有未經(jīng)過(guò)的節(jié)點(diǎn)，Bi表示節(jié)點(diǎn)i的相鄰節(jié)點(diǎn)集，Ak表示螞蟻k下一步待選的節(jié)點(diǎn)集，與一般TSP問(wèn)題不同，待選節(jié)點(diǎn)不是剩余未經(jīng)過(guò)的全部節(jié)點(diǎn)k，而是由九宮圖中相鄰的節(jié)點(diǎn)組成的節(jié)點(diǎn)集（圖1），并排除已經(jīng)經(jīng)過(guò)的節(jié)點(diǎn)，螞蟻不斷在局部范圍內(nèi)搜索節(jié)點(diǎn)，最終到達(dá)目標(biāo)節(jié)點(diǎn)，完成一次航跡。而為了保證螞蟻能最終達(dá)到目標(biāo)節(jié)點(diǎn)，與一般ACO算法不同，本研究的狀態(tài)轉(zhuǎn)移概率引入了導(dǎo)引因子λi（N），使螞蟻搜索具有一定的方向性，即使螞蟻朝著目標(biāo)節(jié)點(diǎn)的方向搜尋航跡，式中α、β、γ分別表示信息素、啟發(fā)因子及導(dǎo)引因子重要性程度參數(shù)，仿真實(shí)踐表明β及γ取值不宜過(guò)大，否則算法容易陷入停滯。此外，對(duì)于Ak中存在的離威脅點(diǎn)太近的節(jié)點(diǎn)，通過(guò)設(shè)置啟發(fā)因子臨界值R來(lái)實(shí)現(xiàn)不選擇該節(jié)點(diǎn)的目的，當(dāng)某節(jié)點(diǎn)j啟發(fā)因子ηj小于R時(shí)，令ηj為無(wú)窮小。那么選擇無(wú)窮小節(jié)點(diǎn)的概率幾乎為0，從而達(dá)到排除選擇該節(jié)點(diǎn)的目的，由此保證算法不會(huì)出現(xiàn)經(jīng)過(guò)威脅節(jié)點(diǎn)。

2.4 信息素更新策略

進(jìn)化代數(shù)N每增加一次，各條路徑上的信息素就要揮發(fā)一次，用參數(shù)（1－ρ）表示信息素的揮發(fā)程度，所有螞蟻完成一次迭代循環(huán)，各航跡段上信息素的濃度根據(jù)式（8）和式（9）作調(diào)整。

其中，Δτij（N）b表示第N次迭代中最小代價(jià)的螞蟻所對(duì)應(yīng)的航跡，區(qū)別一般算法對(duì)所有螞蟻行走的航跡進(jìn)行信息素增強(qiáng)，本文僅考慮最小代價(jià)航跡的信息素增強(qiáng)，以便加快算法的收斂，但為防止某些邊上的信息素增長(zhǎng)過(guò)快，把信息素大小的取值范圍限制在一個(gè)區(qū)間[τmin，τmax]內(nèi)，以避免算法陷入停滯。

其中，Q為常數(shù)，表示信息素增加強(qiáng)度系數(shù)；WbN表示第N次迭代中最小航跡代價(jià)。Q、ρ根據(jù)求解規(guī)模確定其取值。固定迭代次數(shù)或者當(dāng)解的變化不明顯時(shí)便停止計(jì)算。

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

為驗(yàn)證算法的性能，本文采用MATLAB進(jìn)行編程仿真。將航跡分成兩部分，設(shè)置一個(gè)中間過(guò)渡節(jié)點(diǎn)T（10，20），起始節(jié)點(diǎn)S到節(jié)點(diǎn)T時(shí)刻航跡為固定航跡，這是因?yàn)榇硕魏桔E離威脅點(diǎn)有較長(zhǎng)距離，威脅代價(jià)小，幾乎可以忽略，而節(jié)點(diǎn)T到目標(biāo)節(jié)點(diǎn)D時(shí)威脅代價(jià)大，因此對(duì)此部分作航跡優(yōu)化，參數(shù)見(jiàn)表1。

表1 威脅點(diǎn)、起始點(diǎn)及目標(biāo)點(diǎn)坐標(biāo)

算法仿真參數(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可以保證無(wú)人機(jī)航程油耗基本在允許范圍內(nèi)。圖2分別為δ＝1.0、δ＝0.9、δ＝0.5時(shí)的最優(yōu)航跡，從圖2可以看出，最小代價(jià)航跡隨著迭代的進(jìn)行不斷地進(jìn)行著調(diào)整，并最終獲得全局最小代價(jià)航跡。本文ACO算法結(jié)果如表2所示，在權(quán)值系數(shù)δ取不同值的情況下，本文算法均取得較好的結(jié)果。

圖2 不同權(quán)重系數(shù)下的最佳航跡

表2 算法結(jié)果對(duì)比

4 結(jié)語(yǔ)

本文將ACO算法應(yīng)用于無(wú)人機(jī)航跡規(guī)劃問(wèn)題，通過(guò)解決兩大構(gòu)造難題，并將導(dǎo)引因子引入到狀態(tài)轉(zhuǎn)移策略當(dāng)中，保證了算法的收斂速度，同時(shí)確保螞蟻?zhàn)罱K完成航跡搜索，通過(guò)設(shè)置當(dāng)前最優(yōu)路徑信息素更新策略，同時(shí)設(shè)置信息素上下限，在提高算法速度的同時(shí)，防止算法陷入局部最優(yōu)及出現(xiàn)停滯。仿真結(jié)果表明，該算法的構(gòu)造非常合理，在沒(méi)有設(shè)置導(dǎo)航節(jié)點(diǎn)及構(gòu)建VORONOI圖的情況下，螞蟻在自由空間自動(dòng)尋找到目標(biāo)節(jié)點(diǎn)，且收斂速度快，克服了傳統(tǒng)ACO算法航跡規(guī)劃需要預(yù)先設(shè)置導(dǎo)航節(jié)點(diǎn)及構(gòu)建VORONOI圖的缺點(diǎn)，在航跡規(guī)劃問(wèn)題領(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].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2005，33（5）：42－45.

[3]高暉，陳欣，夏云程.無(wú)人機(jī)航路規(guī)劃研究[J].南京航空航天大學(xué)學(xué)報(bào)，2001，33（2）：135－138.

[4]劉森琪，段海濱，余亞翔.基于Voronoi圖和蟻群優(yōu)化算法的無(wú)人作戰(zhàn)飛機(jī)航路規(guī)劃[J].系統(tǒng)仿真學(xué)報(bào)，2008，20（21）：5936－5939.

[5]陳美軍，張志勝，史金飛.多約束下多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題的蟻群算法研究[J].中國(guó)機(jī)械工程，2008，19（16）：1939－1944.

[6]陳謀，肖健，姜長(zhǎng)生.基于改進(jìn)蟻群算法的無(wú)人機(jī)三維航路規(guī)劃[J].吉林大學(xué)學(xué)報(bào)（工學(xué)版），2008，38（4）：991－995.