基于改進(jìn)蟻群算法的無人機(jī)二維航跡規(guī)劃和重規(guī)劃

唐必偉，方 群

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

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

1 航跡的描述

1.1 飛行區(qū)域模型

如圖1所示，將飛行區(qū)域劃分成由個單元格組成的正方形區(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個節(jié)點(diǎn)作為待選節(jié)點(diǎn)。

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

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

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

其中：F（R）是整條航跡的綜合代價函數(shù)；N是該航跡所包含的節(jié)點(diǎn)個數(shù)；（i，j）是該航跡上相鄰兩節(jié)點(diǎn)；是兩相鄰節(jié)點(diǎn)所組成的航跡邊的航程是這兩相鄰節(jié)點(diǎn)所組成的航跡邊的威脅代價；k是權(quán)重系數(shù)，本文中k=0.5。文中關(guān)于航跡邊的威脅代價通過下面的這個表達(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ī)則

飛行器從一個節(jié)點(diǎn)轉(zhuǎn)移到另外一個節(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航跡段的信息素濃度、信息素重要因子、能見度重要因子；η（r，s）是節(jié)點(diǎn)s相對于節(jié)點(diǎn)r的能見度，文中為兩節(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ī)則可以通過式（4）來確定：

其中：

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

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

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

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

2）初始化飛行節(jié)點(diǎn)信息素，形成信息素初始矩陣，信息素初始值設(shè)為2，將在威脅源里面的節(jié)點(diǎn)信息素初值賦為0，以確保飛行器在搜索過程中避開這些節(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）對最優(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)用

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

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

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

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

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

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

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

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

3 仿真分析

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

仿真設(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)蟻群算法的仿真曲線，虛線代表基本蟻群算法仿真曲線。對于航跡的光滑可以采用如下方法處理：當(dāng)?shù)玫降淖顑?yōu)航跡所包含的兩個節(jié)點(diǎn)的連線段不穿過威脅源，同時在轉(zhuǎn)折點(diǎn)處滿足最小轉(zhuǎn)彎半徑rmin限制時，就將兩節(jié)點(diǎn)用直線段連接，否則就保留原來航跡，文中rmin=1。

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

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

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

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

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

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

表1 不同初始條件下不同方法得到的結(jié)果對比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é) 論

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

[1]鄭昌文，嚴(yán)平，丁明躍.飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢[J].宇航學(xué)報，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é)報，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)蟻群算法的無人機(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]徐偉龍，吳慶憲，姜長生.粒子群法在三維航跡規(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.