人工蜂群算法的無人機航路規(guī)劃與平滑

劉敏，鄒杰，馮星，趙振宇

(1.光電控制技術(shù)重點實驗室，河南洛陽 471009;2.中航工業(yè)洛陽光電設(shè)備研究所，河南洛陽 471009)

人工蜂群算法的無人機航路規(guī)劃與平滑

劉敏1，2，鄒杰1，2，馮星1，2，趙振宇1，2

(1.光電控制技術(shù)重點實驗室，河南洛陽 471009;2.中航工業(yè)洛陽光電設(shè)備研究所，河南洛陽 471009)

航路規(guī)劃是無人機(UAV)作戰(zhàn)任務(wù)規(guī)劃系統(tǒng)的關(guān)鍵組成部分，目標是在適當(dāng)?shù)臅r間內(nèi)為UAV計算出最優(yōu)或次最優(yōu)的飛行航路.人工蜂群(ABC)算法是一種最新發(fā)展的模擬昆蟲王國中蜜蜂群體尋找優(yōu)良蜜源的群體智能優(yōu)化算法.采用人工蜂群算法完成無人機的平滑航路規(guī)劃，首先闡述了人工蜂群算法的基本原理，然后將無人機航路規(guī)劃問題通過建模轉(zhuǎn)換成為一個多維函數(shù)優(yōu)化問題，利用人工蜂群算法的優(yōu)勢，找到多維函數(shù)的最優(yōu)解，最后對優(yōu)化后的航路進行了平滑，使UAV對規(guī)劃后的航路可飛.仿真實驗結(jié)果表明，此方法可有效規(guī)劃出航路，且所規(guī)劃的航路可飛.

無人機;航路規(guī)劃;人工蜂群算法;平滑

航路規(guī)劃是無人機(unmanned aerial vehicle，UAV)作戰(zhàn)任務(wù)規(guī)劃系統(tǒng)的關(guān)鍵組成部分［1］，目標是在適當(dāng)?shù)臅r間內(nèi)為UAV計算出最優(yōu)或次優(yōu)的飛行航路，這個航路能使UAV突破敵方威脅環(huán)境，并且在完成任務(wù)目標的同時自我生存.航路規(guī)劃時需要考慮地形、數(shù)據(jù)、威脅信息、燃油和時間約束等.“運籌帷幄之中，決勝千里之外”自古就是軍事家們追求的目標，航路規(guī)劃的出現(xiàn)為實現(xiàn)這一目標提供了有力的技術(shù)支持.隨著航路規(guī)劃技術(shù)在“戰(zhàn)斧”等巡航導(dǎo)彈上的成功應(yīng)用，航路規(guī)劃方法研究日益受到世界各國的重視.

人工蜂群算法(artificial bee colony，ABC)是一種最新發(fā)展的模擬昆蟲王國中蜜蜂群體尋找優(yōu)良蜜源的仿生優(yōu)化算法［2］.它是建立在蜜蜂自組織模型和群體智能基礎(chǔ)上的一種計算方法，主要從蜜蜂實現(xiàn)采蜜的群體智能行為中得到啟發(fā).盡管人工蜂群算法的研究和應(yīng)用還處于初級階段，但由于算法的控制參數(shù)少、易于實現(xiàn)、計算方便等優(yōu)點［3］，已經(jīng)被越來越多的學(xué)者所關(guān)注;相對于蟻群算法、遺傳算法、微粒群算法等其他仿生智能算法，人工蜂群具有很好的全局搜索能力和局部搜索能力，不易陷入局部最優(yōu)，易收斂等優(yōu)點［4］，已被廣泛地應(yīng)用于函數(shù)優(yōu)化、圖像處理、神經(jīng)網(wǎng)絡(luò)訓(xùn)練等領(lǐng)域中，并取得了很多不錯的研究成果.

采用人工蜂群算法完成無人機的平滑航路規(guī)劃，首先將無人機航路規(guī)劃問題通過建模轉(zhuǎn)換成為一個多維函數(shù)優(yōu)化問題，然后利用人工蜂群算法的優(yōu)勢，找到多維函數(shù)的最優(yōu)解，最后對優(yōu)化后的航路進行了平滑，使UAV對規(guī)劃后的航路可飛.仿真實驗結(jié)果表明，所研究的方法可有效規(guī)劃出航路，且所規(guī)劃的航路可飛.

1 人工蜂群算法基本原理

1.1 算法起源

諾貝爾獎得主奧地利人K.Von Frisch發(fā)現(xiàn)，在自然界中，雖然各社會階層的蜜蜂只能完成單一的任務(wù)，但是蜜蜂通過搖擺舞、氣味等多種信息交流方式，使得整個蜂群總是能很自如地發(fā)現(xiàn)優(yōu)良蜜源(或花粉)，實現(xiàn)自組織行為(如圖1所示).

圖1 蜜蜂跳搖擺舞Fig.1 Sketch map of swing dancing bees

在自然界中，蜜蜂沿直線爬行，然后再向左這樣一種舞蹈，其動線呈8字型，并搖擺其腹部，舞蹈的中軸線與地心引力的夾角 正好表示蜜源方向和太陽方向的夾角α;蜜蜂跳舞擺尾的時間表示蜂巢距離蜜源的遠近;在蜂巢內(nèi)的蜜蜂根據(jù)搖擺舞得到的信息，選擇蜜源去采蜜或者在附近重新尋找新的蜜源.蜜蜂之間通過這種相互之間的信息交流、學(xué)習(xí)，使得整個蜂群總能找到較優(yōu)的蜜源進行采蜜.土耳其Erciyes大學(xué)的D.Karaboga于2005年提出了人工蜂群算法［5］，該算法最初應(yīng)用于多峰值函數(shù).

1.2 算法基本原理

蜂群實現(xiàn)采蜜的集體智能行為包含3個基本部分:蜜源、采蜜蜂EF、待工蜂UF，此外引入3種基本的行為模式:搜索蜜源、為蜜源招募和放棄蜜源［4］.

1)蜜源(food sources).

蜜源代表解空間范圍內(nèi)各種可能的解，蜜源值取決于多種因素，諸如蜜源與蜂巢的接近程度、蜜源內(nèi)的大小和集中程度以及提取該能量的容易程度.在多峰函數(shù)求極值中，與函數(shù)值有關(guān)，用數(shù)字量“收益度”衡量蜜源.

2)采蜜蜂(employed foragers).

采蜜蜂同具體的蜜源聯(lián)系在一起，采蜜蜂通過搖擺舞與其他蜜蜂分享這些信息，并按照收益度等因素，一部分成為引領(lǐng)蜂.

3)待工蜂(unemployed foragers).

正在尋找蜜源采集，可以分為偵查蜂和跟隨蜂2種;偵查蜂搜索新蜜源，跟隨蜂在巢內(nèi)等待，通過分享EF的信息來找到蜜源.

此外，引入3種基本的行為模式:搜索蜜源(search)、為蜜源招募(recruit)、放棄蜜源(abandon).如圖2所示，假設(shè)有2個已經(jīng)發(fā)現(xiàn)的蜜源:A、B，剛開始時，待工蜂沒有關(guān)于蜜源的任何信息，有2種選擇:

1)待工蜂作為偵查蜂，自發(fā)尋找蜂巢附近的蜜源(‘S’線);

2)在觀察到其他蜜蜂的搖擺舞之后(分享信息)可以被招募，并按照獲得的信息尋找蜜源(‘R’線).

待工蜂發(fā)現(xiàn)新的蜜源之后，蜜蜂記住蜜源的位置，并迅速采蜜，因此待工蜂變成了采蜜蜂.蜜蜂采完蜜之后回到蜂箱，有以下3種選擇:

1)放棄蜜源(收益度不高)，成為待工的跟隨蜂(UF);

2)跳搖擺舞招募蜂巢其他伙伴(EF1);

3)不招募蜜蜂，繼續(xù)采蜜(EF2).

圖2 人工蜂群算法原理Fig.2 Sketch map of principles of the ABC

初始時刻，所有蜜蜂沒有任何先驗知識，其角色都是偵查蜂.隨機搜索到蜜源后，根據(jù)蜜源收益度相對大小，偵查蜂可以轉(zhuǎn)換為上述任何一種蜜蜂，其轉(zhuǎn)變原則如下:當(dāng)所采集食物源收益度排名高于臨界時，成為引領(lǐng)蜂，繼續(xù)采蜜，并招募更多蜜蜂采蜜(EF1);食物源收益度相對很低時，放棄該食物源，再次成為偵查蜂搜尋食物源(UF);所采集食物源收益度排名小于臨界值時，可以成為跟隨蜂，前往相應(yīng)的食物源采蜜;當(dāng)在蜜源周圍搜索次數(shù)超過極限，但仍未找到較優(yōu)的蜜源時，放棄該蜜源，并去尋找新的蜜源.

在整個群體智慧的形成過程中，蜜蜂間交換信息是最為重要的一環(huán).引領(lǐng)蜂通過搖擺舞的持續(xù)時間等來表現(xiàn)食物源的收益率，收益率與食物源被選擇的可能性成正比.因而，蜜蜂被招募到某一個食物源的概率與食物源的收益率成正比.在整個尋找最優(yōu)解的過程中，引領(lǐng)蜂有保持優(yōu)良花蜜源的作用;跟隨蜂增加優(yōu)良花蜜源對應(yīng)的蜜蜂數(shù)目，起到提高算法收斂速度的作用;偵察蜂隨機搜索新花蜜源，能幫助算法跳出局部最優(yōu).正是通過這種信息交流方式，蜜蜂發(fā)揮群體智能，總能找到較優(yōu)的蜜源位置.相對于其他諸如遺傳算法、粒子群算法，人工蜂群算法最大的優(yōu)點是它在每次迭代都進行局部搜索，因此找到最優(yōu)參數(shù)的概率也大大增加.

2 UAV航路規(guī)劃建模

航路規(guī)劃是無人機作戰(zhàn)任務(wù)規(guī)劃系統(tǒng)的關(guān)鍵組成部分，目標是在適當(dāng)?shù)臅r間內(nèi)為無人機計算出最優(yōu)或次最優(yōu)的飛行航路，這個航路能使無人機突破敵方威脅環(huán)境，并且在完成任務(wù)目標的同時自我生存.航路規(guī)劃時需要考慮地形、數(shù)據(jù)、威脅信息、燃油和時間約束等［6］.

2.1 航路規(guī)劃問題建模

如圖3，將原坐標系轉(zhuǎn)換為以起始點到目標點連線為橫軸的新的坐標軸系［7］，坐標轉(zhuǎn)化公式如式(1)所示，其中(x，y)為點在原地面坐標系OXY下的坐標，(x'，y')為該點在旋轉(zhuǎn)坐標系OX'Y'下的坐標值，θ為坐標系的旋轉(zhuǎn)角度.

圖3 航路規(guī)劃原理Fig.3 Schematic diagram of trajectory planning

然后將X'軸D等分，對每個節(jié)點垂線上相應(yīng)的Y'坐標進行優(yōu)化，得到一組由D個點的縱向坐標組成的點列，顯然，這些點的橫坐標很容易得到.將這些點按順序連接在一起，就組成了一條路徑，這樣就把航路規(guī)劃問題轉(zhuǎn)換成了一個D維函數(shù)優(yōu)化問題.

2.2 航路優(yōu)化性能指標

無人機航路規(guī)劃是根據(jù)任務(wù)目標規(guī)劃出滿足某種性能指標最優(yōu)的飛行航路，其性能指標主要包括完成規(guī)定任務(wù)的安全性能指標和燃油性能指標［8］，即威脅代價最小性能指標和燃油代價最小性能指標.

威脅代價最小性能指標為

油耗代價最小性能指標為

則UAV航路的總性能指標為

式中:wt表示航路上各點的威脅代價;wf表示航路上各點的油耗代價，是航路長度的函數(shù)(仿真中，wf≡1)L為航路的長度;k∈［0，1］，表示安全性能與燃油性能的權(quán)衡系數(shù)，其值可根據(jù)UAV所執(zhí)行的任務(wù)而定，如果任務(wù)重視飛行時的安全性，則k選擇較大的值;如果任務(wù)需要飛機的快速性，則k選擇較小的值.總之，加權(quán)的大小取決于權(quán)項的重要性和可行性的綜合指標.

2.3 威脅代價的計算

當(dāng)無人機沿路徑Li，j飛行時，Nt個威脅源對其產(chǎn)生的總的威脅代價為

為了簡化計算，如圖4所示［9］，把每條邊等分為5段，取其中的5個點來計算這條邊所受到的威脅代價，若威脅點到該邊的距離在威脅半徑之內(nèi)，則按下列公式計算它的威脅代價:

式中:Lij為連接節(jié)點i，j邊的長度;d0.1，k表示Lij邊上的1/10分點距第k個威脅源中心的距離;tk為威脅源的威脅等級.

另外，由于燃油代價與航程有關(guān)，故可以簡單認為wf=L，則對每一條邊的燃油代價有=Lij.

圖4 威脅代價的計算Fig.4 Calculation of threat costs

3 UAV航路規(guī)劃與平滑

利用人工蜂群算法進行無人機平滑航路規(guī)劃的具體實現(xiàn)步驟如下:

1)初始化算法參數(shù)，并根據(jù)所給的任務(wù)和威脅信息，建立旋轉(zhuǎn)坐標系，將戰(zhàn)場威脅信息轉(zhuǎn)化到旋轉(zhuǎn)坐標系上，轉(zhuǎn)換公式如式(1)所示，將旋轉(zhuǎn)坐標系的橫軸D等分，每一個可行解都由D個由浮點數(shù)表示的坐標組成的數(shù)列，可記為P={p1，p2，…，pD};

2)在戰(zhàn)場范圍允許的條件下，隨機產(chǎn)生M條初始路徑作為初始蜜源，根據(jù)戰(zhàn)場上各個威脅的信息，計算每一條可行路徑的代價值，如式(2);

3)采蜜蜂在初始蜜源周圍進行搜索更優(yōu)的路徑，若找到路徑更優(yōu)，直接替換原路徑;

4)跟隨蜂根據(jù)采蜜蜂搜索到的路徑的威脅值大小，按概率選擇威脅值較小的蜜源(路徑)，在其周圍進行搜索路徑，若找到路徑更優(yōu)，則直接替換原路徑;

5)找出所有路徑中威脅值最小的路徑進行標記;

6)若某一蜜源附近的搜索次數(shù)已經(jīng)達到上限，仍沒找到更優(yōu)的路徑，則放棄該蜜源，重新隨機初始化一條新的路徑;

7)若迭代次數(shù)大于最大迭代次數(shù)，則退出循環(huán)，否則轉(zhuǎn)入3)，進入下一迭代;

8)將最終得到的最優(yōu)路徑坐標進行坐標反變換，并輸出;

9)對路徑進行平滑操作，平滑半徑和圓心的設(shè)置見式(3)和(4)，選取圓弧上的點作為平滑航路，并在圖中顯示所得路徑.

不同的航路規(guī)劃算法所產(chǎn)生的各種航路分成以下4類:

1)第1類航路是不連續(xù)的，平滑程度最低，存在位置的突變奇異點，這類型曲線顯然是不可飛航路;

2)第2類曲線是連續(xù)的曲線，但是曲線中存在切線方向的突變;

3)第3類曲線不僅連續(xù)，而且切線方向角也連續(xù)，這種航路較為光滑;

4)第4類曲線是最為光滑的航路，航路曲線的曲率也是連續(xù)的，性能非常好，但這類曲線的算法比較復(fù)雜，在實際系統(tǒng)中一般不予以采用.

利用人工蜂群算法規(guī)劃出的無人機飛行航路屬于第2類曲線，曲線本身是連續(xù)的，但是在節(jié)點處不可微，實際中對UAV而言不是一條可飛的航路，因此對已經(jīng)規(guī)劃出的航路還要經(jīng)平滑處理使之成為連續(xù)可微的航線.

航路平滑的主要目的是:應(yīng)用數(shù)學(xué)的方法，去掉凹凸點，使得搜索出的最優(yōu)航路不僅連續(xù)，并且它的一階導(dǎo)數(shù)也連續(xù)，使搜索出來的曲線成為第3類曲線.

考慮如圖 5 所示的航路［10］，該航路由wi－1、wi和wi+1組成.很明顯，航路在節(jié)點wi處存在切向突變，對UAV而言是不可飛路段，必須對其進行平滑.

圖5 UAV航路點平滑F(xiàn)ig.5 Smoothing to UAV trajectory point

可令 qi表示從wi－1到wi的單位向量，qi+1為從wi到wi+1的單位向量，則有

令 β 表示向量 qi與 qi+1的夾角，則 β=arccos(－qi+1·qi).C表示內(nèi)切圓，其半徑可表示為

顯然，內(nèi)切圓C的圓心在2條折線夾角的平分線上，因此，圓心Ci的坐標可表示為

利用人工蜂群算法進行無人機航路規(guī)劃的基本流程如圖6所示.

圖6 UAV航路規(guī)劃算法流程Fig.6 Trajectory planning algorithm process of UAV

4 仿真算例分析

設(shè)定UAV飛行任務(wù)的戰(zhàn)場環(huán)境如表1所示，仿真軟件的運行環(huán)境為 Windows XP，使用 Matlab2009b進行仿真分析.

表1 任務(wù)設(shè)置Table 1 Task setting

設(shè)置采蜜蜂數(shù)量為30，跟隨蜂數(shù)量為30，最大搜索極限30，函數(shù)優(yōu)化維數(shù)為12，最大迭代次數(shù)為100，威脅類型包括高炮、導(dǎo)彈、雷達、禁飛區(qū)，仿真結(jié)果如圖7～9所示.

圖7 航路規(guī)劃結(jié)果(平滑前)Fig.7 Trajectory planning results(before smoothing)

圖8 航路規(guī)劃結(jié)果(平滑后)Fig.8 Trajectory planning results(after smoothing)

圖9 人工蜂群算法收斂曲線Fig.9 Convergence curve of ABC algorithm

圖7為基于人工蜂群算法的航路規(guī)劃結(jié)果，可以看出，航路段與段之間存在不可微的情況，即不可飛點，不能滿足無人機的飛行性能約束，經(jīng)過本文的平滑策略處理后，見圖8，航路變得較為光滑，可以滿足無人機的飛行要求.通過圖9可以看出，基于人工蜂群的算法在第9次迭代時出現(xiàn)了快速收斂的現(xiàn)象，第16代的規(guī)劃結(jié)果已經(jīng)達到了可飛解的效果，表明改算法具有比較快的收斂速度.由以上結(jié)果表明，人工蜂群算法在解決無人機平滑航路規(guī)劃問題時具有可靠性和有效性.下一步，將進一步開展基于動態(tài)威脅的人工蜂群航路規(guī)劃研究，滿足機載實時重規(guī)劃的要求.

5 結(jié)束語

采用人工蜂群算法完成無人機的平滑航路規(guī)劃，首先將無人機航路規(guī)劃問題通過建模轉(zhuǎn)換成為一個多維函數(shù)優(yōu)化問題，然后利用人工蜂群算法的優(yōu)勢，找到多維函數(shù)的最優(yōu)解，最后對優(yōu)化后的航路進行了平滑，使UAV對規(guī)劃后的航路可飛.仿真實驗結(jié)果表明，所研究的方法可有效規(guī)劃出航路，且所規(guī)劃的航路可飛.

［1］田偉.無人作戰(zhàn)飛機航路規(guī)劃研究［D］.西安:西北工業(yè)大學(xué)，2007:10－13.

TIAN Wei.Research on the path planning for unmanned combat air vehicle［D］.Xi’an:Northwestern Polytechnical University，2007:10－13.

［2］KARABOGA D，BASTURK B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm［J］.Journal of Global Optimization，2007，39(3):459－471.

［3］KARABOGA D，BASTURK B.On the performance of artificial bee colony(ABC)algorithm［J］.Applied Soft Computing，2008，8(1):687－697.

［4］HU C L，SUN T Y.Reliable multi－goal route planning for vehicle using skeletonization and genetic algorithms［C］//Proc 2008 CACS International Automatic Control Conference.［S.l.］，2008:159－263.

［5］KARABOGA D.An idea based on honey bee swarm for numerical optimization technical report 06［R］.Erciyes University，2005.

［6］柳長安，李為吉，王和平.基于蟻群算法的無人機航路規(guī)劃［J］.空軍工程大學(xué)學(xué)報:自然科學(xué)版，2004，2(5):9－12.

LIU Chang’an，LI Weiji，WANG Heping.Path planning for reconnaissance UAV based on ant algorithm［J］.Journal of Air Force Engineering University:Natural Science Edition，2004，2(5):9－12.

［7］王斌，陳知秋，林棟.基于遺傳算法的無人機航路規(guī)劃與建模仿真［J］.吉林工程技術(shù)師范學(xué)院學(xué)報，2010，(03):8－11.

WANG Bin，CHEN Zhiqiu，LIN Dong.Based on genetic algorithm for UAV route planning and modeling and simulation［J］.Journal of Jilin Teachers Institute of Engineering and Technology，2010(3):8－11.

［8］XU Chunfang，DUAN Haibin，LIU Fang.Chaotic artificial bee colony approach to uninhabited combat air vehicle(UCAV)［J］.Aerospace Science and Technology，2010，14(8):535－541.

［9］ANDERSON E P，BEARD R W，MCLAIN T W.Real－time dynamic trajectory smoothing for unmanned air vehicles［J］.IEEE Transactions on Control Systems Technology，2005，13(3):471－477.

劉敏 ，女，1980年生，工程師，主要研究方向為仿生智能計算、無人機航路規(guī)劃.

Smooth trajectory planning of an unmanned aerial vehicle using an artificial bee colony algorithm

LIU Min1，2，ZOU Jie1，2，F(xiàn)ENG Xing1，2，ZHAO Zhenyu1，2

(1.Science and Technology on Electro－optic Control Laboratory，Luoyang 471009，China;2.Luoyang Institute of Electro－Optical E－quipment，AVIC，Luoyang 471009，China)

Trajectory is a key issue for an unmanned aerial vehicle(UAV)，which aims to obtain an optimal or suboptimal trajectory within proper time.The artificial bee colony(ABC)is a new algorithm based on how a bee colony finds food.On the basis of introducing the basic principle of the ABC，and the description of threatening models of a UAV，the UAV trajectory planning was transformed into an optimization problem through modeling.Then the optimal solution of the multi－dimensional function was given by taking advantage of the artificial bee colony algorithm.Finally，the smoothing strategy was adopted to obtain a feasible path.The feasibility and effectiveness of the proposed approach was verified by experimental results.

unmanned aerial vehicle(UAV);trajectory planning;artificial bee colony(ABC)algorithm;smoothing

TP18;V19

A

1673－4785(2011)04－0344－06

10.3969/j.issn.1673－4785.2011.04.011

2011－01－28.

總裝重點實驗室基金資助項目(9140C460104091301).

劉敏.E－mail:chenshuizhong@gmail.com.