楊 玉,金 敏,魯華祥,3,4,5

1(中國科學(xué)技術(shù)大學(xué) 微電子學(xué)院,合肥 230026)

2(中國科學(xué)院 半導(dǎo)體研究所,北京 100083)

3(中國科學(xué)院大學(xué),北京 100049)

4(中國科學(xué)院 腦科學(xué)與智能技術(shù)卓越創(chuàng)新中心,上海 200031)

5(半導(dǎo)體神經(jīng)網(wǎng)絡(luò)智能感知與計算技術(shù)北京市重點實驗室,北京 100083)

軍用無人機由于其造價成本低,機動性能好,可以減少人員傷亡等優(yōu)點,被大量用于執(zhí)行不同的軍事任務(wù).而成功執(zhí)行任務(wù)的前提是無人機能夠保證安全及時的達(dá)到指定目標(biāo)區(qū)域.這就需要在任務(wù)空間中,為無人機規(guī)劃出一條滿足可行性、實效性、最優(yōu)性的航跡[1].常用的航跡規(guī)劃算法可分為經(jīng)典算法和智能算法兩大類[2].經(jīng)典算法主要包括動態(tài)規(guī)劃法、牛頓法、最優(yōu)控制法等.這些經(jīng)典算法雖然算法簡單,但是計算時間會隨著問題規(guī)模的變大而爆炸式的增長,所以目前航跡規(guī)劃最常用的還是智能規(guī)劃算法.

智能算法主要有A*算法[3]、遺傳算法[4]、蟻群算法[5]等.這些算法雖然各有優(yōu)點,但若直接用它們的基本形式來求解航跡規(guī)劃問題,會存在各種各樣的缺點,比如搜索耗時長,占用內(nèi)存大,容易陷入局部最優(yōu)等等.對此許多專家學(xué)者對它們進行了不同方面的改進工作.文獻[6]在A*算法的啟發(fā)函數(shù)中加入了父節(jié)點的影響,使算法的實時性得到了提高.文獻[7]通過指數(shù)衰減的方式對文獻[6]提出的啟發(fā)函數(shù)進行了加權(quán),使算法在搜索航跡時的節(jié)點遍歷數(shù)目得到減少,進而減少了內(nèi)存的占用.文獻[8]使用了二叉堆的結(jié)構(gòu)對A*算法中open 表的管理進行了優(yōu)化,提高了算法的運行速度,并對最終的航跡進行了平滑處理,使之更適合無人機飛行.文獻[9]將基因?qū)Ρ榷纫氲竭z傳算法中,用來增加優(yōu)良基因遺傳給下一代的概率,提高了算法在航跡規(guī)劃中的實時性.文獻[10]通過在遺傳算法的群體進化過程中,根據(jù)個體適應(yīng)度值的大小來自動調(diào)節(jié)交叉概率和變異概率,從一定程度上克服了算法早熟的缺點.文獻[11]將自適應(yīng)閾值引入到蟻群算法中,利用漸進減少的閾值對算法的搜索過程進行干涉,降低了算法陷入局部最優(yōu)的風(fēng)險.綜合上述,如何提高航跡規(guī)劃算法的求解質(zhì)量、時效性,同時盡量減少算法耗用的內(nèi)存空間,是我們后續(xù)算法研究的出發(fā)點.

智能算法中的模擬退火算法[12]具有簡單易實現(xiàn)、局部搜索能力強、在一定程度上能夠擺脫局部最優(yōu)解的特點.但通常要得到更優(yōu)化的解,則需要耗費較長的收斂時間.本文在對其進行設(shè)計與實現(xiàn)之后,在初始解產(chǎn)生方式上,引入了簡化的稀疏A*算法,進而得到了FSSA-SA 算法,并且對算法求解過程中的冗余節(jié)點進行了剔除.相比于模擬退火算法,新的FSSA-SA 算法在求解速度和質(zhì)量上,都有所提升.

1 航跡規(guī)劃問題建模

1.1 威脅建模

無人機飛行環(huán)境中的威脅信息可以事先通過各種偵查手段來獲得,包括它們的位置,影響范圍等.在此我們主要考慮靜態(tài)情形下地形、高炮、雷達(dá)、導(dǎo)彈對無人機的威脅.在航跡搜索的過程中,通過有效避開這些威脅所影響的區(qū)域,就可以大大提高無人機的生存率.

二維空間情況下,對上述威脅建模的通常方法是先將其作用范圍等效為圓,威脅中心點等效為圓心,再進一步建立無人機所受威脅概率p與它到該威脅中心的距離之間的函數(shù)關(guān)系[13]：

其中,d為無人機到威脅中心的距離,Rmin為必受威脅區(qū)半徑,對無人機而言屬于禁飛區(qū).Rmax為該威脅源所能影響的最大范圍半徑,它與Rmin共同確定的圓環(huán)區(qū)域中,以一定的概率存在著對無人機的威脅,該威脅概率用函數(shù)f(d)表示.當(dāng)d大于Rmax時,則認(rèn)為無人機不受該威脅源的影響.文獻[13]中給出了雷達(dá)、導(dǎo)彈、高炮、地形四類威脅源的詳細(xì)威脅模型,并通過分析,進一步簡化得到了它們對應(yīng)的威脅概率函數(shù)表達(dá)式：

其中,pM,pA,pR,pT分別對應(yīng)導(dǎo)彈、高炮、雷達(dá)、地形的威脅概率.可見,隨著距離d的增大,無人機所受威脅也就越小.

1.2 無人機自身的約束

在考慮航跡安全性的同時,可行性也至關(guān)重要.由于無人機自身攜帶的燃油有限,因此要求我們規(guī)劃出的航跡總航程要盡量的小,必須滿足在無人機最大航程范圍以內(nèi).另一方面,受無人機最大轉(zhuǎn)向角的限制,要求我們規(guī)劃出的航跡要盡量平滑.

1.3 綜合代價函數(shù)

綜合代價函數(shù)是無人機面臨的各類威脅與約束在飛行航跡上的集中反映.我們通過它來衡量眾多航跡的優(yōu)劣或者某一空間位置的好壞.這里我們給出綜合代價E的函數(shù)表達(dá)式如下：

式中,L表示整條航跡.et和el分別對應(yīng)每個微元航跡段上的威脅代價與油耗代價,a1,a2分別對應(yīng)它們的權(quán)重系數(shù).E表示綜合代價,它是威脅代價與油耗代價在整條航跡上的積分疊加值.Et和El分別為總威脅和總油耗代價.

由于在規(guī)劃空間中,我們用一系列離散節(jié)點來表示整條航跡,因此可以對各相鄰兩個節(jié)點間的航跡段長度值進行求和,再乘以油耗因子來得到總油耗代價：

式中的n為總航跡節(jié)點數(shù),ωl是油耗因子,代表航程向油耗代價轉(zhuǎn)換的系數(shù),li,i+1為航跡節(jié)點i和i+1 之間的距離.

對于節(jié)點i和i+1 所確定的航跡段,在計算其威脅代價時,為了簡化計算,我們使用航跡段上有限個節(jié)點的威脅代價累加,來近似對整個航跡段的威脅代價積分運算.借鑒文獻[14]中的方法對航跡段進行取點,即取它的4 個五等分點和末端點i+1 共5 個節(jié)點.在得到各航跡段的威脅代價后,將它們累加一起,就得到了整條航跡的總威脅代價：

其中,Pi,i+1,j為所有威脅源在航跡段(i,i+1)上第j個節(jié)點處的威脅概率值疊加后的總和.

2 基于模擬退火算法的航跡規(guī)劃

2.1 模擬退火算法基本原理

模擬退火算法是對固體退火過程的近似模擬,其基本思想如下：首先,給系統(tǒng)賦予一個初始狀態(tài),同時將溫度設(shè)定的比較高；然后,給與當(dāng)前狀態(tài)一個隨機的擾動,產(chǎn)生一個新的狀態(tài),并通過前后兩個狀態(tài)的能量變化來判斷是否接受該新狀態(tài).對于系統(tǒng)能量減小的狀態(tài),系統(tǒng)直接接受；對于系統(tǒng)能量增加的狀態(tài)則在高溫時能夠以很大概率接受,后期隨著系統(tǒng)溫度的逐漸降低,接受的可能性就越來越小,直到不再接受.

在實際求解優(yōu)化問題的運用中,新生解的接受概率由Metropolis 準(zhǔn)則[15]得到：

式中,Pt表示當(dāng)前解xi轉(zhuǎn)換到新解xi+1的概率.ΔE為新解對應(yīng)的待優(yōu)化目標(biāo)函數(shù)值與原值之間的變化量.β對應(yīng)溫度的倒數(shù).當(dāng)遇到使 ΔE大于0 的新解時,處理方式如下：先產(chǎn)生一個在[0,1)區(qū)間內(nèi)均勻分布的隨機數(shù)u,如果它滿足不等式u＜exp(-βΔE),那么就將這個新解接受,否則不予接受.

2.2 模擬退火算法的實現(xiàn)

2.2.1 模擬退火算法

結(jié)合模擬退火算法的基本原理,并參考文獻[16]中的初始解產(chǎn)生方式,我們給出如下的基本模擬退火算法：

(1)設(shè)置起始溫度倒數(shù)β0和終止溫度倒數(shù)β1以及退火溫度表長度nsweeps的值,以 β1-β0/nsweeps的值為間距產(chǎn)生退火溫度表.

(2)隨機的在規(guī)劃空間中產(chǎn)生連接起始點和終點的初始航跡,計算相應(yīng)的綜合代價值,并將β設(shè)置為起始值.

(3)在當(dāng)前溫度下,沿著從起點到終點的方向,依次對除航跡起始點、終點以外的每一個中間節(jié)點進行擾動操作,并計算該次擾動產(chǎn)生的新解對應(yīng)的ΔE.如果 ΔE＜0 ,或ΔE＞0且u＜exp(-βΔE),則接受此新解；否則不接受,并將下一節(jié)點作為新的擾動目標(biāo).

(4)如果對所有中間節(jié)點都完成了步驟(3)中所述操作,則轉(zhuǎn)步驟(5),否則繼續(xù)對剩余節(jié)點進行未完成的操作.

(5)將溫度表中的下一個值賦值給β,并判斷是否到達(dá)終止值β1,若是則終止算法,輸出最終結(jié)果.否則,轉(zhuǎn)步驟(3).

2.2.2 新解的產(chǎn)生以及ΔE的計算

如何對當(dāng)前解進行"細(xì)微擾動",產(chǎn)生新的解.我們給出如下的設(shè)計方法：

圖1 新解產(chǎn)生示意圖

如圖1所示,在航跡段中,設(shè)C 是當(dāng)前被選中需要更新位置的節(jié)點,A,B 是它的兩個相鄰節(jié)點.我們在與A、B 節(jié)點連線垂直的兩個方向中,隨機選擇一個方向?qū)⒐?jié)點C 移動一小段距離ds,并將移動后的節(jié)點與其他原航跡節(jié)點構(gòu)成的航跡作為新產(chǎn)生的解.ds的值在退火過程中,會隨著溫度的降低而慢慢變小.

令A(yù)、B、C 三個節(jié)點的坐標(biāo)分別為(x1,y1)、(x2,y2)、(xold,yold),則更新后的C 節(jié)點位置(xnew,ynew)計算方式如下：如果A、B 間斜率存在,則：

如果A、B 間斜率不存在,則：

其中,k為A、B 節(jié)點間的斜率,b是為了簡化公式引入的參數(shù),μ為0 到1 之間均勻分布的隨機數(shù).

新解的產(chǎn)生帶來了航跡綜合代價的變化.我們設(shè)原航跡段AC、CB 對應(yīng)的代價分別為e1和e2,新航跡段的分別為e3和e4.則：

可以看到,我們只需要計算兩個發(fā)生變化的航跡段的代價和的差,就能得出整條航跡的綜合代價變化量,而不用先求出變化前后整條航跡的代價后再做差來得到.

3 模擬退火算法與簡化稀疏A*算法的融合

3.1 FSSA-SA 算法和簡化的稀疏A*算法

理想的模擬退火算法,只要退火起止溫度選擇合適,退火時間足夠長,初始解的選擇對最終結(jié)果影響不大.但在實際情況下,給無人機用做航跡規(guī)劃的時間是十分有限的,因此,如果能夠用簡單的方法,快速的產(chǎn)生一個盡量靠近最優(yōu)解的初始解,則有希望能夠使模擬退火算法在更短時間里得到一個更優(yōu)的結(jié)果.本文我們提出用簡化的稀疏A*算法來產(chǎn)生模擬退火算法的初始解,再將二者融合后得到的FSSA-SA 算法用于最終的航跡規(guī)劃.具體實現(xiàn)時,可將3.2.1 節(jié)中模擬退火算法步驟(2)里的初始解產(chǎn)生方式換成由簡化的稀疏A*算法得到.

稀疏A*算法[17]是一種啟發(fā)式的搜索算法.它的代價函數(shù)為f(n)=g(n)+h(n).g(n)是從起始點到當(dāng)前節(jié)點n的實際代價值,我們可以通過將計算E時的疊加上限由終點改為節(jié)點n來得到.h(n)表示由當(dāng)前節(jié)點到終點的代價預(yù)估值,其值一般用當(dāng)前點到終點的距離乘以一定的系數(shù)得到.f(n)則代表途經(jīng)節(jié)點n的整條航跡的總代價估值.

圖2 稀疏A*算法節(jié)點擴展示意圖

算法在搜索航跡時,從起始點開始向外逐步擴展產(chǎn)生備選節(jié)點.如圖2所示,每次擴展都以一定步長,按照當(dāng)前前進的方向,在滿足無人機最大轉(zhuǎn)向角約束的范圍內(nèi),產(chǎn)生新的節(jié)點.再用這些新節(jié)點更新待擴展節(jié)點集,并從所有待擴展節(jié)點中選擇具有最小總代價估值f(n)的節(jié)點進行下一次的擴展.我們借鑒文獻[18]中提出的無記憶性思想,對上述擴展過程進行簡化：每一次只從當(dāng)前節(jié)點產(chǎn)生的待擴展節(jié)點中選擇最優(yōu)的一個進行下一步擴展.通過這種簡化,我們可以快速的得到一個代價值相對較小的初始解.簡化后的稀疏A*算法的步驟為：

(1)設(shè)置好搜索步長、相應(yīng)角度參數(shù)、代價參數(shù).

(2)以起始點為當(dāng)前點,將終點的方向假定為此時前進的方向,產(chǎn)生擴展節(jié)點.

(3)分別計算各擴展節(jié)點對應(yīng)的f(n).選擇具有最小f(n)值的節(jié)點作為新的當(dāng)前點.

(4)判斷當(dāng)前節(jié)點距離終點的距離是否小于等于一個步長,若是,則將終點加入航跡中,算法結(jié)束.否則轉(zhuǎn)至步驟(5).

(5)利用前一航跡節(jié)點和當(dāng)前點以所確定的方向,產(chǎn)生新的擴展節(jié)點,轉(zhuǎn)至步驟(3).

值得注意的是,當(dāng)面臨的環(huán)境較為復(fù)雜時(比如存在近似"凹" 字形區(qū)域),上述算法的這種"搜一步,走一步" 的擴展模式,很有可能會使搜索過程形成一個閉環(huán).換言之,尚未擴展完成的航跡形成了閉合回路,使得接下來的搜索過程在這條回路上周而復(fù)始,陷入死循環(huán).為了避免上述情況的發(fā)生,我們可以等角間距地產(chǎn)生新節(jié)點,并使間距值不能整除360 度.

通常情況下,由于只是用來產(chǎn)生模擬退火算法的初始解,所以對于簡化的稀疏A*算法而言,我們可以將航跡最大轉(zhuǎn)角的值設(shè)置的更大一些,從而能夠更大范圍的找尋每次擴展時的位置最優(yōu)點.但是假如環(huán)境中存在長時間無法跳出的搜索死區(qū)時,則應(yīng)適當(dāng)縮小最大擴展角的范圍(最極端情況下變?yōu)閮H直線向前擴展),以保證擴展的航跡能從組成搜索死區(qū)的威脅區(qū)中穿出,繼續(xù)向目標(biāo)點擴展.

簡化的稀疏A*算法由于每步只進行一次擴展,所以對環(huán)境的感知能力是很有限的,最終導(dǎo)致產(chǎn)生的航跡全局性較差.為了改善這一點,我們可以將原先的搜索起始點和終點調(diào)換一下,再進行一次搜索,然后將兩條航跡進行對比,選擇具有較小綜合代價的那條作為我們的規(guī)劃初始航跡.

圖3 簡化稀疏A*算法調(diào)換起始點前后的規(guī)劃結(jié)果圖

如圖3中所示的規(guī)劃情況中,虛線表示的路徑為利用簡化稀疏A*算法從起始點向終點搜索得到的結(jié)果,由于搜索過程中碰到了近似”凹” 形的威脅區(qū)域,使得規(guī)劃出的路徑存在繞徑.而在調(diào)換起始點重新搜索后,得出的圖3中實線表示的路徑則較優(yōu)化的多,更適合作為規(guī)劃初始解.

3.2 對FSSA-SA 算法中位置冗余節(jié)點的剔除

退火過程中可能會出現(xiàn)兩個或多個位置近似重合的節(jié)點,這些節(jié)點在溫度不高且所受擾動幅度較小的情況下顯得多余：既不能為改善航跡質(zhì)量做出主要貢獻,又浪費了系統(tǒng)運行的時間.對于這樣的節(jié)點,應(yīng)該給與剔除,以加快算法運行的速度.產(chǎn)生位置相近似的冗余節(jié)點的主要原因如下：

第一,退火過程中,雖然節(jié)點的位置變化都是隨機的,但總航程會呈現(xiàn)出越來越小的趨勢,這就使得航跡節(jié)點的整體分布逐漸稠密化.例如在圖2中,C 節(jié)點只有朝著接近A、B 節(jié)點連線的方向上移動才能縮短航程,進而它與A、B 節(jié)點的距離變得更近了.

第二,簡化的稀疏A*算法在遇到較復(fù)雜環(huán)境時,為了跳出"搜索死區(qū)",會進行一定步數(shù)的搜索,使得在當(dāng)前擴展區(qū)域內(nèi)的節(jié)點較為密集.在后面的退火過程中,為了減少被這些節(jié)點浪費掉的航程,會使它們的位置變得更加緊湊.

剔除位置冗余節(jié)點的具體方法如下：當(dāng)系統(tǒng)溫度下降至設(shè)定的低溫段時,對于每一個航跡中間節(jié)點,不管其位置在受擾動后是否發(fā)生變化,如果它與任何一個相鄰航跡節(jié)點間的橫縱坐標(biāo)差值的絕對值都小于某一設(shè)定閾值,則將其剔除.

4 仿真結(jié)果及分析

我們將本文的FSSA-SA 算法與稀疏A*算法[17]、模擬退火算法[16](后文簡稱SA 算法)進行了仿真對比試驗,并對結(jié)果進行了分析.實驗中的規(guī)劃環(huán)境大小為100km×100km,威脅信息如表1所示(單位為km).實驗使用的PC 系統(tǒng)為Windows7,處理器型號為Intel(R)Core(TM)i7-6700,主頻率3.40 GHz.開發(fā)環(huán)境為Visual Studio,編程語言為C++.使用Matlab 對規(guī)劃環(huán)境和規(guī)劃得到的航跡進行畫圖.

代價函數(shù)中,威脅代價和油耗代價的權(quán)值系數(shù)a1,a2分別為20,8,油耗因子ωl為0.1.算法的主要參數(shù)方面,在稀疏A*及其簡化算法中,擴展步長為6；模擬退火算法中,β0和β1的值分別為0.05 和3.0,nsweeps的值在兩次實驗中依次為2000 和1000,ds的初值為1.3,并在退火過程的1/2 和3/4 以及9/10 處分別減小至初值的0.8、0.5 和0.3 倍.FSSA-SA 算法中,在退火過程的后1/3 段進行冗余節(jié)點剔除,判斷位置冗余的閾值設(shè)置為0.5.

表1 威脅信息表

我們進行了兩組規(guī)劃仿真實驗,規(guī)劃起止點分別為(85,15)、(5,85)和(10,10)、(100,100).每組實驗中,每個算法都進行了10 次航跡規(guī)劃,各自規(guī)劃中最優(yōu)結(jié)果見圖4、5.10 次規(guī)劃結(jié)果取均值后如表2所示.

從表2中的初始代價一項可以看出,簡化的稀疏A*算法相比于隨機產(chǎn)生的方式能夠得到更優(yōu)化的初始航跡.這是由于它在搜索初始航跡時,在綜合代價函數(shù)的作用下,每一步都盡量選取威脅較小且盡量靠近目標(biāo)點的節(jié)點作為下一個擴展節(jié)點.換句話說,算法的每一步的擴展都建立在對上一步擴展節(jié)點的擇優(yōu)選擇之上,這樣能夠盡量保證得到代價較低的初始航跡.從表2中的最終代價均值可以看到,從更優(yōu)化的初始解開始再經(jīng)過相同的退火過程之后,新的FSSA-SA 算法得出的結(jié)果要比SA 算法更為優(yōu)化.

忽略初始化的影響,由SA 與FSSA-SA 算法的步驟可知,它們在搜索航跡中的主要耗時取決于降溫過程中,對整條航跡反復(fù)遍歷中的擾動與擇優(yōu).參數(shù)nsweeps的大小決定了反復(fù)遍歷的次數(shù),航跡節(jié)點數(shù)目的大小決定了每次遍歷中需要訪問節(jié)點的個數(shù).對于SA 算法而言,其航跡節(jié)點數(shù)目始終恒定,若設(shè)初始航跡節(jié)點數(shù)為m,則m×nsweeps的值越大,搜索耗時就越長,反之則就越少,這一點在表2中兩次實驗的SA算法耗時對比中得到了驗證.對于FSSA-SA 算法而言,由于在低溫區(qū)進行了冗余節(jié)點的剔除,所以在初始航跡節(jié)點數(shù)目、退火條件都相同的情況下,其搜索耗時要少于或相近于SA 算法,具體結(jié)果如表2所示.進一步說,簡化稀疏A*算法搜索得到的初始航跡的節(jié)點數(shù)目與nsweeps的乘積大小,可以為判斷FSSA-SA 算法的上限運行時間長短提供參考.

圖4 第一次仿真規(guī)劃結(jié)果示意圖

圖5 第二次仿真規(guī)劃結(jié)果示意圖

從表2可知,相比于稀疏A*算法的搜索結(jié)果,雖然FSSA-SA 算法最終航跡代價略高,但其占用了較少的節(jié)點內(nèi)存空間,花費了較少的搜索時間.稀疏A*算法的內(nèi)存占用量與運行耗時會隨著搜索覆蓋范圍的增大而增加,因為其要遍歷每一個已到訪位置和為它們提供儲存空間.FSSA-SA 算法的耗時前文已做出分析,它的運行內(nèi)存占用量主要由簡化稀疏A*算法決定.簡化的稀疏A*算法在搜索過程中,一方面保存已搜得的路徑節(jié)點,另一方面只保存被擴展節(jié)點的當(dāng)前最優(yōu)子節(jié)點,所以在搜得整條初始航跡時的耗存節(jié)點數(shù)最大.在后續(xù)的退火過程中,由于去冗余節(jié)點操作的存在,這些節(jié)點的數(shù)目只可能減少而不會增加.因此,FSSA-SA 算法的最大耗存節(jié)點數(shù)取決于簡化稀疏A*算法規(guī)劃出的 初始解節(jié)點數(shù)大小.

表2 規(guī)劃結(jié)果對比表

觀察圖4、5 可以看到,FSSA-SA 算法規(guī)劃的航跡整體較為平滑.這是因為：為了縮短航程,文中設(shè)計的新解產(chǎn)生方式能夠使得航跡上的每一個中間節(jié)點,都盡量的與它相鄰的兩個節(jié)點構(gòu)成一條直線.進而從整體看來,航跡中沒有較大的轉(zhuǎn)角出現(xiàn),更適合無人機實際的飛行.

5 結(jié)束語

本文為解決威脅環(huán)境下的無人機航跡規(guī)劃問題,提出了一種FSSA-SA 算法.該算法中,使用簡化稀疏A*算法為模擬退火算法產(chǎn)生初始解,并通過將某一節(jié)點在與其兩個相鄰節(jié)點連線垂直的方向上進行隨機移動,實現(xiàn)對退火過程中隨機擾動的模擬,在低溫區(qū)時,對于位置冗余的節(jié)點進行了剔除.實驗結(jié)果表明,本文FSSA-SA 算法能夠利用較少內(nèi)存,快速的得到一條綜合代價較低且較為平滑的航跡,在實時性要求較高并且存儲資源有限的規(guī)劃情況下,具有一定的實用性.