基于HME-ABC 算法的多無人直升機(jī)時(shí)間協(xié)同航路規(guī)劃

韓增亮 陳 謀 朱豪杰 吳慶憲

在軍事領(lǐng)域,UAH 憑借其能夠在復(fù)雜危險(xiǎn)環(huán)境工作的出色能力,成為近年來最具發(fā)展前景和挑戰(zhàn)的軍事裝備之一[1].隨著現(xiàn)代空戰(zhàn)技術(shù)的不斷發(fā)展,軍事偵察與打擊任務(wù)的復(fù)雜性日益增加,單機(jī)偵察與打擊模式已無法滿足當(dāng)前的軍事任務(wù)需求,多機(jī)協(xié)同作戰(zhàn)成為UAH 在戰(zhàn)場(chǎng)作戰(zhàn)的主要形式.航路規(guī)劃作為UAH 協(xié)同作戰(zhàn)的基礎(chǔ),能夠?yàn)槊考躑AH 提供一條安全無碰撞的最優(yōu)飛行航路,使UAH 編隊(duì)能夠安全有效地完成預(yù)定任務(wù)[2].因此,高效合理的協(xié)同規(guī)劃技術(shù)便成為了任務(wù)能否成功的關(guān)鍵.

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

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

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

1.1 問題描述

多UAH 時(shí)間協(xié)同航路規(guī)劃要求每架UAH 根據(jù)任務(wù)需求,從不同起點(diǎn)出發(fā)并同時(shí)到達(dá)目標(biāo)區(qū)域執(zhí)行任務(wù).UAH 編隊(duì)在飛行過程中可能面臨著地形與防空武器的威脅,規(guī)劃的航路須避開上述威脅區(qū)域并滿足UAH 的機(jī)動(dòng)性能約束.

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

由于對(duì)規(guī)劃空間進(jìn)行了垂直分割操作,航路點(diǎn)的尋找范圍從整個(gè)三維規(guī)劃空間可以縮小為N-1 個(gè)二維平面.對(duì)于每個(gè)二維平面,航路點(diǎn)的表征方式可以轉(zhuǎn)換為.因此,多UAH 時(shí)間協(xié)同航路規(guī)劃問題的優(yōu)化變量E 可以被定義為:

所有航路點(diǎn)應(yīng)滿足地圖邊界的約束,即[8]

1.2 航路代價(jià)分析

1.2.1 油耗代價(jià)

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

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

1.2.2 威脅代價(jià)

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

圖2 威脅代價(jià)計(jì)算示意圖Fig.2 Schematic diagram of threat cost calculation

1.2.3 高度代價(jià)

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

圖3 高度代價(jià)計(jì)算示意圖Fig.3 Schematic diagram of altitude cost calculation

1.3 航路約束分析

1.3.1 UAH 性能約束

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

1.3.2 航路安全約束

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

協(xié)同航路規(guī)劃還需考慮不同的UAH 之間的航路避碰問題.首先考慮航路i 上的航路點(diǎn)m 與航路j上的航路點(diǎn)n 之間的距離是否小于預(yù)設(shè)安全距離.

1.3.3 航路協(xié)同能力

多UAH 協(xié)同航路規(guī)劃的時(shí)間協(xié)同性要求每架UAH 應(yīng)具有相同的編隊(duì)預(yù)計(jì)到達(dá)時(shí)間（estimate time arrival,ETA）.如圖4 所示,UAH 編隊(duì)中每架UAH 的速度范圍為,則第i 架UAH 的飛行時(shí)間段為:

圖4 時(shí)間協(xié)同窗口示意圖Fig.4 Schematic diagram of the time synergy window

當(dāng)?shù)趇 架UAH 和第j 架UAH 存在時(shí)間協(xié)同的可能性,則這兩架UAH 沿航路飛行的時(shí)間應(yīng)滿足以下關(guān)系:

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

2 多UAH 時(shí)間協(xié)同航路規(guī)劃算法

2.1 多UAH 時(shí)間協(xié)同航路規(guī)劃框架

多UAH 時(shí)間協(xié)同航路規(guī)劃要求UAH 編隊(duì)從不同起點(diǎn)出發(fā),并在合理的時(shí)間窗口內(nèi)飛至任務(wù)區(qū)域.圖5 為多UAH 時(shí)間協(xié)同航路規(guī)劃框架,該框架將多UAH 航路規(guī)劃被轉(zhuǎn)化為單UAH 航路規(guī)劃,通過時(shí)間約束調(diào)整各架UAH 飛行速度,計(jì)算時(shí)間協(xié)同變量ETA,從而為UAH 編隊(duì)規(guī)劃出滿足時(shí)間窗口的飛行路徑.

圖5 時(shí)間協(xié)同航路規(guī)劃框架Fig.5 Framework of time-coordinated flight path planning

2.2 基于HME-ABC 算法的多UAH 時(shí)間協(xié)同航路規(guī)劃

為了提高多UAH 時(shí)間協(xié)同航路規(guī)劃問題的結(jié)算效率與規(guī)劃質(zhì)量,本文根據(jù)蜂群的聯(lián)想記憶能力提出了一種基于HME-ABC 算法.通過異維記憶知識(shí)庫的引導(dǎo)進(jìn)化降低了蜂群的無效搜索過程,提高ABC算法的收斂速度和優(yōu)化效率,為UAH 編隊(duì)快速高效地規(guī)劃出時(shí)間協(xié)同飛行航路.詳細(xì)的基于HME-ABC算法的多UAH 時(shí)間協(xié)同航路規(guī)劃過程如下所示.

2.2.1 建立協(xié)同航路規(guī)劃目標(biāo)函數(shù)

根據(jù)戰(zhàn)場(chǎng)環(huán)境配置與協(xié)同任務(wù)需求構(gòu)建協(xié)同航路規(guī)劃問題模型.考慮到協(xié)同航路的綜合代價(jià)與約束,多UAH 時(shí)間協(xié)同航路規(guī)劃目標(biāo)函數(shù)可以描述為:

2.2.2 算法初始化

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

2.2.3 HME-ABC 算法優(yōu)化過程

1）雇傭蜂階段

a）基于種群信息引導(dǎo)的平衡進(jìn)化方式

該進(jìn)化方式利用了種群中不同質(zhì)量個(gè)體的綜合信息,個(gè)體在決定更新行為時(shí)充分考慮了自身、當(dāng)前最優(yōu)個(gè)體和其他個(gè)體的影響.基于種群信息引導(dǎo)的平衡進(jìn)化方式如下:

其中,fit（xi）為當(dāng)前個(gè)體的適應(yīng)度函數(shù).個(gè)體適應(yīng)度值計(jì)算方式如下[14]:

其中,obj（x）為備選解x 的目標(biāo)函數(shù)值.

b）基于異維記憶機(jī)制的進(jìn)化方式

考慮到蜂群進(jìn)化存在失敗概率的問題,本節(jié)為進(jìn)化失敗的雇傭蜂設(shè)計(jì)了一種基于異維記憶機(jī)制的進(jìn)化方式,利用蜜蜂的記憶能力將進(jìn)化成功經(jīng)驗(yàn)應(yīng)用于UAH 航路點(diǎn)的搜索.

圖6 記憶知識(shí)庫Fig.6 Memory knowledgebase

針對(duì)于進(jìn)化失敗的個(gè)體,將給予其二次進(jìn)化的機(jī)會(huì).為提高航路規(guī)劃的成功率,二次進(jìn)化階段將借鑒記憶知識(shí)庫中的成功案例對(duì)其進(jìn)行指導(dǎo).

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

圖7 二次進(jìn)化示意圖Fig.7 Schematic diagram of secondary evolution

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

2）觀察蜂階段

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

其中,fiti（x）為第i 個(gè)蜜源的適應(yīng)度.

3）偵察蜂階段

傳統(tǒng)的ABC 算法采用初始化策略作為偵察蜂的進(jìn)化方式,搜索方向的隨機(jī)性可能會(huì)降低新蜜源的開發(fā)效率.為此,將根據(jù)記憶知識(shí)庫的進(jìn)化經(jīng)驗(yàn),設(shè)計(jì)一種基于跨越式搜索的偵察蜂更新策略.

如圖8 所示,偵察蜂從記憶知識(shí)庫中選擇兩例成功進(jìn)化經(jīng)驗(yàn),其對(duì)應(yīng)的蜜源位置中心作為新蜜源位置,該過程可描述為:

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

2.2.4 協(xié)同航路ETA 計(jì)算

當(dāng)HME-ABC 算法滿足迭代終止條件,便輸出最終的全局最優(yōu)UAH 編隊(duì)航路點(diǎn)序列.根據(jù)所規(guī)劃出的候選航路的長度,協(xié)調(diào)各架UAH 的飛行速度,利用式（22）和式（23）計(jì)算出航路協(xié)同ETA.最終的規(guī)劃結(jié)果為UAH 編隊(duì)的飛行航路與協(xié)同時(shí)間窗口.

基于HME-ABC 算法的多UAH 時(shí)間協(xié)同航路規(guī)劃流程如圖9 所示.

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

2.3 計(jì)算復(fù)雜度分析

HME-ABC 算法的計(jì)算復(fù)雜度由初始化階段復(fù)雜度與優(yōu)化階段復(fù)雜度組成,具體計(jì)算如下[19].

1）初始化階段

2）算法優(yōu)化階段

其中,O（·）表示算法漸進(jìn)時(shí)間復(fù)雜度,n 代表輸入數(shù)據(jù)的量.

初始化階段只在程序開始時(shí)執(zhí)行一次,優(yōu)化階段必須在每個(gè)周期中執(zhí)行,直到算法結(jié)束.因此,HME-ABC 算法的最大計(jì)算復(fù)雜度可以被描述為:

相似的,傳統(tǒng)ABC 算法的最大計(jì)算復(fù)雜度可以被計(jì)算如下:

計(jì)算結(jié)果表明,HME-ABC 算法并沒有增加傳統(tǒng)ABC 算法的計(jì)算復(fù)雜度,能夠保證多UAH 時(shí)間協(xié)同航路規(guī)劃系統(tǒng)的求解效率.并且憑借群智能算法無模型依賴的特性,HME-ABC 算法在復(fù)雜優(yōu)化問題的適用性能力也能夠得到保障.

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

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

表1 仿真場(chǎng)景參數(shù)信息Table 1 Simulation scene parameter information

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

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

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

圖12 基于ABC 算法的ETA 協(xié)同時(shí)間窗Fig.12 ETA synergy time window based on ABC

圖10、圖13、圖16 為3 種算法所規(guī)劃的UAH的協(xié)同飛行航路.可以直觀地看出,ABC 算法所規(guī)劃的飛行航路重疊區(qū)域更多,盡管UAH 在時(shí)空上并沒有發(fā)生碰撞,但較多的重疊路線無形中增加了UAH編隊(duì)飛行碰撞的風(fēng)險(xiǎn).另外,BAS-ABC 算法所規(guī)劃的個(gè)別飛行航路性能較差,航路長度相對(duì)較長.相比較而言,HME-ABC 算法所規(guī)劃的飛行航路無論在航路質(zhì)量還是UAH 飛行安全上都更加優(yōu)秀.

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

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

圖15 基于BAS-ABC 算法的ETA 協(xié)同時(shí)間窗Fig.15 ETA synergy time window based on BAS-ABC

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

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

表2 ABC 算法仿真結(jié)果統(tǒng)計(jì)Table 2 ABC algorithm simulation statistics results

表3 BAS-ABC 算法仿真結(jié)果統(tǒng)計(jì)Table 3 BAS-ABC algorithm simulation statistics results

表4 HME-ABC 算法仿真結(jié)果統(tǒng)計(jì)Table 4 HME-ABC algorithm simulation statistics results

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

圖12、圖15、圖18 中3 種算法為UAH 編隊(duì)的協(xié)同時(shí)間窗口.由圖可知,ABC 算法與BAS-ABC 算法所規(guī)劃的時(shí)間窗明顯小于本文所設(shè)計(jì)的HMEABC 算法,而越小的時(shí)間窗意味著更高的任務(wù)執(zhí)行難度.在相同約束條件下,HME-ABC 算法所規(guī)劃的航路協(xié)同性更強(qiáng),任務(wù)執(zhí)行容錯(cuò)率更低.

上述分析表明,本文所提出的HME-ABC 算法能夠利用異維記憶進(jìn)化策略加快算法收斂速度,避免算法局部最優(yōu),有效地提高了傳統(tǒng)ABC 算法的優(yōu)化性能,快速高效地為UAH 編隊(duì)規(guī)劃出時(shí)間協(xié)同飛行航路.

4 結(jié)論

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