一種基于SVM的航路規(guī)劃研究

程春華，吳進(jìn)華，周大旺

（海軍航空工程學(xué)院 a.研究生管理大隊(duì)；b.控制工程系，山東 煙臺(tái) 264001)

0 引言

航跡規(guī)劃定義為在特定約束條件（包括環(huán)境約束和運(yùn)動(dòng)體自身約束）下，尋找運(yùn)動(dòng)物體從起始點(diǎn)到目標(biāo)點(diǎn)，滿足某種性能指標(biāo)和某些約束的最優(yōu)運(yùn)動(dòng)路線、路徑[1-2]。對(duì)于反艦導(dǎo)彈，其航跡規(guī)劃的目的就是通過規(guī)劃對(duì)島嶼、陸地、警戒雷達(dá)區(qū)域或其他需要規(guī)避的區(qū)域進(jìn)行規(guī)避，以達(dá)到避開島嶼攻擊目標(biāo)的作戰(zhàn)目的。假設(shè)反艦導(dǎo)彈在遂行任務(wù)過程中保持高度不變、速度不變，而且考慮敵方防御區(qū)處于平坦地域，那么反艦導(dǎo)彈就無法利用地形因素進(jìn)行威脅規(guī)避機(jī)動(dòng)，航路規(guī)劃問題就可以被簡(jiǎn)化成為一個(gè)二維航路（也就是水平航路）規(guī)劃問題。很多學(xué)者通過對(duì)規(guī)劃空間進(jìn)行網(wǎng)格劃分形成連接起始點(diǎn)和目標(biāo)點(diǎn)的網(wǎng)絡(luò)圖[1-3]，然后采用搜索算法進(jìn)行航路尋優(yōu)。許多學(xué)者在這方面做了大量的工作，采用了許多智能搜索算法，如A*算法[4]、遺傳算法[5]、蟻群算法[6]、粒子群算法[7]等。JunMiura在文獻(xiàn)[8]中提出了基于SVM的新航路規(guī)劃方法，基于此，本文提出了SVM在反艦導(dǎo)彈中的應(yīng)用，同時(shí)本方法也適用于其他飛行器。

1 SVM 概述

支持向量機(jī)（SVM）是統(tǒng)計(jì)學(xué)習(xí)理論中最年輕的內(nèi)容，它包括支持向量分類機(jī)（SVC）和支持向量回歸機(jī)（SVR）。其中SVC是基于間隔最大化思想尋找最優(yōu)超平面的分類方法[9-10]。

給定一組線性可分樣本數(shù)據(jù)集

存在惟一的規(guī)范超平面(ω?x) +b=0，使得下式成立：

這樣通過超平面就使兩類樣本點(diǎn)落到平面H1:(ω?xi) +b=1和 H2:(ω?xi) +b=?1的兩側(cè)（或H1與H2上）。

而平面H1與平面H2之間的距離為它表示了兩類點(diǎn)被分開的程度。SVC就是要在式(1)條件下最大化ρ。求解該問題可以通過求解它的Wolfe對(duì)偶問題，即求解下面的二次規(guī)劃問題：

其中與樣本點(diǎn) xi對(duì)應(yīng)的αi滿足 αi≠0，則 xi叫支持向量，它在平面H1或H2上，是決定平面的向量。求得 α *后就得到了決策函數(shù) f (x)：

上面是在線性可分的情況下得到的，而很多情況下將是線性不可分劃。對(duì)于某些線性不可分問題，線性分劃造成的錯(cuò)分點(diǎn)可能比較少，這類問題稱為近似線性可分。此時(shí)我們使用軟間隔的辦法引入松弛變量iξ 來“軟化”約束條件(1)，

同時(shí)在目標(biāo)函數(shù)中引入懲罰參數(shù)C，得到如下對(duì)偶規(guī)劃問題：

求解結(jié)果非零 αi對(duì)應(yīng)了兩類支持向量，一是在平面H1和H2上的普通支持向量，此時(shí) 0＜αi＜C；另一種為兩平面間的邊界支持向量，此時(shí) αi=C。

當(dāng)訓(xùn)練集T的兩類樣本點(diǎn)集非線性可分時(shí)，SVC 通過引進(jìn)從輸入空間X 到另一個(gè)高維的Hilbert 空間H的變換 x ??(x)，將原輸入空間X的訓(xùn)練集轉(zhuǎn)化為Hilbert 空間H的新的訓(xùn)練集：使其在Hilbert 空間H 中線性可分。然后在空間H 中求得超平面(ω??(x))+ b=0，這個(gè)超平面可以硬線性分劃訓(xùn)練集。采用核函數(shù)K 滿足

可以避免在高維特征空間進(jìn)行的復(fù)雜運(yùn)算，解決了“維數(shù)災(zāi)難”。得到的決策函數(shù)為

2 SVM 在航跡規(guī)劃中的研究

引言中已經(jīng)將反艦導(dǎo)彈的航跡規(guī)劃問題簡(jiǎn)化成二維平面的障礙規(guī)避問題。此時(shí)，航路可以看成障礙中的安全走廊，這條安全走廊將障礙物分成了兩部分：一部分在航路的左邊；另一部分在航路的右方。因此，我們可以利用SVM 良好的分類能力，將這兩部分障礙分開，從而得到分界曲線作為航路。可以看出，要將SVM 應(yīng)用到航路規(guī)劃中來，首先，得對(duì)規(guī)劃空間進(jìn)行劃分，將規(guī)劃空間中的障礙規(guī)劃成兩類[3]；然后，應(yīng)用SVM的分類能力。本文直接以初始點(diǎn)與目標(biāo)點(diǎn)的連線為基準(zhǔn)線[8]。

2.1 障礙物的劃分

假設(shè)(x0,y0)為出發(fā)點(diǎn)，(xT,yT)為目標(biāo)點(diǎn)，則基準(zhǔn)線方程為：

式中：(x,y)為障礙的中心坐標(biāo)。

根據(jù)y的值，規(guī)劃空間中所有的障礙可以分成以下兩類：

正類障礙：y＞0；

負(fù)類障礙：y＜0。

若y=0，則根據(jù)具體的情況來分析：將它分成正類和負(fù)類各一次進(jìn)行規(guī)劃，若判別為正類時(shí)規(guī)劃出的航路短，則為正類，反之亦然。在航路規(guī)劃中，先將不互相覆蓋的威脅區(qū)域分離開，取它的周圍特征點(diǎn)來表示該威脅區(qū)域。如果兩個(gè)障礙區(qū)域有重疊現(xiàn)象，則可以將它們看成是一個(gè)障礙區(qū)域。如圖1中，障礙a 和b 重疊，故視為一個(gè)障礙。

圖1 障礙圖

2.2 SVM 規(guī)劃出的航路

利用SVM 對(duì)上面的兩類障礙物進(jìn)行規(guī)劃，得出判別決策函數(shù)式(7)。取

正類障礙區(qū)域：V≥1；

負(fù)類障礙區(qū)域：V≤?1；

安全航路區(qū)域（間隔區(qū)域）：?1＜V＜1。

我們希望目標(biāo)點(diǎn)和初始點(diǎn)都落在間隔區(qū)域中，這樣就可以尋找從出發(fā)點(diǎn)到目的點(diǎn)的航路，同時(shí)也確保了反艦彈最安全地飛行[8]。

2.3 輔助障礙點(diǎn)的選取

我們知道SVM 規(guī)劃出的間隔區(qū)域有可能是非連通的。為了盡量使出發(fā)點(diǎn)和目標(biāo)點(diǎn)落在同一間隔區(qū)域內(nèi)，我們加入了一些輔助障礙點(diǎn)引導(dǎo)間隔區(qū)域經(jīng)過出發(fā)點(diǎn)和目標(biāo)點(diǎn)。

輔助障礙點(diǎn)的選?。?/p>

1）在出發(fā)點(diǎn)和目標(biāo)點(diǎn)附近

為了確保間隔區(qū)域經(jīng)過出發(fā)點(diǎn)和目標(biāo)點(diǎn)，我們?cè)谒鼈儍蓚?cè)分別設(shè)了N個(gè)正類、負(fù)類障礙點(diǎn)，并且平行于標(biāo)準(zhǔn)線，如圖2所示。

圖2 障礙點(diǎn)和輔助點(diǎn)圖

2）中間輔助障礙點(diǎn)的選取

輔助障礙點(diǎn)的選取可以引導(dǎo)SVM 作出我們所需要的間隔區(qū)域。但是它畢竟是虛設(shè)的，所以不能影響實(shí)際存在的障礙。所以要以一定的距離平行標(biāo)準(zhǔn)線選取，本文取各類障礙距離標(biāo)準(zhǔn)線的平均距離dE，則兩類輔助障礙點(diǎn)的方程為：

3 仿真驗(yàn)證

在仿真過程中，選取規(guī)劃的區(qū)域是1×100km2正方形區(qū)域，設(shè)置了20個(gè)邊長(zhǎng)為400×m的正方形障礙，其中正方形障礙P是特別設(shè)定的，正好位于出發(fā)點(diǎn)和目標(biāo)點(diǎn)的連線上。其他的是隨機(jī)生成的障礙。在仿真過程中我們采用了高斯徑向基函數(shù)

作為SVM的核函數(shù)，其中P 選為10，C 選為300。仿真結(jié)果如圖3所示。

圖3 基于SVM的障礙分類圖

從而得到實(shí)際飛行航跡圖如圖4所示，此時(shí)SVM的支撐向量的個(gè)數(shù)為50個(gè)，占全部向量的41.7%。當(dāng)P 選為25，C 選為300，此時(shí)仿真結(jié)果如圖5所示，此時(shí)SVM的支撐向量的個(gè)數(shù)為20個(gè)，占全部向量的16.7%。

圖4 實(shí)際飛行航跡圖

圖5 實(shí)際飛行航跡圖

由圖5可以看出SVM 用于航跡規(guī)劃是可行的，雖然該方法不能保證航跡最短，但是在燃料條件等允許的條件下，它能保證飛行器最安全地在障礙間飛行，并且由SVM 規(guī)劃出的航跡還不必進(jìn)行光順處理。同時(shí)，也存在缺陷，就是有關(guān)核函數(shù)及其參數(shù)的選取對(duì)結(jié)果影響很大。

4 結(jié)論及展望

本文研究了SVM 在航路規(guī)劃中的應(yīng)用，從仿真結(jié)果來看，它是一種有效可行的方法，由它規(guī)劃出的航跡不必進(jìn)行光順處理。但同時(shí)，核函數(shù)及其參數(shù)的選取一直是SVM 問題中的難題，也將成為SVM 在航跡規(guī)劃中應(yīng)用的瓶頸。再者，本文僅研究了無威脅的障礙，對(duì)于其威脅性是有待進(jìn)一步研究的問題。

[1]柳長(zhǎng)安,李為吉,王和平.基于蟻群算法的無人機(jī)航路規(guī)劃[J].空軍工程大學(xué)學(xué)報(bào):自然科學(xué)版,2004,5(2):9-12.

[2]葉文,朱愛紅,范洪達(dá).低空突防航路規(guī)劃算法綜述[J].系統(tǒng)仿真學(xué)報(bào),2007,19(10):2357-2361.

[3]張雅妮,高金源.一種基于改進(jìn)A*算法的三維航跡規(guī)劃方法[J].飛行力學(xué),2008,26(1):48-51.

[4]范晨,王正杰.基于A*算法的飛行器三維航跡規(guī)劃研究[J].彈箭與制導(dǎo)學(xué)報(bào),2006,26(1):650-656.

[5]虞蕾,趙紅,趙宗濤.一種基于遺傳算法的航跡優(yōu)化方法[J].西北大學(xué)學(xué)報(bào):自然科學(xué)版,2006,36(2):205-213.

[6]李棟,曹義華,蘇媛,等.基于改進(jìn)蟻群算法的低空突防航跡規(guī)劃[J].北京航空航天大學(xué)學(xué)報(bào),2006,32(3):258-262.

[7]陳冬,周德云,馮琦.基于粒子群優(yōu)化算法的無人機(jī)航跡規(guī)劃[J].彈箭與制導(dǎo)學(xué)報(bào),2007,27(4):340-342.

[8]JUN MIURA.Support Vector Path Planning[C]//Proceedings of the 2006 IEEE/RSJ.International Conference on Intelligent Robots and Systems,BJ:IEEE Press,2006:2894-2899.

[9]鄧乃揚(yáng),田英杰.數(shù)據(jù)挖掘中的新方法——支持向量機(jī)[M].北京:科學(xué)出版社,2004.

[10]VAPNIK V N.Statistical Learning Theory[M].John Wiley &Sons,New York,1998.