基于HME-ABC 算法的多無人直升機時間協同航路規劃

韓增亮 陳 謀 朱豪杰 吳慶憲

在軍事領域,UAH 憑借其能夠在復雜危險環境工作的出色能力,成為近年來最具發展前景和挑戰的軍事裝備之一[1].隨著現代空戰技術的不斷發展,軍事偵察與打擊任務的復雜性日益增加,單機偵察與打擊模式已無法滿足當前的軍事任務需求,多機協同作戰成為UAH 在戰場作戰的主要形式.航路規劃作為UAH 協同作戰的基礎,能夠為每架UAH 提供一條安全無碰撞的最優飛行航路,使UAH 編隊能夠安全有效地完成預定任務[2].因此,高效合理的協同規劃技術便成為了任務能否成功的關鍵.

學者們提出了一系列方法來處理UAH 的航路規劃問題,例如人工勢場（artificial potential field,APF）算法、A* 算法、Voronoi 圖算法以及快速探索隨機樹（rapidly-exploring random tree,RRT）算法等[3-6].上述優化算法在處理具有復雜約束的航路規劃問題時,普遍存在搜索時間長、易陷入局部最優等問題.隨著計算智能的提出與發展,群智能算法逐漸成為解決航路規劃問題的熱門方向.文獻[7]提出了一種具有貪婪啟發機制的遺傳算法,通過對風速與風向的評估規劃無人機三維緊急降落航路規劃問題;文獻[8]提出了一種基于量子粒子群優化的混合差分進化（quantum-particle swarm optimization,Q-PSO）算法,利用不同算法的融合為海上UAV 提供了飛行航路方案;文獻[9]提出了一種改進的離散粒子群優化（discrete-particle swarm optimization,DPSO）算法,通過采用確定性初始化、隨機突變和邊緣交換等方式來求解耦合旅行商問題.伴隨著空戰環境日益復雜,一系列新型群智能優化算法被提出并應用于航路規劃問題,例如人工蜂群（artificial bee colony,ABC）算法、狼群搜索（wolf pack search,WPS）算法、混合蛙跳（shuffled frog leaping,SFL）算法和杜鵑搜索（cuckoo search,CS）算法等[10-13].同時,隨著群智能算法的深入研究與發展,其改進型算法成為了協同航路規劃問題的熱門研究方向,見文獻[14-18].通過大量的文獻分析可以看出,無論單UAV 還是多UAV 很多研究都僅限于空間上的航路規劃,這些方法更多地注重于航路避碰,卻忽略了對于時間協同的考慮.然而對于多機聯合作戰任務,往往需要多架UAV 能夠在規定時間約束下從不同的起點同時飛至指定的任務區域,使其能在有效時間窗口下協同執行偵察或打擊任務.這就需要UAV 編隊的飛行航路要滿足時間協同性的要求.因此,時間上的協同便成為了UAV 聯合作戰任務成功關鍵因素,所以為UAH 編隊規劃出帶有時間協同約束的飛行航路就顯得極其重要.

本文針對多UAH 時間協同航路規劃問題,研究了一種基于異維記憶進化策略的人工蜂群協同航路算法,利用蜂群的記憶模式與信息交互能力設計了異維記憶知識庫用來取代傳統ABC 算法單一隨機的搜索方式,有效地降低了蜂群的無效搜索,在減少優化迭代次數的同時顯著提高了協同航路的優化效率.

1 航路規劃問題建模

1.1 問題描述

多UAH 時間協同航路規劃要求每架UAH 根據任務需求,從不同起點出發并同時到達目標區域執行任務.UAH 編隊在飛行過程中可能面臨著地形與防空武器的威脅,規劃的航路須避開上述威脅區域并滿足UAH 的機動性能約束.

圖1 多UAH 協同航路規劃問題模型Fig.1 Model of multi-UAH coordinated flight path planning problem

由于對規劃空間進行了垂直分割操作,航路點的尋找范圍從整個三維規劃空間可以縮小為N-1 個二維平面.對于每個二維平面,航路點的表征方式可以轉換為.因此,多UAH 時間協同航路規劃問題的優化變量E 可以被定義為:

所有航路點應滿足地圖邊界的約束,即[8]

1.2 航路代價分析

1.2.1 油耗代價

更短的飛行航路意味著更少的燃油消耗、更短的飛行時間和更安全的飛行包線.因此,油耗代價Jl可以描述為[18]:

其中,k=1,2,…,N,N 為航路點數量,v 為UAH 的飛行速度,lk為第k 條子航跡長度,ρ 為UAH 平均油耗.

1.2.2 威脅代價

如圖2 所示,將威脅區域簡化為半徑為R 的半球體,航路威脅代價Jt可以描述為[19]:

圖2 威脅代價計算示意圖Fig.2 Schematic diagram of threat cost calculation

1.2.3 高度代價

在保證UAH 安全飛行的前提下,降低其飛行高度可以提高UAH 的隱蔽性,如圖3 所示.因此,航路的高度代價Ja可以描述為[19]:

圖3 高度代價計算示意圖Fig.3 Schematic diagram of altitude cost calculation

1.3 航路約束分析

1.3.1 UAH 性能約束

UAH 的性能約束主要為偏航角約束與俯仰角約束,性能約束項可以表示為:

1.3.2 航路安全約束

航路安全性主要體現在UAH 與地形是否發生碰撞和UAH 之間是否發生碰撞.因此,航路安全約束可以表示為:

協同航路規劃還需考慮不同的UAH 之間的航路避碰問題.首先考慮航路i 上的航路點m 與航路j上的航路點n 之間的距離是否小于預設安全距離.

1.3.3 航路協同能力

多UAH 協同航路規劃的時間協同性要求每架UAH 應具有相同的編隊預計到達時間（estimate time arrival,ETA）.如圖4 所示,UAH 編隊中每架UAH 的速度范圍為,則第i 架UAH 的飛行時間段為:

圖4 時間協同窗口示意圖Fig.4 Schematic diagram of the time synergy window

當第i 架UAH 和第j 架UAH 存在時間協同的可能性,則這兩架UAH 沿航路飛行的時間應滿足以下關系:

若兩架UAH 飛行時間段的相交區間與兩時間段中較小時間段長度之比不小于,則

2 多UAH 時間協同航路規劃算法

2.1 多UAH 時間協同航路規劃框架

多UAH 時間協同航路規劃要求UAH 編隊從不同起點出發,并在合理的時間窗口內飛至任務區域.圖5 為多UAH 時間協同航路規劃框架,該框架將多UAH 航路規劃被轉化為單UAH 航路規劃,通過時間約束調整各架UAH 飛行速度,計算時間協同變量ETA,從而為UAH 編隊規劃出滿足時間窗口的飛行路徑.

圖5 時間協同航路規劃框架Fig.5 Framework of time-coordinated flight path planning

2.2 基于HME-ABC 算法的多UAH 時間協同航路規劃

為了提高多UAH 時間協同航路規劃問題的結算效率與規劃質量,本文根據蜂群的聯想記憶能力提出了一種基于HME-ABC 算法.通過異維記憶知識庫的引導進化降低了蜂群的無效搜索過程,提高ABC算法的收斂速度和優化效率,為UAH 編隊快速高效地規劃出時間協同飛行航路.詳細的基于HME-ABC算法的多UAH 時間協同航路規劃過程如下所示.

2.2.1 建立協同航路規劃目標函數

根據戰場環境配置與協同任務需求構建協同航路規劃問題模型.考慮到協同航路的綜合代價與約束,多UAH 時間協同航路規劃目標函數可以描述為:

2.2.2 算法初始化

每個蜜源位置代表一個UAH 的候選航路點,設置雇傭蜂和觀察蜂數量為SN,采用D 維向量來描述第i 個蜜源的位置信息,通過式（26）在規劃空間中初始化蜜源位置[19].

2.2.3 HME-ABC 算法優化過程

1）雇傭蜂階段

a）基于種群信息引導的平衡進化方式

該進化方式利用了種群中不同質量個體的綜合信息,個體在決定更新行為時充分考慮了自身、當前最優個體和其他個體的影響.基于種群信息引導的平衡進化方式如下:

其中,fit（xi）為當前個體的適應度函數.個體適應度值計算方式如下[14]:

其中,obj（x）為備選解x 的目標函數值.

b）基于異維記憶機制的進化方式

考慮到蜂群進化存在失敗概率的問題,本節為進化失敗的雇傭蜂設計了一種基于異維記憶機制的進化方式,利用蜜蜂的記憶能力將進化成功經驗應用于UAH 航路點的搜索.

圖6 記憶知識庫Fig.6 Memory knowledgebase

針對于進化失敗的個體,將給予其二次進化的機會.為提高航路規劃的成功率,二次進化階段將借鑒記憶知識庫中的成功案例對其進行指導.

如圖7 所示,二次進化所需的信息將不再從種群中獲得,取而代之的是記憶知識庫中的成功經驗.考慮到算法需平衡開發與探索能力,設計了如下的進化方式:

圖7 二次進化示意圖Fig.7 Schematic diagram of secondary evolution

HME-ABC 算法的雇傭蜂階段流程如下.

2）觀察蜂階段

觀察蜂通過雇傭蜂所分享的信息,根據蜜源質量采用輪盤賭策略選擇合適的蜜源進行開采.跟隨概率Pi（x）可表示為[19]:

其中,fiti（x）為第i 個蜜源的適應度.

3）偵察蜂階段

傳統的ABC 算法采用初始化策略作為偵察蜂的進化方式,搜索方向的隨機性可能會降低新蜜源的開發效率.為此,將根據記憶知識庫的進化經驗,設計一種基于跨越式搜索的偵察蜂更新策略.

如圖8 所示,偵察蜂從記憶知識庫中選擇兩例成功進化經驗,其對應的蜜源位置中心作為新蜜源位置,該過程可描述為:

圖8 偵察蜂搜索策略Fig.8 Strategy of scout bee search

2.2.4 協同航路ETA 計算

當HME-ABC 算法滿足迭代終止條件,便輸出最終的全局最優UAH 編隊航路點序列.根據所規劃出的候選航路的長度,協調各架UAH 的飛行速度,利用式（22）和式（23）計算出航路協同ETA.最終的規劃結果為UAH 編隊的飛行航路與協同時間窗口.

基于HME-ABC 算法的多UAH 時間協同航路規劃流程如圖9 所示.

圖9 HME-ABC 算法流程圖Fig.9 Flow chart of HME-ABC algorithm

2.3 計算復雜度分析

HME-ABC 算法的計算復雜度由初始化階段復雜度與優化階段復雜度組成,具體計算如下[19].

1）初始化階段

2）算法優化階段

其中,O（·）表示算法漸進時間復雜度,n 代表輸入數據的量.

初始化階段只在程序開始時執行一次,優化階段必須在每個周期中執行,直到算法結束.因此,HME-ABC 算法的最大計算復雜度可以被描述為:

相似的,傳統ABC 算法的最大計算復雜度可以被計算如下:

計算結果表明,HME-ABC 算法并沒有增加傳統ABC 算法的計算復雜度,能夠保證多UAH 時間協同航路規劃系統的求解效率.并且憑借群智能算法無模型依賴的特性,HME-ABC 算法在復雜優化問題的適用性能力也能夠得到保障.

3 仿真結果與分析

為驗證所提模型與HME-ABC 算法在多UAH時間協同航路規劃問題中的有效性,將ABC 算法、BAS-ABC 算法以及HME-ABC 算法3 種算法進行仿真實驗驗證[14].模擬飛行空間范圍為250km× 250 km×250 km,飛行區域存在3 個不同的威脅區域,威脅信息如表1 所示.5 架UAH 分別從（171,30,30）,（190,97,38）,（175,185,25）,（19,22,43）和（65,168,27）處起飛,任務終點位置坐標為（57,59,64）.

表1 仿真場景參數信息Table 1 Simulation scene parameter information

為使仿真實驗的結果更加客觀公平,設置3 種對比算法的種群數量SN=100,最大迭代次數Maxcycle=50,最大開采限制Limit=5,所有航跡進行平滑處理,實驗結果為獨立運行20 次所得.仿真結果如圖10～圖18 所示.

圖10 基于ABC 算法的UAH 協同飛行航路Fig.10 UAH coordinated flight path based on ABC algorithm

圖11 基于ABC 算法的每架UAH 航路代價值Fig.11 Cost value of each UAH flight path based on ABC

圖12 基于ABC 算法的ETA 協同時間窗Fig.12 ETA synergy time window based on ABC

圖10、圖13、圖16 為3 種算法所規劃的UAH的協同飛行航路.可以直觀地看出,ABC 算法所規劃的飛行航路重疊區域更多,盡管UAH 在時空上并沒有發生碰撞,但較多的重疊路線無形中增加了UAH編隊飛行碰撞的風險.另外,BAS-ABC 算法所規劃的個別飛行航路性能較差,航路長度相對較長.相比較而言,HME-ABC 算法所規劃的飛行航路無論在航路質量還是UAH 飛行安全上都更加優秀.

圖13 基于BAS-ABC 算法的UAH 協同飛行航路Fig.13 UAH coordinated flight path based on BAS-ABC algorithm

圖14 基于BAS-ABC 算法的每架UAH 航路代價值Fig.14 Cost value of each UAH flight path based on BAS-ABC

圖15 基于BAS-ABC 算法的ETA 協同時間窗Fig.15 ETA synergy time window based on BAS-ABC

圖16 基于HME-ABC 算法的UAH 協同飛行航路Fig.16 UAH coordinated flight path based on HME-ABC algorithm

圖11、圖14、圖17 為3 種算法的優化迭代曲線,通過收斂曲線可以明顯地看出,無論從收斂迭代次數還是最終的航路代價值,HME-ABC 的優化性能都要優于其他兩種對比算法.仿真對比統計結果如表2～表4 所示,HME-ABC 算法憑借優秀的搜索策略與進化機制,能有效地避免局部最優解,使算法優化性能更加穩定且優秀.

表2 ABC 算法仿真結果統計Table 2 ABC algorithm simulation statistics results

表3 BAS-ABC 算法仿真結果統計Table 3 BAS-ABC algorithm simulation statistics results

表4 HME-ABC 算法仿真結果統計Table 4 HME-ABC algorithm simulation statistics results

圖17 基于HME-ABC 算法的每架UAH 航路代價值Fig.17 Cost value of each UAH flight path base on HME-ABC

圖12、圖15、圖18 中3 種算法為UAH 編隊的協同時間窗口.由圖可知,ABC 算法與BAS-ABC 算法所規劃的時間窗明顯小于本文所設計的HMEABC 算法,而越小的時間窗意味著更高的任務執行難度.在相同約束條件下,HME-ABC 算法所規劃的航路協同性更強,任務執行容錯率更低.

上述分析表明,本文所提出的HME-ABC 算法能夠利用異維記憶進化策略加快算法收斂速度,避免算法局部最優,有效地提高了傳統ABC 算法的優化性能,快速高效地為UAH 編隊規劃出時間協同飛行航路.

4 結論

研究了一種基于異維記憶進化策略的人工蜂群算法用以解決多UAH 時間協同航路規劃問題.該算法利用了蜜蜂的記憶能力與蜂群的信息交互能力,通過構建一個存儲歷史經驗的記憶知識庫來指導種群后續搜索與更新,提高了算法的收斂速度與優化效率.同時,基于跨越式搜索的偵察蜂更新策略也增強了傳統ABC 算法的局部最優脫困能力.仿真結果表明,與傳統ABC 算法相比較,HME-ABC 算法所規劃的協同時間窗口寬裕度提高約72%,且算法迭代次數縮短約13%.