李松銳 張 明 王蒙蒙 李伯權(quán) 裴正瑩

(南京航空航天大學(xué)民航學(xué)院 南京 211106)

0 引 言

在以往研究中提到無(wú)人地面車(chē)輛(unmanned ground vehicle ,UGV)-無(wú)人機(jī)(unmanned aerial vehicle，UAV)基于協(xié)作搜索的路線規(guī)劃方法[1-3]，UGV作為無(wú)人機(jī)的“能源服務(wù)站”，以補(bǔ)充無(wú)人機(jī)電量.在滿足UAV電池能耗約束的前提下，以UAV的總距離最小、UGV的總距離最小及其二者總和最小作為優(yōu)化目標(biāo)進(jìn)行求解，從而獲得協(xié)同任務(wù)計(jì)劃結(jié)果.但是，這種方法規(guī)模較小，沒(méi)有考慮地形和環(huán)境因素對(duì)結(jié)果的影響，而是在2D平面內(nèi)建立模型.Maini等[4]建議使用移動(dòng)加油站擴(kuò)大操作范圍，這可以節(jié)省空間和時(shí)間成本.盡管已經(jīng)考慮了地形對(duì)移動(dòng)加油站位置的影響，但該文獻(xiàn)在實(shí)踐中在飛行任務(wù)分配方面仍存在某些不足.

在一些研究中，無(wú)人機(jī)的飛行路徑通常是理想的，而沒(méi)有考慮到無(wú)人機(jī)避開(kāi)地形障礙和天氣、無(wú)人機(jī)的性能、無(wú)人機(jī)的釋放和回收，以及無(wú)人機(jī)在實(shí)際任務(wù)的不同飛行階段中的能耗差異的影響進(jìn)行分配[5].沒(méi)有探討無(wú)人機(jī)的電量限制[6].無(wú)人機(jī)在搜救點(diǎn)的盤(pán)旋過(guò)程通常與災(zāi)區(qū)狀況的嚴(yán)重性有關(guān)[7].搜救點(diǎn)的等級(jí)屬性分離是一個(gè)災(zāi)害分級(jí)問(wèn)題[8].因此，必須進(jìn)一步結(jié)合救援實(shí)踐來(lái)考慮無(wú)人機(jī)的災(zāi)害分分級(jí)與懸停時(shí)間之間的相關(guān)性.

在以往的研究中，優(yōu)化的目標(biāo)通常為整體的路徑最短，但在文中研究的無(wú)人機(jī)和通航直升機(jī)協(xié)同搜救中，通航直升機(jī)的速度遠(yuǎn)遠(yuǎn)大于無(wú)人機(jī)并且通航直升機(jī)的能源一般較為充足，為使得救援效率提高，優(yōu)化的目標(biāo)不再是整體路徑最短，而著重考慮無(wú)人機(jī)的電量消耗對(duì)搜救過(guò)程中的影響.

1 問(wèn)題描述

由于應(yīng)急救援中考慮對(duì)搜救點(diǎn)進(jìn)行分配之前，需要對(duì)通航直升機(jī)釋放無(wú)人機(jī)的位置進(jìn)行選址，建立適合本文情景的選址模型，考慮地形和低空風(fēng)對(duì)無(wú)人機(jī)電池能耗的影響，以及懸停與飛行狀態(tài)的能耗差異等因素，以搜救的費(fèi)用最小為目標(biāo)進(jìn)行建模，并運(yùn)用改進(jìn)二進(jìn)制蝙蝠算法進(jìn)行求解.

獲取無(wú)人機(jī)性能數(shù)據(jù)(包括最大續(xù)航時(shí)間、最大懸停時(shí)間、3級(jí)低空風(fēng)對(duì)無(wú)人機(jī)電池能耗的影響下的飛行續(xù)航時(shí)間、升限、價(jià)格、最大充電次數(shù)等)、所研究地區(qū)地形數(shù)據(jù)，以及主要的八項(xiàng)災(zāi)情指標(biāo)；考慮無(wú)人機(jī)飛行續(xù)航性能、災(zāi)情等級(jí)、風(fēng)和地形對(duì)無(wú)人機(jī)續(xù)航時(shí)間的影響，以總的搜救費(fèi)用最小為目標(biāo)，對(duì)通航直升機(jī)釋放無(wú)人機(jī)位置的確定問(wèn)題進(jìn)行建模.對(duì)二進(jìn)制蝙蝠算法改進(jìn)，引入差分進(jìn)化機(jī)制，對(duì)上述模型進(jìn)行求解，確定通航直升機(jī)釋放無(wú)人機(jī)的位置，并與未改進(jìn)的算法求得的結(jié)果進(jìn)行對(duì)比分析.

2 直升機(jī)釋放無(wú)人機(jī)位置點(diǎn)選址模型

2.1 模型假設(shè)

1) 備選的通航直升機(jī)懸停點(diǎn)位置、無(wú)人機(jī)的目標(biāo)搜索點(diǎn)的具體坐標(biāo)已知，各節(jié)點(diǎn)之間的距離按照歐氏距離計(jì)算.

2) 將考慮低空風(fēng)對(duì)無(wú)人機(jī)電池能耗的影響、避障的影響及懸停影響下的能耗換算成無(wú)人機(jī)在不考慮以上因素勻速飛行狀態(tài)時(shí)(如本文算例中機(jī)型A的速度為15 m/s)對(duì)應(yīng)的航程進(jìn)行計(jì)量.

3) 搜救高度相對(duì)目標(biāo)搜索點(diǎn)的地形高500 m.

4) 每個(gè)目標(biāo)搜救點(diǎn)有且僅有一架UAV進(jìn)行搜索.

5) 各節(jié)點(diǎn)出發(fā)的UAV的速度均一致，無(wú)人機(jī)的航程成本與無(wú)人機(jī)完成任務(wù)換算成的航程成正比.

6) 不考慮無(wú)人機(jī)充電即多次循環(huán)使用問(wèn)題，發(fā)射前為滿電量.

7) 根據(jù)通航直升機(jī)在山區(qū)的最低安全高度要求標(biāo)準(zhǔn)，其釋放無(wú)人機(jī)的位置的相對(duì)地面高度不得小于600 m.

8) 不考慮無(wú)人機(jī)的通訊問(wèn)題，數(shù)據(jù)傳輸效果在任何飛行位置均為良好.

2.2 參數(shù)定義

選址模型變量為：M為備選通航直升機(jī)釋放無(wú)人機(jī)位置集合，M={1,2,…,m,…,|M|}；N為無(wú)人機(jī)目標(biāo)搜索點(diǎn)集合，N={1,2,…,n}；Fj為釋放位置j的服務(wù)費(fèi)用，元；djk為從釋放位置j到目標(biāo)搜救點(diǎn)k的歐式距離，m；c為UAV單位飛行距離的成本，元/m；tk為UAV在目標(biāo)搜索點(diǎn)k的懸停時(shí)間，s；D為UAV的最大行駛里程(以無(wú)人機(jī)續(xù)航時(shí)間計(jì)算)，m；α為低空風(fēng)對(duì)電池能耗影響系數(shù)；β為避障能耗預(yù)留率；γ為旋翼無(wú)人機(jī)飛行與懸停能耗比；l為計(jì)劃選取的通航直升機(jī)釋放無(wú)人機(jī)位置的個(gè)數(shù)；v為無(wú)人機(jī)勻速飛行的速度，m/s；Sjk為考慮風(fēng)和避障的條件下無(wú)人機(jī)從第j個(gè)通航直升機(jī)懸停點(diǎn)到第k個(gè)搜救點(diǎn)完成搜救任務(wù)的能耗換算成不考慮外界因素的理想狀態(tài)下無(wú)人機(jī)勻速飛行的航程，m；xj為備選中心j被選中則為1，否則為0；zjk為搜救點(diǎn)k由備選中心j服務(wù)則為1，否則為0.

2.3 模型建立

考慮無(wú)人機(jī)的性能參數(shù)，分別求解低空風(fēng)對(duì)電池能耗影響系數(shù)、旋翼無(wú)人機(jī)飛行與懸停能耗比.設(shè)滿電量條件下UAV在無(wú)風(fēng)條件下的最大懸停時(shí)間為T(mén)hover，以速度v可以飛行的最大時(shí)間為T(mén)v，無(wú)人機(jī)一般適合在某級(jí)風(fēng)以下的條件進(jìn)行飛行活動(dòng)，設(shè)在該級(jí)風(fēng)條件下(如本文所研究的無(wú)人機(jī)機(jī)型適合長(zhǎng)時(shí)間在3級(jí)以下的風(fēng)場(chǎng)中飛行，需要預(yù)留足夠的能量)無(wú)人機(jī)最大飛行時(shí)間為T(mén)wind，則無(wú)人機(jī)飛行與懸停能耗比和低空風(fēng)對(duì)電池能耗影響系數(shù)分別為

(3)

(4)

目標(biāo)函數(shù)：

(5)

約束條件：

(6)

(7)

zjk≤xj，j∈M,k∈N

(8)

(9)

Sjk≤D,j∈M,k∈N

(10)

zjk={0,1},j∈M,k∈N

(11)

xj={0,1},j∈M

(12)

式(5)為目標(biāo)函數(shù)，表示總的搜救代價(jià)最小，包括總的完成搜救的費(fèi)用(飛行和懸停)和總的服務(wù)費(fèi)用；式(6)為每個(gè)搜救點(diǎn)由通航直升機(jī)在釋放無(wú)人機(jī)的位置點(diǎn)處派出一架無(wú)人機(jī)進(jìn)行搜救；式(7)為從備選通航直升機(jī)釋放無(wú)人機(jī)的位置點(diǎn)中最少選出l個(gè)釋放位置點(diǎn)進(jìn)行無(wú)人機(jī)的釋放；式(8)為對(duì)于搜救點(diǎn)k，通航直升機(jī)在釋放無(wú)人機(jī)位置點(diǎn)j派出無(wú)人機(jī)搜救，則j必須是被選中的釋放點(diǎn)；式(9)為在不考慮任何外界條件下以一定速度勻速飛行時(shí)為理想狀態(tài)，則需要將無(wú)人機(jī)考慮風(fēng)、避障以及懸停狀態(tài)等因素下完成任務(wù)的能耗換算為理想狀態(tài)下無(wú)人機(jī)的航程Sjk；式(10)為無(wú)人機(jī)懸停點(diǎn)到搜救點(diǎn)的搜救范圍約束，表示無(wú)人機(jī)從通航直升機(jī)釋放無(wú)人機(jī)的位置點(diǎn)j到搜救點(diǎn)k完成搜救任務(wù)的能耗換算為無(wú)人機(jī)勻速飛行狀態(tài)下的航程不大于無(wú)人機(jī)的最大航程；式(11)和(12)為決策變量zjk和xj是0-1變量.

3 算法設(shè)計(jì)

將蝙蝠算法(bat algorithm，BA)用于通航直升機(jī)釋放無(wú)人機(jī)的選址問(wèn)題，計(jì)算方便且計(jì)算效率高，結(jié)果更精確.但由于BA本身的缺陷，即主要依靠個(gè)體之間的信息交換進(jìn)行優(yōu)化，缺乏個(gè)體變異的機(jī)制，使得求得的解迅速向優(yōu)秀的個(gè)體聚集從而使得求解陷入局部最優(yōu)[9]，本文引入差分進(jìn)化算法(differential evolution algorithm，DE)，使得蝙蝠個(gè)體產(chǎn)生變異，對(duì)二進(jìn)制蝙蝠算法(binary bat algorithm，BBA)作出改進(jìn)，進(jìn)而得到更優(yōu)的解.

1) 編碼方式設(shè)計(jì)及種群的初始化 初始化種群中是有d個(gè)備選位置選出l個(gè)釋放位置，則d為每個(gè)蝙蝠的維數(shù).對(duì)于式(9)，令α2和αk分別為

(13)

αk=αγtkvi，k∈N，i∈W

(14)

對(duì)于第k個(gè)搜救點(diǎn)，tk已經(jīng)確定，則知αk為常數(shù).α2顯然是常數(shù)，用第i類無(wú)人機(jī)搜索時(shí)，vi也是定值，則式(9)可以簡(jiǎn)化為

Sjk=α2djk+αk,j∈M,k∈N

(15)

由式(15)可知，無(wú)人機(jī)由于懸停而產(chǎn)生的總費(fèi)用與釋放位置的選擇有關(guān)，因而一旦確定釋放位置，即可采用就近分配的原則將搜救點(diǎn)分配給離其最近的釋放位置.如從10個(gè)備選位置中隨機(jī)選擇7個(gè)釋放位置，被選中的序號(hào)位置置1，其余置0，則其中一個(gè)蝙蝠可以編碼為[1,1,1,0,1,1,0,0,1,1]T，表示第1,2,3,5,6,9,10號(hào)釋放位置開(kāi)放，而其他釋放位置關(guān)閉.釋放位置確定之后，搜救點(diǎn)采用就近分配并且滿足約束條件則任務(wù)即分配完畢，否則該蝙蝠停止向此次方向進(jìn)化，取父代繼續(xù)向其他方向進(jìn)化.

2) 評(píng)價(jià)函數(shù)的定義 評(píng)價(jià)函數(shù)Evaluation這里取目標(biāo)函數(shù)的值，即式(16)，其數(shù)值越小，個(gè)體越優(yōu)良.

(16)

3) 改進(jìn)的二進(jìn)制蝙蝠算法(improved binary bat algorithm，IBBA) DE擁有更多豐富的突變策略，其突變算子更有效地利用了種群分布特征，并且突變效率更高.使得DE和BBA的結(jié)合可以克服BA的收斂精度低，容易陷入局部最優(yōu)等缺點(diǎn).應(yīng)當(dāng)注意，DE算法也是一種連續(xù)優(yōu)化算法，因此將其轉(zhuǎn)換為二進(jìn)制DE.

(17)

從總體中隨機(jī)選擇兩個(gè)與當(dāng)前個(gè)體不同的個(gè)體；然后，將它們之間的差分向量加到當(dāng)前最優(yōu)個(gè)體上，差分突變后的新個(gè)體的分量可以表示為

(18)

(19)

4) 改進(jìn)二進(jìn)制蝙蝠算法步驟

步驟1隨機(jī)生成規(guī)模為d，維度為d的初始解.最大脈沖音量r0，最大脈沖率r0，最大迭代次數(shù)Ngen.根據(jù)評(píng)價(jià)函數(shù)值的大小尋找當(dāng)前所有蝙蝠個(gè)體中的最優(yōu)解.

步驟2蝙蝠i的搜索脈沖頻率fi更新方式如式(20)，其中fmin和fmax分別為最小和最大搜索脈沖頻率，β1是均勻分布的隨機(jī)數(shù)，β1∈[0,1].

fi=fmin+(fmax-fmin)β1

(20)

標(biāo)準(zhǔn)蝙蝠算法求解是用來(lái)求解連續(xù)型函數(shù)的優(yōu)化問(wèn)題，所以需要對(duì)蝙蝠的位置更新公式以及速度更新公式進(jìn)行變換，得到適合求解離散優(yōu)化問(wèn)題的BA.對(duì)標(biāo)準(zhǔn)BA進(jìn)行修改，得到BBA.所求的目標(biāo)為最小化，為將尋優(yōu)域維持在0-1兩個(gè)數(shù)內(nèi)，對(duì)蝙蝠的速度變換和位置變換為

(21)

(22)

步驟3生成均勻分布隨機(jī)數(shù)rand，如果rand>r(r為蝙蝠游走步長(zhǎng))，則對(duì)x*進(jìn)行隨機(jī)擾動(dòng)，產(chǎn)生一個(gè)新的解，并對(duì)新的解根據(jù)式(23)進(jìn)行越界處理，其中rand(1,d)代表生成d維0-1之間的隨機(jī)數(shù).

xnew=∧(xold,round(rand(1,d)))

(23)

(24)

(25)

步驟5變異和交叉

步驟6對(duì)當(dāng)前全部蝙蝠個(gè)體的評(píng)價(jià)函數(shù)值排序,得到當(dāng)前最優(yōu)解.

步驟7重復(fù)步驟2～步驟6直至達(dá)到最大迭代次數(shù).

步驟8輸出全局最優(yōu)值和最優(yōu)解.

4 算例分析

4.1 數(shù)據(jù)獲取

選用三種不同機(jī)型進(jìn)行分析，其性能數(shù)據(jù)見(jiàn)表1.

表1 無(wú)人機(jī)性能參數(shù)

文中所用機(jī)型A無(wú)人機(jī)型號(hào)為多旋翼類型無(wú)人機(jī)X6L(雙電池)，以飛行速度15 m/s進(jìn)行計(jì)算，其最大航程為108 km.機(jī)型B為X6M(雙電池)，機(jī)型C為Z6M(雙電池).風(fēng)的折算和懸停折算可以根據(jù)對(duì)應(yīng)公式求得，對(duì)于地形的避障，根據(jù)實(shí)際地形情況取折損系數(shù)，在這里取30%.

4.2 模型及算法參數(shù)

算例分析中用到的模型參數(shù)和算法參數(shù)見(jiàn)表2.

表2 機(jī)型及算法參數(shù)設(shè)置表

4.3 基于改進(jìn)二進(jìn)制蝙蝠算法的通航直升機(jī)釋放無(wú)人機(jī)位置選址

釋放位置有100個(gè)備選，根據(jù)通航直升機(jī)山區(qū)飛行最低高度最少要位于障礙上方600 m處，則選取釋放位置位于釋放點(diǎn)高程上方600 m處進(jìn)行無(wú)人機(jī)的釋放，保障通航直升機(jī)的飛行安全，備選點(diǎn)的經(jīng)緯度坐標(biāo)與搜救點(diǎn)一致，高度在搜救點(diǎn)(相對(duì)地面高度500 m)的基礎(chǔ)上增加100 m.

1) 種群初始化 以機(jī)型A為例，機(jī)型B和C類似.產(chǎn)生全1序列，長(zhǎng)度為100，為便于后面進(jìn)行迭代使得開(kāi)放位置越來(lái)越少，隨機(jī)取其中一個(gè)位置置為0，則其中一個(gè)蝙蝠可以為[0 1 1…1]，以同樣的方式產(chǎn)生其余蝙蝠，選取釋放位置的個(gè)數(shù)不少于18個(gè).

2) 計(jì)算結(jié)果 運(yùn)用IBBA進(jìn)行迭代800次，分別與BBA、二進(jìn)制粒子群算法(binary particle swarm optimization，BPSO)[10]、簡(jiǎn)化的二進(jìn)制人工魚(yú)群算法[11](simplified binary artificial fish-swarm algorithm，S-bAFSA)的迭代結(jié)果進(jìn)行對(duì)比見(jiàn)圖1.由圖1可知:見(jiàn)IBBA算法相比于BBA算法得到的結(jié)果更優(yōu)，在保證各相同參數(shù)一致的條件下，IBBA算法相比于BBA的總費(fèi)用平均減少了4.60%，而相比于BPSO、S-bAFSA得到的總費(fèi)用平均分別減少了21.20%和4.13%.同理，運(yùn)用機(jī)型B和機(jī)型C分別進(jìn)行算例分析，得出IBBA相比于其他算法總費(fèi)用減少的比率見(jiàn)表4，其中費(fèi)用變化率見(jiàn)式(26).

圖1 IBBA和其他算法迭代效果對(duì)比

表3 三種機(jī)型選址結(jié)果對(duì)比

(26)

三種機(jī)型的結(jié)果中，IBBA相比于BPSO、S-bAFSA、BBA得到的結(jié)果的總費(fèi)用平均減少了22.07%、6.17%、6.61%，表明改進(jìn)后的算法在求解質(zhì)量上相比于改進(jìn)前以及其他優(yōu)化算法有明顯提高.

取IBBA的運(yùn)行結(jié)果進(jìn)行進(jìn)一步研究，其對(duì)應(yīng)的解為：[0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1]，即開(kāi)放7，13，16，17，25，30，38，39，42，53，61，71，74，75，78，89，91，100號(hào)等18個(gè)位置作為通航直升機(jī)釋放無(wú)人機(jī)的位置，每個(gè)釋放位置分配搜救點(diǎn)的其中一種結(jié)果見(jiàn)表4.

表4 無(wú)人機(jī)釋放點(diǎn)選址結(jié)果及對(duì)應(yīng)選址點(diǎn)任務(wù)分配結(jié)果

5 結(jié) 束 語(yǔ)

文中提出了考慮無(wú)人機(jī)運(yùn)行環(huán)境和性能的通航直升機(jī)釋放無(wú)人機(jī)位置選取模型.根據(jù)災(zāi)區(qū)的各項(xiàng)災(zāi)情指標(biāo)，人口分布對(duì)受災(zāi)搜救點(diǎn)進(jìn)行模擬，并考慮無(wú)人機(jī)的探測(cè)范圍來(lái)確定目標(biāo)搜索點(diǎn)的災(zāi)情等級(jí)和相應(yīng)懸停搜救時(shí)間.在考慮災(zāi)情等級(jí)，無(wú)人機(jī)性能和低空風(fēng)對(duì)無(wú)人機(jī)電池能耗影響的基礎(chǔ)上，建立了通航直升機(jī)釋放無(wú)人機(jī)的位置選址模型，引入差分進(jìn)化機(jī)制，改進(jìn)的二進(jìn)制蝙蝠算法進(jìn)行求解，從而得到更優(yōu)的結(jié)果.由于對(duì)地形因素避障預(yù)留的無(wú)人機(jī)電池電量難以準(zhǔn)確評(píng)估，該研究的文獻(xiàn)較少，只能以一定的覆蓋率來(lái)完成搜索任務(wù)，未來(lái)研究考慮引入無(wú)人機(jī)電池環(huán)境與耗能曲線，精確估計(jì)無(wú)人機(jī)能耗，提高無(wú)人機(jī)任務(wù)分配的準(zhǔn)確度.此外，在救援點(diǎn)的高度各不相同，如果無(wú)人機(jī)在不同的救援和搜索點(diǎn)懸停時(shí)改變高度，無(wú)人機(jī)的能耗狀況隨之改變，并且即使在相同的環(huán)境條件下進(jìn)行相同的操作，電池壽命或能耗也存在很多不確定性，只能建立一些較為理想化的數(shù)學(xué)模型，未來(lái)可以對(duì)其進(jìn)行更深入的研究.