胡中華 趙 敏 姚 敏
南京航空航天大學(xué),南京,210016
無(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]。
本文假設(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)
由于在實(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。
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)的方向搜尋航跡。
根據(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矩陣。
啟發(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ā)揮指引作用。
設(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)。
進(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ì)算。
為驗(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ì)比
本文將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.