基于低空救援的無人機起降點選址問題研究

高 翔 張 明 李松銳 劉 旭 孫麗超

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

0 引 言

無人機具有體積小、靈活輕便的優點,但無人機航程有限難以執行大規模的探測搜救任務.而直升機具有航程大、受天氣影響小,以及機動性強等特點,相比于車輛具有移動速度快、受地面狀態影響小的優點,因此在地震發生后利用直升機和無人機協同搜救可以充分發揮兩者的優勢[1].Carlsson[2]論證了車輛和無人機的使用效率,證明了使用車輛和無人機協同搜救的潛在效益與車輛和無人機之間的速度比的平方根成正比.Wang等[3]針對多輛卡車和無人機引入了無人機車輛路徑問題,論證了協同作業下效率的提高.San等[4]在無人機和無人車協作的模型中考慮了實際飛行中的約束條件,來求解路徑問題.Chowdhury等[5]針對無人機攜帶設備的重量和能耗之間的關系建模,估算無人機能實際覆蓋的飛行范圍來求解無人機的航跡規劃問題.Dorling 等[6]通過建立一個有效載荷不同的無人機能量消耗模型解決了多無人機路徑規劃問題.

針對載體和多無人機協作的無人機起降點選址問題.Sergio等[7]提出了一輛卡車和多架無人機的新模式,設置無人機的起飛降落點為同一位置,利用k-means聚類算法來確定位置無人機的起降點.Freitas等[8]為了確定無人機的起降點提出了一種混合啟發式算法,初始解由TSP求解器生成,之后使用混合啟發式算法求解得出無人機的起降點和卡車的路線.Agatz等[9]假定無人機每次起飛和降落必須在相同位置,利用局部搜索的方法來確定無人機的起降點.Bouman等[10]為了確定載體和多無人機的協作下無人機起降點問題,提出了一種動態規劃的精準方法,該方法以能夠求解出更大規模的實例.楊雷博等[11]提出了一種在限制區下一輛車攜帶多架無人機的貨車支持無人機配送解決方案,并構造了以最小服務時間為優化目標的雙層規劃求解方法.曹峰等[12]提出了一種面向大面積巡檢區域的巡檢車路徑規劃方法,巡檢車在每個駐車點處駐車一次,多架無人機由巡檢車起降平臺上起飛,前往各自目標桿塔完成相應的巡檢任務,且要求無人機必須同點起降.劉艷秋等[13]提出貨車和無人機“協同+并行”混合配送模式,以總運營成本最小為目標,建立了搭載多架無人機的車輛路徑問題混合整數規劃模型.彭勇等[14]構建了卡車無人機協同配送的路徑優化模型,考慮一輛卡車與多架無人機進行配送,且配送客戶需要讓卡車在服務的客戶點等待無人機完成配送任務并回收后才繼續下一個點的配送服務.曹英英等[15]基于集群提出卡車與無人機聯合配送新模式,考慮一輛卡車配有多架無人機進行配送,并提出兩階段算法,通過改進后的K-means算法求出卡車停靠點,采用遺傳模擬退火算法優化卡車與無人機聯合配送路線.

針對無人機起降點選址的建模中,大多將無人機的起飛點和降落點設置為同一位置,沒有考慮無人機實際飛行中在執行完搜救任務后可能會就近降落,導致選址成本較高.而且模型的約束中很少考慮環境溫度、無人機的負載以及飛行姿態對無人機的續航能力的影響.文中針對傳統的無人機本地起降模式選址模型進行改進,將無人機運行時的環境溫度、無人機的負載,以及無人機的飛行姿態對無人機續航能力的影響作為模型的約束,在模型中不要求無人機的起降點為同一位置,使得對無人機起降點的選址問題更加符合實際,降低選址成本.

1 無人機飛行狀態對續航能力的影響

文中基于氣動理論建立旋翼無人機的理想化的近似功耗模型[16].

1) 無人機懸停時的功率方程為

(1)

2) 無人機水平飛行時的功率方程為

(2)

式中:ρ為空氣密度;W(N)為總重量;ζ(m2)為旋翼面積;Vhor為無人機水平飛行的速度;α(Vhor)為水平飛行時的迎角;ηhor為水平飛行時的效率系數;α(Vhor)、ηhor均為經驗系數,文獻[16]中利用實測數據根據最小二乘法計算得出.

(3)

(4)

S′=vtσ1

(5)

(6)

式中:σ1為無人機攜帶負載懸停的時的功率與無人機空載水平飛行時功率的比值;σ2為無人機攜帶負載水平飛行時的功率與無人機空載水平飛行時功率的比值.設無人機水平飛行時間為t,懸停時間為t′,無人機的水平飛行速度為v.

負載條件下無人機水平飛行時間t,對應標準情況下(無人機空載、運行環境溫度為25℃)無人機航程S′'由所示.負載條件下無人機懸停時間為t′,對應標準情況下(無人機空載、運行環境溫度為25℃)無人機航程為S″由所示.

2 運行環境溫度對無人機續航能力影響

利用無人機低空搜救時僅考慮環境溫度對無人機續航能力的影響,引用鋰離子電池在不同運行溫度下實際的電池容量見表1,鋰離子電池標準容量為環境溫度為25℃下的的電池容量.利用不同的擬合方法求得鋰電池容量變化與溫度的關系,建立鋰離子電池實際容量與環境溫度的函數關系.

表1 電池的容量隨外界溫度變化表

根據SPSS的實際運行結果,匯總了實測結果中環境溫度與電池容量擬合的三種線型的參數表見表2,圖1為擬合曲線圖.

圖1 溫度-電池實際容量擬合(實測散點圖與三類擬合曲線)

表2 溫度-電池實際容量擬合參數表

δx=0.98+6.72×10-4x+3.11×10-5x2-

8.27×10-7x3-20≤x≤25

(7)

(8)

式中:x為無人機搜救過程中的環境溫度,℃;δx為在環境溫度為x時,電池的實際容量與理論容量的比值,其物理意義為在當前溫度下鋰離子電池容量與標準電池容量的比值;v為無人機的水平飛行速度;t″為最大飛行時間.

3 無人機異地起降選址模型

直升機和無人機協同搜救無人機的本地起降模式見圖2a),直升機放飛無人機后在原地等待無人機搜救任務完成后進行回收,回收后執行下一組任務.協同搜救的異地起降模式見圖2b),直升機放飛無人機后直接飛往下一點來回收無人機,交替進行完成任務.

圖2 本地起降模式與異地起降模式

模型假設:①待搜救點已經確定,每個待搜救點只需且只能被探測一次;②考慮無人機實際避障帶來的影響,設置預留能耗系數;③每個待搜救點的探測時間已知,無人機攜帶負載下的懸停時間和飛行時間的轉為為無人機標準情況下(無人機空載、運行環境溫度為25 ℃)的航程;④忽略了無人機的在起飛和降落的具體狀態每架無人機的起飛和著陸都可以瞬間完成;⑤無人機在直升機上能自動充電或更換電池.

考慮無人機的負載、無人機的飛行狀態、運行環境溫度變化對無人機續航能力的影響,針對以往研究中的選址模型進行改進,建立直升機和無人機協同搜救的無人機異地起降選址模型.

考慮以搜救費用最低為目標函數,目標函數為

(9)

(10)

Sb,k,l≤Sδx,b,l∈M',k∈M

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

xb={0,1},b∈M′

(19)

(20)

pl={0,1},l∈M′

(21)

式(10)為無人機考慮懸停、負載情況下的無人機實際航程;式(11)為在環境溫度為x時需要滿足的無人機續航能力要求;式(12)為每個待搜救點只由一個無人機起降點為其服務;式(13)為每個待搜救點只由一個無人機降落點為其服務;式(14)為一組無人機起降點可以服務多個待搜救點,每個待搜救點只能由一組無人機起降點為其服務;式(15)為選出的無人機起飛點數量和無人機降落點數量一定要相等;式(16)為當b被選成無人機起飛點時才可能存在待搜救點k由該點起飛的無人機服務;式(17)為若l點被選中為無人機的降落點才可能存在待搜救點k無人機服務完成降落;式(18)為無人機由b點出發飛向待搜救點k則為1否則為0;式(19)為b被選選作無人機起飛點則為1否則為0;式(20)為無人機從待搜救點k飛回降落點l則為1,否則為0;式(21)為l被選作無人機降落點則為1,否則為0.

4 算法設計

運用改進的二進制粒子群算法求解無人機起降點選址問題.每個粒子表示一種選址序列,1表示該組起降點被選中,0表示該組起降點未被選中.算法設計中的變量與含義見表3.

表3 算法設計變量表

初始化種群是將若干組備選無人機起降位置兩兩組合,用這種方式求解滿足了模型中的的限制,從組合中選取無人機起降點,針對式令α和αk分別為.

(22)

αk=tkv

(23)

則式(2)～(10)可以化簡為

Sb,k,l=(db,k+dk,l)ασ1+αkσ2

(24)

Z1為選址成本即式,無人機起降點選址成本越小越符合要求.

(25)

傳統的粒子群算法在迭代計算的過程中線性減少權重w,但是運算中僅僅只減少w,容易使函數收斂到局部極值點.為解決此問題本文在求解無人機起降點選址問題時中采用慣性權重動態改變的方法:

(26)

(27)

(28)

(29)

基于改進二進制粒子群算法求解異地選址問題的步驟如下.

步驟1確定粒子群規模m,最大迭代次數n,以及參數c1,c2,r1,r2,w,生成距離矩陣.

步驟2將無人機起降點按照組合的方式產生,按照上文介紹的種群初始化的規則隨機產生m個可行解X1,X2,X3,…,Xm,每個解的矩陣行數為待搜救點的組合數.找到未開放的選址組合在距離矩陣中相應位置為無窮大,找到每行中非0以外的最小位置,并生成指派矩陣滿足(14)、(15),并判斷矩陣中的解是否滿足式(10)、(11).若滿足按照式(25)計算Xi的適應度并且將初始適應度作為初始個體極值Pbest,i,由于異地選址問題中的目標函數是搜救費用滿足最低要求,所以將所有Pbest,i中的最小值賦給Gbest作為初始全局極值,vi的初始值設為0.

步驟3在更新后按照式(25)計算更新后每個個體對應的無人機起降點選址成本,并且按照式(26)、(27)跟新慣性權重w,如果粒子i的無人機起降點選址成本低于此前個體極值Pbest,i,則將其置為Pbest,i,如果最佳的Pbest,i優于此前的全局的極值Gbest則將其置為Gbest.

步驟4如果滿足收斂條件或達到的最大迭代次數,就停止計算,否則返回步驟3.

5 算例分析

5.1 數據獲取及相關參數設計

以2010年4月14日玉樹地震為例,選取在該地震帶上受災較為嚴重的玉樹縣和稱多縣.選擇100個點作為待搜救點,生命探測儀DKL LifeGuard TM在開放空間搜救距離可達500 m以上,水面達1 km以上,在碰到障礙物時偵測范圍會減少.無人機型號為科衛泰X6L,詳細參數見表4.

表4 相關參數表

5.2 無人機起降點的選址

利用改進的二進制粒子群算法求解無人機起降點的選址模型,算法的設置見表5.

表5 粒子群算法參數設置表

粒子群算法具有隨機性,因此每次求解運算10次,以10次的平均值作為最終的解.以30個待搜救點數量為例,運用改進二進制粒子群算法迭代100次,求解模型相關參數,得到對應的無人機起降點組合以及對應的待搜救點和相應的選址成本,并且與未改進的粒子群算法進行對比的迭代結果見圖3,分別求得無人機異地起降模式下的選址總成本為2 185.401元和無人機本地起降選址模式下的總成本為2 966.596元.

圖3 改進的二進制算法和其他算法迭代效果對比

求解無人機起降點選址模型得到的解為若干組無人機起降點以及每組起降點對應的待搜救點.在選址階段我們不要求得到無人機的數量與飛行計劃,在后續的無人機任務分配的基礎上規劃出直升機的航線后,根據執行各個子任務的順序,各組子任務的無人機的起飛點和無人機的降落點將會被確定.

30個待搜救點規模下的求解結果見表6.由表6可知:30個待搜救點數量下的求解結果共選出4組無人機起降點即將整個搜救任務分成4組子任務.

表6 30個待搜救點規模下無人機起降點選址結果

繼續求解50個待搜救點規模下,80個待搜救點規模下,100個待搜救點規模下的選址問題,結果見表7～9.

表7 50個待搜救點規模下無人機起降點選址結果

表8 80個待搜救點規模下無人機起降點選址結果

表9 100個待搜救點規模下無人機起降點選址結果

5.3 文獻對比分析

選取30、50、80和100個四種規模不同的待搜救點進行驗證,求解本地起降與異地起降的選址成本和方案,見圖4.

圖4 不同數量待搜救點下的本地選址成本與異地選址成本對比

計算出10次運算后選址成本的均值,并且計算成本變化率,見表10.

表10 兩種模式不同規模下選址成本均值以及成本變化率

成本變化率=[(|本地起降模式選址成本均值-異地起降模式選址成本均|)/異地起降模式選址成本均值]×100%

6 結 束 語

本文提出了考慮無人機的運行環境溫度、無人機負載、無人機的飛行狀態作為模型約束,在此基礎上建立直升機無人機協同搜救的無人機異地起降選址模型,利用二進制粒子群算法求解時引入了動態調整慣性權重的方法,通過算例證明了改進后的算法改進了其容易產生局部最優解的缺陷,從而得到較優得結果.在30、50、80、100個待搜救點規模下本文所建立的模型相對以往的研究選址成本分別降低了14.98%,56.08%,31.69%和31.06%.

在本文的設置的搜救環境下考慮溫度對無人機續航能力的影響時,極端條件設置的溫度系數為玉樹地區四月月均溫最低值,但實際搜救過程中環境溫度在不斷變化,因此在后續的研究中可以考慮無人機續航能力隨溫度的動態變化.