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

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

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

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

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

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

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

無人機;航路規劃;人工蜂群算法;平滑

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

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

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

1 人工蜂群算法基本原理

1.1 算法起源

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

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

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

1.2 算法基本原理

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

1)蜜源(food sources).

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

2)采蜜蜂(employed foragers).

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

3)待工蜂(unemployed foragers).

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

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

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

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

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

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

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

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

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

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

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

2 UAV航路規劃建模

航路規劃是無人機作戰任務規劃系統的關鍵組成部分，目標是在適當的時間內為無人機計算出最優或次最優的飛行航路，這個航路能使無人機突破敵方威脅環境，并且在完成任務目標的同時自我生存.航路規劃時需要考慮地形、數據、威脅信息、燃油和時間約束等［6］.

2.1 航路規劃問題建模

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

圖3 航路規劃原理Fig.3 Schematic diagram of trajectory planning

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

2.2 航路優化性能指標

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

威脅代價最小性能指標為

油耗代價最小性能指標為

則UAV航路的總性能指標為

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

2.3 威脅代價的計算

當無人機沿路徑Li，j飛行時，Nt個威脅源對其產生的總的威脅代價為

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

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

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

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

3 UAV航路規劃與平滑

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

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

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

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

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

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

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

7)若迭代次數大于最大迭代次數，則退出循環，否則轉入3)，進入下一迭代;

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

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

不同的航路規劃算法所產生的各種航路分成以下4類:

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

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

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

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

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

航路平滑的主要目的是:應用數學的方法，去掉凹凸點，使得搜索出的最優航路不僅連續，并且它的一階導數也連續，使搜索出來的曲線成為第3類曲線.

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

圖5 UAV航路點平滑Fig.5 Smoothing to UAV trajectory point

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

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

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

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

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

4 仿真算例分析

設定UAV飛行任務的戰場環境如表1所示，仿真軟件的運行環境為 Windows XP，使用 Matlab2009b進行仿真分析.

表1 任務設置Table 1 Task setting

設置采蜜蜂數量為30，跟隨蜂數量為30，最大搜索極限30，函數優化維數為12，最大迭代次數為100，威脅類型包括高炮、導彈、雷達、禁飛區，仿真結果如圖7～9所示.

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

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

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

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

5 結束語

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

［1］田偉.無人作戰飛機航路規劃研究［D］.西安:西北工業大學，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］柳長安，李為吉，王和平.基于蟻群算法的無人機航路規劃［J］.空軍工程大學學報:自然科學版，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］王斌，陳知秋，林棟.基于遺傳算法的無人機航路規劃與建模仿真［J］.吉林工程技術師范學院學報，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年生，工程師，主要研究方向為仿生智能計算、無人機航路規劃.

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

LIU Min1，2，ZOU Jie1，2，FENG 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.