，，， ，

(南京航空航天大學(xué)自動(dòng)化學(xué)院，江蘇 南京 211106)

0 引言

無人機(jī)航跡規(guī)劃是指在一定的約束條件限制下，按照某種評價(jià)標(biāo)準(zhǔn)尋找從起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑[1]。航跡規(guī)劃過程中最為核心的內(nèi)容就是航跡規(guī)劃算法，針對無人機(jī)航跡規(guī)劃算法，國內(nèi)外許多學(xué)者做了大量的研究，具有代表性的航跡規(guī)劃算法有：A*算法、動(dòng)態(tài)規(guī)劃法、人工勢場法、遺傳算法、粒子群算法、人工蟻群算法等，這些算法都有其各自的特點(diǎn)，但是也存在缺點(diǎn)與不足。對于無人機(jī)航跡規(guī)劃，通常會(huì)根據(jù)具體的情況，結(jié)合實(shí)際應(yīng)用對算法進(jìn)行改進(jìn)，如郭忠同、扈宏杰[2]等人針對人工勢場法易陷入局部最優(yōu)的缺點(diǎn)，提出了改進(jìn)后的算法，將其應(yīng)用于航跡規(guī)劃中，提高了算法的收斂速度；于霜[3]等人針對傳統(tǒng)人工蜂群算法常見的缺點(diǎn)，提出用自適應(yīng)搜索機(jī)制、一種新的概率選擇方式和混沌搜索策略對算法進(jìn)行改進(jìn)；劉麗峰[4]等人以人工免疫算法為基礎(chǔ)，針對算法搜索效率差的缺點(diǎn)，對算法進(jìn)行了改進(jìn)。這些經(jīng)過改進(jìn)之后的航跡規(guī)劃算法，在一定程度上提高了算法尋優(yōu)速度，但是依舊存在很多不足：如算法的通用性較差，容易陷入局部最優(yōu)等。

針對上述問題，本文提出一種樽海鞘群智能算法(salp swarm algorithm，SSA)，該算法模擬了海洋生物樽海鞘在海洋中導(dǎo)航和覓食時(shí)的群集行為。算法通過隨機(jī)初始化種群解，選用合適的適應(yīng)度函數(shù)進(jìn)行個(gè)體評價(jià)，根據(jù)位置更新策略進(jìn)行迭代，最終得到最優(yōu)解，SSA算法具有良好的全局搜索能力和快速收斂的特點(diǎn)。同時(shí)，本文對威脅空間進(jìn)行了建模，選取了合理的評價(jià)函數(shù)，通過仿真實(shí)驗(yàn)，驗(yàn)證了算法的優(yōu)越性。

1 約束條件與威脅建模

無人機(jī)在執(zhí)行任務(wù)的過程中，需要綜合考慮各種因素，包括飛行區(qū)域的地形信息、威脅信息、飛行限制和無人機(jī)自身性能等內(nèi)容[5]。因而在無人機(jī)航跡規(guī)劃時(shí)，需要對約束條件和各類威脅進(jìn)行分析與建模，通過評估綜合代價(jià)，得到指標(biāo)函數(shù)最優(yōu)的航跡。

1.1 約束條件

1.1.1 最短航跡段

無人機(jī)在某些航跡段飛行時(shí)，需要一定的時(shí)間調(diào)整姿態(tài)，以便到達(dá)下一個(gè)指定位置時(shí)完成機(jī)動(dòng)動(dòng)作。為了保證飛行安全與質(zhì)量，無人機(jī)在飛行姿態(tài)調(diào)整時(shí)的前后一段距離，需要直飛，直飛的這段距離為最小步長，記作lmin，則飛行過程中任意航跡段都不能小于最小步長，如式(1)：

li≥lmin,(i=1,2,,n)

(1)

1.1.2 最大航程限制

無人飛行器的最長飛行距離受其所攜帶的燃料量限制。在從起點(diǎn)飛向終點(diǎn)的過程中，無人機(jī)需要回避障礙物與威脅，由于燃料有限，為保證飛行安全，必須將航程限制在一定的范圍內(nèi)。假設(shè)最大航程為lmax，一條航跡分為n個(gè)航跡段，li表示第i個(gè)航跡段，則總航程滿足以下約束：

(2)

1.1.3 最大轉(zhuǎn)彎角限制

無人機(jī)受機(jī)動(dòng)性能限制，其轉(zhuǎn)彎角和爬升/俯仰角不能過大，本文是在二維環(huán)境下對無人機(jī)航跡規(guī)劃進(jìn)行研究的，因此只考慮無人機(jī)飛行時(shí)的最大轉(zhuǎn)彎角。在無人機(jī)航跡規(guī)劃時(shí)，每個(gè)航跡段之間的夾角都不能大于預(yù)先設(shè)定的最大轉(zhuǎn)彎角。

如圖1所示，θ為最大轉(zhuǎn)彎角，假設(shè)第i個(gè)航跡點(diǎn)坐標(biāo)表示為(xi,yi)，i-1個(gè)航跡點(diǎn)坐標(biāo)表示為(xi-1,yi-1)，則第i條航跡段表示為ai=(xi-xi-1,yi-yi-1)，該約束可表示為：

(3)

圖1 最大轉(zhuǎn)彎角

1.2 威脅建模

1.2.1 山峰威脅

無人機(jī)飛行過程中受地形因素影響，而山峰是主要地形因素，對于單個(gè)山峰地形來說，可以用如下表達(dá)式來模擬：

(4)

z0為山峰地形的基準(zhǔn)高度；(x0,y0)表示山峰的中心坐標(biāo)；a，b反映x軸，y軸方向地形衰減速度，衰減越快則該軸地形越陡峭。本文假設(shè)無人機(jī)以固定高度飛行，即Z(x,y)為常數(shù)，則山峰影響區(qū)域可以用圓形表示，無人機(jī)不能在圓形區(qū)域內(nèi)飛行，obs表示無人機(jī)受山峰威脅的區(qū)域范圍，其表達(dá)式如下：

obs={(x,y)|(x-x0)2+(y-y0)2≤max(a,b)2}

(5)

1.2.2 雷達(dá)威脅

雷達(dá)是軍事作戰(zhàn)中的重要裝備，其主要是利用電磁波理論，通過接收目標(biāo)反射的回波信號(hào)進(jìn)行探測，雷達(dá)是否能截獲目標(biāo)取決于接收信號(hào)的質(zhì)量，簡化的雷達(dá)接收功率方程為[6]：

(6)

(7)

一條航跡共有n個(gè)航跡段，則整條航跡受到的雷達(dá)威脅可表示為：

(8)

經(jīng)過對山峰威脅和雷達(dá)威脅的分析，可以發(fā)現(xiàn)，山峰威脅可以近似用雷達(dá)威脅模型反映，將山峰模型用與雷達(dá)相同的量化方式進(jìn)行量化，則第i條航跡對于威脅源j的代價(jià)可表示為：

(9)

假設(shè)飛行過程中有m個(gè)威脅存在，則總的威脅代價(jià)為：

JT=JT,1+JT,2++JT,m

(10)

1.3 航跡代價(jià)評價(jià)指標(biāo)函數(shù)

綜合無人機(jī)飛行的約束條件和執(zhí)行任務(wù)可能面臨的威脅，可得到無人機(jī)航跡規(guī)劃的代價(jià)函數(shù)，代價(jià)函數(shù)需要反映出航程長短、避開威脅的程度、時(shí)間長短等指標(biāo)。航跡代價(jià)評價(jià)函數(shù)如下：

J=ωJL+(1-ω)JT

(11)

J為航路的總代價(jià)值;ω為代價(jià)權(quán)重系數(shù)，其大小根據(jù)實(shí)際規(guī)劃需要確定;JL為航程代價(jià)，JL=Li，即第i條航跡的總長度，總長度越長航程代價(jià)值越大;JT為威脅代價(jià)。

2 SSA算法

2.1 算法描述

SSA算法模擬了海洋生物樽海鞘在海洋中導(dǎo)航和覓食時(shí)的群集行為。樽海鞘的身體呈桶狀，身長在1～10 cm范圍，是一種遠(yuǎn)海膠質(zhì)脊索動(dòng)物，它們靠不斷吸入和噴出海水在海里完成移動(dòng)。樽海鞘有一個(gè)顯著的行為，是它們的蜂擁行為，這種行為主要是由于樽海鞘可以通過快速協(xié)調(diào)的改變和覓食來實(shí)現(xiàn)更好的運(yùn)動(dòng)。在SSA算法中，解群相當(dāng)于樽海鞘群，樽海鞘位置變化的過程相當(dāng)于解群不斷更新的過程。

為了解決尋優(yōu)問題，本文提出樽海鞘鏈模型[7]。樽海鞘群中有兩種類型的個(gè)體：領(lǐng)導(dǎo)者和追隨者。領(lǐng)導(dǎo)者會(huì)直接或間接的引導(dǎo)鏈條中追隨者的運(yùn)動(dòng)。一個(gè)由M個(gè)樽海鞘組成的樽海鞘鏈X可以由一個(gè)二維矩陣表示，這個(gè)群體的目標(biāo)是搜索空間中的一個(gè)食物來源，記作F。

(12)

SSA算法的數(shù)學(xué)描述為：設(shè)樽海鞘搜索的區(qū)域是一個(gè)N維空間，一個(gè)群體中有M個(gè)樽海鞘，其中第i個(gè)樽海鞘的位置x表示優(yōu)化問題的其中一個(gè)解。每個(gè)樽海鞘個(gè)體會(huì)按照一定的規(guī)則不斷調(diào)整自己的位置，最終尋得最優(yōu)解，每個(gè)樽海鞘都有一個(gè)由被優(yōu)化函數(shù)決定的適應(yīng)度值，根據(jù)適應(yīng)度值計(jì)算函數(shù)可以求出目前為止整個(gè)樽海鞘群發(fā)現(xiàn)的最好位置，在N維空間中，每次迭代之后，都會(huì)存在一個(gè)目前為止整個(gè)樽海鞘群發(fā)現(xiàn)的最好位置，記為g=[g1,g2,,gN]，gd表示在d維分量中的最優(yōu)解，將gd作為d維分量中的食物源Fd，即群體目標(biāo)隨迭代次數(shù)而更新。則第d維分量中，作為領(lǐng)導(dǎo)者的樽海鞘位置變化公式為：

(13)

k表示迭代次數(shù)；c1是一個(gè)在迭代過程中逐漸減少的變量，并按照下列方程計(jì)算：

(14)

l和L分別是當(dāng)前迭代和最大迭代次數(shù)。c2和c3是[0-1]之間的隨機(jī)數(shù)，它們的取值決定了將第d個(gè)維度中的下一個(gè)位置指向正或者負(fù)以及指定步長。ubd,lbd分別代表d維分量中x的最大和最小邊界。d維分量中，第i個(gè)跟隨者位置變化公式為：

(15)

與其他群智能算法類似，SSA是一種基于群體的算法，并從隨機(jī)初始化個(gè)體開始，每一個(gè)個(gè)體都代表解決目標(biāo)問題的候選方案。SSA算法保存了迄今為止獲得的最佳解決方案，并將其作為群體目標(biāo)，保證了群體中解的優(yōu)良性。算法只更新群體中領(lǐng)導(dǎo)者相對于目標(biāo)的位置，領(lǐng)導(dǎo)者可充分利用和探索其周圍的空間，此過程具有快速和隨機(jī)的特點(diǎn)，從而增加了算法的尋優(yōu)效率。在足夠的探索后，群體中的跟隨者會(huì)逐漸向領(lǐng)導(dǎo)者移動(dòng)，此過程不如探索階段的范圍大，具有緩慢改變和局部移動(dòng)的特點(diǎn)，可避免算法陷入局部最優(yōu)。

2.2 規(guī)劃空間

無人機(jī)航跡規(guī)劃問題可描述為在給定的飛行區(qū)間內(nèi)，尋找從起始點(diǎn)到達(dá)目標(biāo)點(diǎn)的最優(yōu)路徑。為降低航跡規(guī)劃問題的復(fù)雜性，首先需要對飛行環(huán)境進(jìn)行規(guī)劃和建立模型，本文提出一種操作簡單、易于計(jì)算的方法來構(gòu)建環(huán)境模型[8]。

圖2 路徑的生成

2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是衡量樽海鞘種群質(zhì)量的重要依據(jù)，適應(yīng)度函數(shù)的選取，是種群個(gè)體位置變換更新的基礎(chǔ)，它對于算法的收斂性和快速性有著重要的影響，適應(yīng)度函數(shù)是評價(jià)航跡好壞的指標(biāo)。綜合考慮無人機(jī)飛行過程的約束條件和威脅等影響因素，可得到適應(yīng)度函數(shù)U(x)的公式：

U(x)=ε∞-J

(16)

ε∞是一個(gè)足夠大的數(shù)；J為航跡總代價(jià)值，結(jié)合代價(jià)公式和適應(yīng)度函數(shù)公式可以看出，航跡長度越短，航跡適應(yīng)度函數(shù)U(x)越大，航跡段距離威脅越遠(yuǎn)，適應(yīng)度函數(shù)越大。因此，該計(jì)算公式在滿足約束條件要求下，可達(dá)到減小航跡長度和避開威脅的目的。

2.4 算法流程

SSA算法的基本流程[9]如圖3所示。

圖3 SSA算法流程圖

3 仿真驗(yàn)證

3.1 仿真條件

本文設(shè)定了一個(gè)240 km×120 km的二維規(guī)劃空間，設(shè)無人機(jī)飛行起始點(diǎn)位置為S，目標(biāo)點(diǎn)位置為T，起點(diǎn)與目標(biāo)點(diǎn)之間的直線距離為200 km，本文采用SSA算法和粒子群算法進(jìn)行航跡規(guī)劃，使用MATLAB R2014a進(jìn)行計(jì)算和仿真分析。將整條航跡分為N+1段，取N=10，群體大小M取30，最大迭代次數(shù)L=100，代價(jià)權(quán)重系數(shù)ω取0.3，c1根據(jù)公式(14)計(jì)算，c2和c3取[0-1]之間的隨機(jī)數(shù)，ub,lb為y的最大和最小邊界，令ub=120,lb=0，最大轉(zhuǎn)彎角度設(shè)為±45°，最大航程為400 km。

3.2 仿真結(jié)果與分析

如圖4和圖5所示，取無人機(jī)飛行起點(diǎn)作為二維坐標(biāo)系的原點(diǎn)；三角形代表無人機(jī)要到達(dá)的目標(biāo)位置；灰色圓形表示雷達(dá)區(qū)域；黑色圓形表示山峰區(qū)域；黑色線段表示規(guī)劃出的無人機(jī)最優(yōu)路徑。仿真結(jié)果證明，采用SSA算法和粒子群算法各運(yùn)行100次后，兩種算法都可以找到各自的最優(yōu)路徑。對比圖4和圖5可以看出，針對復(fù)雜環(huán)境，SSA算法可充分利用威脅模型，規(guī)劃出較短路徑，并且可以保持較小的轉(zhuǎn)彎角度，更好的體現(xiàn)了SSA算法的快速收斂性和魯棒性，相比之下，粒子群算法所規(guī)劃出的路徑航程較長、耗時(shí)多，轉(zhuǎn)彎角度也偏大。

如圖6所示，利用MATLAB對所建立的適應(yīng)度函數(shù)進(jìn)行驗(yàn)證，黑色實(shí)線表示SSA算法的適應(yīng)度值變化趨勢，虛線表示粒子群算法的適應(yīng)度變化趨勢。由此可以看出，利用SSA算法求解時(shí)，算法收斂時(shí)適應(yīng)度值為140，而運(yùn)用普通的粒子群算法時(shí)，算法收斂時(shí)適應(yīng)度函數(shù)值為80。顯然，SSA算法的尋優(yōu)速度和尋優(yōu)效果都要比粒子群算法好。

圖4 基于SSA算法的無人機(jī)航跡規(guī)劃

圖5 基于粒子群算法的無人機(jī)航跡規(guī)劃

圖6 適應(yīng)度收斂圖

如圖7所示，基于兩種算法規(guī)劃的路徑長度均隨迭代次數(shù)不斷變化。從圖中可以看出，在基于粒子群算法的航跡規(guī)劃中，最短航跡近似為260 km，收斂次數(shù)約為80，收斂區(qū)間為258～262 km。而在基于SSA算法的航跡規(guī)劃中，最短航跡近似為210 km，收斂次數(shù)約為60，收斂區(qū)間為209～211 km。

圖7 路徑長度隨迭代次數(shù)變化圖

4 結(jié)束語

本文研究了復(fù)雜環(huán)境下的無人機(jī)航跡規(guī)劃問題，首先分析了飛行過程中的約束條件，建立了山峰、雷達(dá)等各類威脅模型，為算法選取了合適的適應(yīng)度函數(shù)；對飛行區(qū)域進(jìn)行了合理的規(guī)劃，通過SSA算法，求解無人機(jī)最優(yōu)路徑。該算法通過位置更新策略來更新群體狀態(tài)，增加了種群的多樣性和尋優(yōu)效率，與傳統(tǒng)算法相比，SSA算法可避免局部最優(yōu)，具有很好的全局收斂性。但本文只是考慮了二維空間中無人機(jī)航跡規(guī)劃問題，并未涉及三維空間。為了使無人機(jī)更好的適應(yīng)作戰(zhàn)環(huán)境，如何將SSA算法應(yīng)用到無人機(jī)三維航跡規(guī)劃問題中，將是未來需要深入研究的問題。