直升機釋放無人機的選址問題研究

李松銳 張 明 王蒙蒙 李伯權 裴正瑩

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

0 引 言

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

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

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

1 問題描述

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

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

2 直升機釋放無人機位置點選址模型

2.1 模型假設

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

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

3) 搜救高度相對目標搜索點的地形高500 m.

4) 每個目標搜救點有且僅有一架UAV進行搜索.

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

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

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

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

2.2 參數(shù)定義

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

2.3 模型建立

考慮無人機的性能參數(shù)，分別求解低空風對電池能耗影響系數(shù)、旋翼無人機飛行與懸停能耗比.設滿電量條件下UAV在無風條件下的最大懸停時間為Thover，以速度v可以飛行的最大時間為Tv，無人機一般適合在某級風以下的條件進行飛行活動，設在該級風條件下(如本文所研究的無人機機型適合長時間在3級以下的風場中飛行，需要預留足夠的能量)無人機最大飛行時間為Twind，則無人機飛行與懸停能耗比和低空風對電池能耗影響系數(shù)分別為

(3)

(4)

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

3 算法設計

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

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

(13)

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

(14)

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

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

(15)

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

2) 評價函數(shù)的定義 評價函數(shù)Evaluation這里取目標函數(shù)的值，即式(16)，其數(shù)值越小，個體越優(yōu)良.

(16)

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

(17)

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

(18)

(19)

4) 改進二進制蝙蝠算法步驟

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

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

fi=fmin+(fmax-fmin)β1

(20)

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

(21)

(22)

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

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

(23)

(24)

(25)

步驟5變異和交叉

步驟6對當前全部蝙蝠個體的評價函數(shù)值排序,得到當前最優(yōu)解.

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

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

4 算例分析

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

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

表1 無人機性能參數(shù)

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

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

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

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

4.3 基于改進二進制蝙蝠算法的通航直升機釋放無人機位置選址

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

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

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

圖1 IBBA和其他算法迭代效果對比

表3 三種機型選址結果對比

(26)

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

取IBBA的運行結果進行進一步研究，其對應的解為：[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]，即開放7，13，16，17，25，30，38，39，42，53，61，71，74，75，78，89，91，100號等18個位置作為通航直升機釋放無人機的位置，每個釋放位置分配搜救點的其中一種結果見表4.

表4 無人機釋放點選址結果及對應選址點任務分配結果

5 結 束 語

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