林火搜救多無人機協(xié)同任務分配方法

劉 森 姜雪松 張宇晨 郭軼男 李晉澤

（東北林業(yè)大學，黑龍江 哈爾濱 150040）

隨著科技的不斷進步與創(chuàng)新，越來越多的國內(nèi)外專家與學者開始致力于探索無人機在搜救行動中的潛在應用。

肖玉杰等[1]提出了一種分層框架，其用途是分配任務、規(guī)劃路徑和進行碰撞檢測，其中，使用協(xié)商算法進行任務分配。袁德平等[2]運用群智能算法和進化算法解決了搜救任務分配問題。朱紅果等[3]提出一種基于市場機制的復雜任務分配算法，充分考慮了任務的優(yōu)先級，并驗證了分層動態(tài)樹方法在大規(guī)模UAV監(jiān)測中的有效性。國博等[4]創(chuàng)建了基于混合整數(shù)線性規(guī)劃的任務分配模型，并改進了粒子群算法，以解決多UAV任務分配問題。有偉等[5]綜合考慮多種約束條件，建立多目標整數(shù)規(guī)劃的任務協(xié)同分配模型，設(shè)計了免疫粒子群算法，以解決多UAV任務分配問題。Deng，Qi bo等[6]使用多類型基因改進遺傳算法處理異構(gòu)UAV動態(tài)任務分配問題，同時考慮了資源約束?；跓o人機在搜救行動受到的環(huán)境影響，如風速、風向、大氣能見度、云層高度以及光照角度等關(guān)鍵要素，本文構(gòu)建了一個無人機-環(huán)境約束模型，旨在精確評估并優(yōu)化無人機在復雜環(huán)境下的搜救效率。針對多機協(xié)同搜救任務分配問題，提出狀態(tài)壓縮動態(tài)規(guī)劃算法，通過仿真確定最終任務分配方案。

1 無人機-環(huán)境約束模型

1.1 風力風速約束模型

無人機的最大抗風能力Cw通常取決于多個因素，包括無人機的質(zhì)量、體積以及發(fā)動機的最大輸出功率等核心參數(shù)。在氣象學領(lǐng)域，根據(jù)其對各種物體的影響程度將風速劃分為不同的等級。目前，搜救無人機能夠在最大風力達到6級的情況下保持穩(wěn)定運行和操作。為保障搜救無人機的安全，保證搜救效率，本文設(shè)定了無人機可承受的最大風速為10.8m/s。一旦風速超過閾值，無人機將無法通過該區(qū)域。當風速超過可承受最大風速時，可通過降低無人機的飛行高度來減緩風速，直至其降至無人機可承受的最大風速范圍內(nèi)。采用該模型的目的是找到一種策略，以應對不同風速條件下的搜救任務，如公式（1）所示。

式中：vΔH為由當前高度降低高度ΔH后的風速大??；vs為海拔高度Hs處的平均水平風速大小構(gòu)建無人機最大抗風能力與飛行速度之間的約束模型，以保障搜救行動的安全，如公式（2）所示。

式中：v為搜救無人機搜索時的飛行速度；vw為當前風速；cw為無人機可承受最大風速。

1.2 能見度約束模型

根據(jù)森林地區(qū)能見度的特性分析，該地區(qū)的局部能見度與平原地區(qū)存在顯著差異，變化較大。在能見度較低的情況下，為了確保機載攝像機能夠清晰拍攝到目標區(qū)域的地面情況，搜救無人機需要降低飛行高度，因此，本文構(gòu)建了能見度與拍攝距離之間的約束關(guān)系模型，如公式（3）～公式（5）所示。

式中：Vis為目標區(qū)域的當前能見度；Hcloud為云層距離地面的相對高度；Hmin為搜救無人機在該地區(qū)最低安全飛行高度，具體高度值須根據(jù)實際情況進行確定；Hmax為搜救無人機的最高飛行高度。

1.3 光照角度對無人機搜救約束

通?？梢杂锰柕母叨冉呛吞柗轿唤莵砻枋龉庹战嵌取＿@2個參數(shù)對拍攝圖像的清晰度和質(zhì)量有重要影響，如圖1所示。

圖1 太陽光照角度

光照角度和方位角關(guān)系式如公式（6）所示。

式中：α、β分別為太陽的高度角和方位角；φ、δ分別為赤緯角和太陽時角。

1.4 搜救無人機視程約束

當搜救無人機執(zhí)行搜索與救援任務時，其核心功能依賴于圖像采集技術(shù)。在實踐中，常見的圖像采集方法涵蓋了攝像機、掃描儀、紅外線熱成像儀以及激光雷達等多種設(shè)備。然而，鑒于森林環(huán)境的獨特復雜性，這些設(shè)備在應用中常會受到環(huán)境因素的干擾，影響其精確度。同時，考慮經(jīng)濟成本，搜救無人機難以配備高精尖或高成本的圖像采集設(shè)備。搜救無人機攜帶的攝像機系統(tǒng)包括攝像頭和云臺2個主要部分，以滿足在搜救任務中獲取圖像數(shù)據(jù)的需求。搜救無人機機載攝像機對目標區(qū)域地面的拍攝方式如圖2所示。

圖2 搜救無人機動態(tài)視程示意圖

無人機尺寸和搜救無人機拍攝視程的比例關(guān)系如公式（7）～公式（9）所示。

式中：p為待搜救區(qū)域面積和無人機搜救視程之間的比例關(guān)系；l為待搜救區(qū)域長度；w為待搜救區(qū)域?qū)挾?；α、β分別為太陽的高度角和方位角。

1.5 無人機動態(tài)搜救油耗約束

搜救無人機的油耗受多種因素影響，包括發(fā)動機型號、飛行速度、載荷以及飛行高度。在發(fā)動機型號一致的情況下，飛行速度、載荷和飛行高度與油耗之間存在正相關(guān)關(guān)系。隨著飛行速度的增加、載荷的加重以及飛行高度的提升，無人機的油耗也會相應上升?；谶@些因素，可以構(gòu)建一個關(guān)于搜救無人機油耗的模型表達式，如公式（10）～公式（15）所示。

式中：Fueli為搜救無人機在高度Hi處搜救時的油耗；v為搜救無人機的飛行速度；G為無人機所攜帶的負載；為搜救無人機在高度H處巡航時的油耗；C為巡航階段；fuelH為搜救無人機在巡航階段的速度、高度和載荷均不變階段無人機的油耗為固定值；為搜救無人機爬升高度的油耗；U為爬升階段；λ1每百米油耗增長系數(shù)，即每爬升100m消耗燃料增加量的燃料消耗；為搜救無人機下降高度ΔH的油耗；D為下降階段；λ2為每百米油耗降低系數(shù)，表示在下降階段每下降100m所減少的燃料消耗；ΔH為無人機在不同飛行階段的高度變化；C為搜救無人機在特定高度H處的巡航階段的耗油量，即巡航期間的燃料消耗；為搜救無人機在飛行高度H處、飛行總時間的耗油量；m為在高度處H的航段數(shù)；capfuel為最大載油量。

2 無人機協(xié)同搜救任務分配模型原理

2.1 火勢蔓延模型

模型假設(shè)如下。

A1：森林火災火勢初始蔓延速度與氣溫和風力呈線性相關(guān)。

A2：研究區(qū)域為丘陵地區(qū)，地勢坡度＜60°。

A3：林場類型包括草甸、次生林和針葉林。

A4：能夠及時獲取森林火災區(qū)域的氣象數(shù)據(jù)，如公式（16）和公式（17）所示。

式中：Vd為火勢蔓延速度；Vw為風速；V0為火勢初始蔓延速度；Ks為可燃物類型修正系數(shù)；Kw為風力修正系數(shù)；Kφ為地形坡度修正系數(shù)；T為溫度；w為風力；a=0.053，b=0.048，c=0.275。

初始蔓延速度可通過地表可燃物取樣火燒方法測算獲得，根據(jù)回歸取樣數(shù)據(jù)可得到V0與空氣溫度、風速或風力等關(guān)系式；可燃物類型修正系數(shù)為草甸Ks，g=1.0；次生林Ks，sf=0.7；針葉林Ks，cf=0.4；草甸、零坡度地勢、風力等級為1～12級時的Vw。

2.2 基于狀態(tài)壓縮動態(tài)規(guī)劃算法建模

使用狀態(tài)壓縮的動態(tài)規(guī)劃，mask：由01組成的二進制數(shù)，第i位表示第i個著火點，第i位為1說明第i個著火點已滅火，第i位為0說明第i個著火點未滅火。dp[j][mask]：說明在只有1個無人機且狀態(tài)為mask時，最后1個滅火點為j，需要的最短時間prev_j：j的前一個滅火點，prev_mask：j的前一個滅火點對應的mask，time_to_extinguish：從prev_j到j點并滅火需要的總時間。先求出使用1個無人機時狀態(tài)為mask的最短時間dp2[0][mask] = min（dp[j][mask]） j 在mask內(nèi)再通過動態(tài)規(guī)劃求出dp2[i][mask]i ＞1，dp2[i][mask1]= min（dp2[i][mask1]，max（dp2[0][mask2]，dp2[i - 1][mask1 -mask2]）），dp2[0][mask2] 表示狀態(tài)mask2用第i + 1個無人機去滅火dp2[i - 1][mask1 - mask2] 表示剩余的滅火點用前i個無人機去滅火，最終求出多無人機的飛行路徑paths和總滅火時間。

模型假設(shè)如下。1）著火點的火勢由中心勻速環(huán)狀向外蔓延，蔓延半徑和時間成正比。2）各無人機的救援速度相同。3）無人機同型號且飛行速度相同。4）出救點的資源儲備滿足火點的總需求。

目標函數(shù)min_Tp。

式中：Tp為搜救時間；Vij為第i個著火點到第j個著火點距離（第0個點為救援點）；ri為第i個著火點初始火勢大?。籿di為第i個著火點火勢蔓延速度；vf為無人機飛行速度；Vu為無人機搜救速度。

3 案例分析

3.1 案例

為驗證多無人機協(xié)同任務分配模型的有效性，本文以2010年大興安嶺呼中林業(yè)局呼中林區(qū)發(fā)生火災為背景，根據(jù)調(diào)查有7個著火點，火災于7月3日11時被撲滅。各火點之間的距離如圖3所示、氣象以及地理數(shù)據(jù)見表1～表3。本文采用貪心算法和狀態(tài)壓縮DP算法進行求解。所有搜救無人機均從同一起點飛入各自負責的子區(qū)域。已知該型號的搜救無人機性能如下：升限高度為6700m，最大載油量為5000mL，油耗系數(shù)λ1=λ2= 0.05；該型號搜救無人機的搜救能力如下：橫向視場角α= 60°，縱向視場角β= 60°，對發(fā)生火災區(qū)域進行標記，分別為 A、B、C、D、E、F和G 共7個地區(qū)。

表1 著火點氣象數(shù)據(jù)

表2 著火點的地理數(shù)據(jù)

表3 各著火點的火勢蔓延速度

圖3 著火點之間距離

出救點目前有3架無人機向7個著火點進行搜救。

3.2 仿真結(jié)果

基于改進動態(tài)規(guī)劃算法和貪心算法仿真結(jié)果，假設(shè)有3架無人機，飛行速度分別為80km/h、85km/h、90km/h、95km/h以及100km/h，對比如圖4和圖5所示。

圖4 算法對比結(jié)果一

圖5 算法對比結(jié)果二

對比訓練結(jié)果可知，固定無人機數(shù)量和無人機飛行速度，無人機救援速度在15km/h～20km/h，貪心算法的救援時間比動態(tài)規(guī)劃算法的救援時間更短，而無人機救援速度在10km/h～15km/h，動態(tài)規(guī)劃算法的救援時間比貪心算法的救援時間更短。然而實際救援速度大部分在10km/h～15km/h，因此改進的動態(tài)規(guī)劃算法更有優(yōu)勢。

4 結(jié)語

本文研究了多UAV對于動態(tài)任務分配的問題，在綜合考慮UAV能耗、視程等自身性能約束，執(zhí)行任務環(huán)境約束等條件的情況下建立以UAV搜救時間最短為目標的任務分配模型。1）根據(jù)搜救任務的動態(tài)變化趨勢選取符合搜救環(huán)境的UAV，滿足搜救任務的穩(wěn)定性。2）狀態(tài)壓縮DP以更快的速度進行狀態(tài)轉(zhuǎn)移和計算，因為狀態(tài)的表示更緊湊。這可以降低計算復雜度，使任務分配問題的求解時間更短，特別是對于大型復雜任務分配問題來說。