唐必偉，方 群

（西北工業(yè)大學(xué) 航天學(xué)院，陜西 西安 710072）

航跡規(guī)劃是指在特定約束條件下尋找運(yùn)動(dòng)體從起始點(diǎn)到終點(diǎn)滿足某項(xiàng)性能指標(biāo)最優(yōu)的運(yùn)動(dòng)軌跡[1]?；鞠伻核惴軌蛘业斤w行航跡的可行解，并且具有較好的魯棒性，但容易陷入局部最優(yōu)，并且求解時(shí)消耗時(shí)間較長(zhǎng)，在求解大型問(wèn)題上相對(duì)比較弱[2]。針對(duì)基本蟻群算法的缺點(diǎn)，文中通過(guò)引入偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則，對(duì)基本算法進(jìn)行改進(jìn)，該方法的最大的好處就是能夠使算法在較短的時(shí)間里盡快收斂到最優(yōu)解附近，使得算法耗時(shí)較少，同時(shí)可以避免局部最優(yōu)。因?yàn)闊o(wú)人機(jī)在執(zhí)行特定任務(wù)的過(guò)程中，由于飛行區(qū)域異常復(fù)雜多變，為了提高無(wú)人機(jī)在執(zhí)行任務(wù)過(guò)程中的生存概率，文中通過(guò)引入動(dòng)態(tài)窗口對(duì)無(wú)人機(jī)在碰到突發(fā)威脅的過(guò)程中進(jìn)行航跡重新規(guī)劃。

1 航跡的描述

1.1 飛行區(qū)域模型

如圖1所示，將飛行區(qū)域劃分成由個(gè)單元格組成的正方形區(qū)域，形成連接起始點(diǎn)到飛行目標(biāo)點(diǎn)的網(wǎng)絡(luò)圖。飛行器在網(wǎng)格中的節(jié)點(diǎn)上飛行。將威脅源（包括雷達(dá)、防空高炮陣地等）視為半徑為的圓。在該正方形區(qū)域中建立二維坐標(biāo)系，飛行起點(diǎn)坐標(biāo)（0，0），飛行終點(diǎn)坐標(biāo)為（，0），待選節(jié)點(diǎn)的生成和選擇原則參考文獻(xiàn)[2]，即將距離當(dāng)前飛行節(jié)點(diǎn)最近的5個(gè)節(jié)點(diǎn)作為待選節(jié)點(diǎn)。

圖1 飛行區(qū)域模型Fig.1 Model of fligth area

1.2 航跡規(guī)劃目標(biāo)函數(shù)

文中采用低于某一探測(cè)指標(biāo)，而且具有可接受航程的航跡作為任務(wù)航跡，按最小航程和最小可探測(cè)性航跡加權(quán)方法計(jì)算代價(jià)函數(shù)作為描述航跡的性能指標(biāo)。因?yàn)樵诮w行區(qū)域模型的時(shí)候?qū)⑦B續(xù)的飛行區(qū)域進(jìn)行了離散化，無(wú)人機(jī)在航跡節(jié)點(diǎn)進(jìn)行飛行，所以在計(jì)算航跡目標(biāo)優(yōu)化函數(shù)的時(shí)候以每條航跡上兩相鄰節(jié)點(diǎn)組成的航跡邊為對(duì)象計(jì)算航跡邊的代價(jià)，然后將整條航跡進(jìn)行所有的航跡邊進(jìn)行求和。具體航跡代價(jià)函數(shù)為：

其中：F（R）是整條航跡的綜合代價(jià)函數(shù)；N是該航跡所包含的節(jié)點(diǎn)個(gè)數(shù)；（i，j）是該航跡上相鄰兩節(jié)點(diǎn)；是兩相鄰節(jié)點(diǎn)所組成的航跡邊的航程是這兩相鄰節(jié)點(diǎn)所組成的航跡邊的威脅代價(jià)；k是權(quán)重系數(shù)，本文中k=0.5。文中關(guān)于航跡邊的威脅代價(jià)通過(guò)下面的這個(gè)表達(dá)式求得：1/min （l1，l2，l3…lthreatnum）。 其中 l1，l2，l3…lthreatnum為節(jié)點(diǎn) j到這威脅圓圓心的距離。

2 改進(jìn)蟻群算法

2.1 偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則

飛行器從一個(gè)節(jié)點(diǎn)轉(zhuǎn)移到另外一個(gè)節(jié)點(diǎn)是由式（2）依照概率進(jìn)行的：

而偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則可以表述為式（3）：

其中：pk（r，s）、τ（r，s）、α、β 分別表示節(jié)點(diǎn) r轉(zhuǎn)移到節(jié)點(diǎn) s的概率、節(jié)點(diǎn)r到節(jié)點(diǎn)s航跡段的信息素濃度、信息素重要因子、能見(jiàn)度重要因子；η（r，s）是節(jié)點(diǎn)s相對(duì)于節(jié)點(diǎn)r的能見(jiàn)度，文中為兩節(jié)點(diǎn)距離倒數(shù)； arg max{[τ（r，s）]α·[η（r，s）]β}函數(shù)的作用是返回{[τ（r，s）]α·[η（r，s）]β}數(shù)值為最大的節(jié)點(diǎn) s 的值；Mk是待選節(jié)點(diǎn)候選集合；q0是觸發(fā)參數(shù)；運(yùn)用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則使搜索方向更傾向于最優(yōu)解方向，從而更有利于得到最優(yōu)解。

2.2 信息素更新規(guī)則

蟻群算法中信息素更新規(guī)則可以通過(guò)式（4）來(lái)確定：

其中：

其中：antnum表示螞蟻總數(shù)；Q是給定的常數(shù)；ρ表示信息素?fù)]發(fā)系數(shù)，取值范圍為 0～1；Δτ（r，s）是本次循環(huán)中航跡邊（r，s）上總的信息素增量；Δτk（r，s）是本次循環(huán)中航跡邊（r，s）上由第只螞蟻所帶來(lái)的信息增量；wk在文中表示本次搜索中的最優(yōu)航跡的航跡代價(jià)值。

2.3 改進(jìn)的蟻群算法在二維航跡規(guī)劃中的應(yīng)用

下面的步驟主要給出了改進(jìn)蟻群算法在無(wú)人機(jī)二維航跡規(guī)劃中的應(yīng)用步驟：

1）初始化初始參數(shù)（包括螞蟻的總數(shù)、飛行區(qū)域的節(jié)點(diǎn)數(shù)目、迭代的次數(shù)等等初始參數(shù)）；

2）初始化飛行節(jié)點(diǎn)信息素，形成信息素初始矩陣，信息素初始值設(shè)為2，將在威脅源里面的節(jié)點(diǎn)信息素初值賦為0，以確保飛行器在搜索過(guò)程中避開(kāi)這些節(jié)點(diǎn)；

3）按照式（2）和式（3），從起始位置逐點(diǎn)進(jìn)行剩余節(jié)點(diǎn)轉(zhuǎn)移，直到到達(dá)目標(biāo)位置；

4）找到本次循環(huán)中的最優(yōu)路徑，利用式（4）、式（5）、式（6）對(duì)最優(yōu)路徑上的節(jié)點(diǎn)進(jìn)行信息素更新；

5）判斷是否達(dá)到指定迭代次數(shù)，如果到達(dá)則輸出最優(yōu)路徑的解。如果不是，則跳轉(zhuǎn)到第3步進(jìn)行循環(huán)迭代。

2.4 改進(jìn)的蟻群算法在二維航跡重規(guī)劃中的應(yīng)用

通過(guò)前面介紹的方法可以很好地得到無(wú)人機(jī)二維全局航跡，全局航跡的規(guī)劃是根據(jù)已知的威脅源信息離線完成的，并裝載在無(wú)人機(jī)上作為飛行的參考航跡。如果在飛行過(guò)程中遇到了事先沒(méi)有確定的威脅源，就要進(jìn)行航跡的在線重新規(guī)劃。當(dāng)無(wú)人機(jī)探測(cè)到新的威脅并且確定威脅范圍后，選擇一個(gè)合適的動(dòng)態(tài)窗口，要求此窗口包含新探測(cè)到的威脅源所包含的范圍和此范圍內(nèi)的全局航跡，并對(duì)局部航跡進(jìn)行重規(guī)劃，盡量保證飛行航跡的性能指標(biāo)最優(yōu)，下面介紹一下動(dòng)態(tài)窗口。

動(dòng)態(tài)窗口[4]：當(dāng)飛行器在某時(shí)刻探測(cè)到新威脅源的位置和該威脅源包括的范圍后，選擇一個(gè)大小合適的窗口，此窗口包含了新探測(cè)到的威脅范圍和此范圍內(nèi)包含的全局航跡，動(dòng)態(tài)窗口包含的范圍就是航跡重規(guī)劃的區(qū)域大小。動(dòng)態(tài)窗口其實(shí)就是一個(gè)大小可變的規(guī)劃區(qū)域，只是這個(gè)區(qū)域的大小是由新探測(cè)到的威脅源的位置和新威脅源覆蓋的范圍決定的，當(dāng)窗口選得越大的時(shí)候重規(guī)劃效果越好，但算法也越耗時(shí)，當(dāng)動(dòng)態(tài)窗口選擇稍小的時(shí)候重規(guī)劃效果稍差，算法越節(jié)省時(shí)間。

下面介紹一下文中介紹的蟻群算法在無(wú)人機(jī)二維航跡重規(guī)劃中的應(yīng)用步驟：

1）無(wú)人機(jī)探測(cè)新威脅的位置和威脅范圍，假設(shè)新威脅源的中心坐標(biāo)為，威脅半徑為；

2）判斷新的威脅源與機(jī)載的全局航跡有沒(méi)有交點(diǎn)：如果沒(méi)有交點(diǎn)就不需要進(jìn)行航跡的局部重規(guī)劃，無(wú)人機(jī)還是按照機(jī)載的全局航跡飛行；如果有交點(diǎn)則轉(zhuǎn)至步驟3）；

3）求出新威脅源與機(jī)載全局航跡的交點(diǎn)，假設(shè)為（xstart，ystart），（xend，yend），根據(jù)這兩個(gè)交點(diǎn)確定動(dòng)態(tài)窗口的起點(diǎn)和終點(diǎn)分別為（xstart－window，ystar－window），（xend－window，yend－window），其中window是一個(gè)事先給定的常數(shù)，一般取4～5之間的整數(shù)，window的數(shù)值越大表示動(dòng)態(tài)窗口越大，重規(guī)劃效果也越好，但是所需要的時(shí)間也越長(zhǎng)。

4）根據(jù)動(dòng)態(tài)窗口的起點(diǎn)和終點(diǎn)確定需要進(jìn)行航跡重規(guī)劃的區(qū)域，動(dòng)態(tài)窗口的起點(diǎn)和終點(diǎn)就是局部航跡規(guī)劃區(qū)域的起點(diǎn)和終點(diǎn)，確定了局部航跡規(guī)劃的起點(diǎn)和終點(diǎn)后就可以參考類似全局航跡規(guī)劃的算法，利用改進(jìn)的蟻群算法進(jìn)行動(dòng)態(tài)窗口飛行區(qū)域里航跡的重規(guī)劃；

5）當(dāng)動(dòng)態(tài)窗口里面的局部航跡重規(guī)劃后，將這個(gè)區(qū)域里面的局部航跡替代原來(lái)機(jī)載的這個(gè)范圍里面對(duì)應(yīng)的全局航跡，保證無(wú)人機(jī)可以成功的回避新探測(cè)到的威脅。

3 仿真分析

3.1 改進(jìn)蟻群算法與基本蟻群算法仿真結(jié)果對(duì)比分析

仿真設(shè)初始參數(shù)為：

antnum=20，Q=10，repeat=100，α=5，β =3，Rmax=150，ρmax=0.8，ρmin=0.2，q0=0.7。仿真結(jié)果如圖2～圖3所示。圖中實(shí)線代表改進(jìn)蟻群算法的仿真曲線，虛線代表基本蟻群算法仿真曲線。對(duì)于航跡的光滑可以采用如下方法處理：當(dāng)?shù)玫降淖顑?yōu)航跡所包含的兩個(gè)節(jié)點(diǎn)的連線段不穿過(guò)威脅源，同時(shí)在轉(zhuǎn)折點(diǎn)處滿足最小轉(zhuǎn)彎半徑rmin限制時(shí)，就將兩節(jié)點(diǎn)用直線段連接，否則就保留原來(lái)航跡，文中rmin=1。

圖2 6個(gè)威脅源下航跡Fig.2 Route under six threats

圖3 13個(gè)威脅源下航跡Fig.3 Route under thirteen threats

為了進(jìn)一步比較，下面的表另外給出了兩種方法在不同威脅源分布情況下的最優(yōu)解和收斂時(shí)間記錄，其中試驗(yàn)1是文中的方法得到的結(jié)果，試驗(yàn)2是基本算法得到的結(jié)果。

3.2 改進(jìn)蟻群算法在二維航跡重規(guī)劃中的仿真示例

初始條件同上，取window=4，重規(guī)劃的迭代次數(shù)repeat1=20，新探測(cè)到的第一個(gè)威脅源圓心為（15，1），威脅半徑為 r=4，第二個(gè)威脅源圓心為（36，1），威脅半徑為 r=4。進(jìn)行仿真，結(jié)果如圖4所示，其中黑色虛線表示離線規(guī)劃好的全局航跡，黑色實(shí)線表示重新規(guī)劃后的航跡，實(shí)線圓表示離線探測(cè)到的威脅，虛線圓表示新探測(cè)到的威脅源。

表2記錄了該仿真實(shí)驗(yàn)組的數(shù)值結(jié)果，具體如下：

表1 不同初始條件下不同方法得到的結(jié)果對(duì)比Tab.1 Comparing of result on different initial conditions using different method

圖4 重規(guī)劃航跡Fig.4 Replanning route

表2 重規(guī)劃航跡結(jié)果記錄Tab.2 Result of replanning route

4 結(jié) 論

通過(guò)引入偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則對(duì)基本蟻群算法進(jìn)行改進(jìn)，并將改進(jìn)的算法應(yīng)用到無(wú)人機(jī)二維航跡規(guī)劃上。為了提高無(wú)人機(jī)在變多的戰(zhàn)場(chǎng)環(huán)境的生存概率，通過(guò)引入動(dòng)態(tài)窗口的思想進(jìn)行航跡重規(guī)劃，最后給出了對(duì)應(yīng)的仿真示例和相應(yīng)的仿真數(shù)值結(jié)果。由前面的仿真結(jié)果可以看出，無(wú)論是基本蟻群算法還是改進(jìn)蟻群算法都可以用在無(wú)人機(jī)航跡規(guī)劃研究中，都能搜索到一條可行的航跡。但是從仿真曲線2和3可以看出在相同條件下，文中改進(jìn)的蟻群算法搜索到的航跡比基本蟻群算法搜索到的航跡的最優(yōu)解要好，從表1的數(shù)據(jù)中也可以看出利用本文改進(jìn)的蟻群算法進(jìn)行航跡規(guī)劃的時(shí)候，無(wú)論是得到的航跡最優(yōu)解還是算法耗時(shí)都要全面優(yōu)于基本蟻群算法。從仿真曲線4可以看出通過(guò)動(dòng)態(tài)窗口的引入，利用文中介紹的蟻群算法可以成功地為無(wú)人機(jī)進(jìn)行航跡重規(guī)劃，并從表2的仿真結(jié)果看以看出，利用文中改進(jìn)算法進(jìn)行航跡重規(guī)劃的時(shí)候，算法耗時(shí)基本上滿足實(shí)時(shí)性要求。

[1]鄭昌文，嚴(yán)平，丁明躍.飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢(shì)[J].宇航學(xué)報(bào)，2007，28（6）；1441-1446.ZHENG Chang-wen，YAN Ping，DING Ming-yue.Research status and trend of route planning for flying vehicles[J].Journal of Astronautics，2007，28（6）：1441-1446.

[2]楊士勇，楊丹.基于改進(jìn)蟻群算法的巡航導(dǎo)彈航跡規(guī)劃[J].宇航學(xué)報(bào)，2007，28（4）:903-907.YANG Shi-yong，YANG Dan.Route planning of cruise missile based on improved ant colony algorithm[J].Journal of Astronautics，2007，28（4）:903-907.

[3]任波，于雷，韓李勛.自適應(yīng)蟻群算法的無(wú)人機(jī)航跡規(guī)劃方法[J].電光與控制，2007，14（6）:36-39.REN Bo，YU Lei，HAN Li-xun.On path planning for UAVs based on adaptive ant system algorithm[J].Electronics Optics&Control，2007，14（6）:36-39.

[4]徐偉龍，吳慶憲，姜長(zhǎng)生.粒子群法在三維航跡規(guī)劃及其優(yōu)化中的應(yīng)用[J].電光與控制，2008，15（5）:1-6.XU Wei-long，WU Qing-xian，JIANG Chang-sheng.Application of particle swarm algorithm in 3D route planning and optimization of air vehicles[J].Electronics Optics&Control，2008，15（5）:1-6.

[5]Stump E，Michael N.Multi-Robot Persistent Sur-veillance Planning as a Vehicle Routing Problem [C]//2011 IEEE International Conference，569-575.

[6]Reiners T，Pahl J，Maroszek M，et al.Integrated Aircraft Scheduling Problem:An Auto-Adapting Algorithm to Find Robust Aircraft Assignments for Large Flight Plans[C].45th Hawaii international Conference on System Sciences，2012：1267-1276.

[7]Bertuccelli L F，Cummings M L.Operator Choice Modeling forCollaborative UAV VisualSearch tasks[C]//IEEE Transactions on Systems，2012，42（5）:1088-1099.

[8]WANG Ting-song，ZHENG Peng-jun，LIU Zhi-yuan.Model and algorithm for a liner ship fleet planning problem with uncertain container shipment demand[C]//IEEE，2012，202-207.