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

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

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

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

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

1 無人機-環境約束模型

1.1 風力風速約束模型

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

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

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

1.2 能見度約束模型

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

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

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

通常可以用太陽的高度角和太陽方位角來描述光照角度。這2個參數對拍攝圖像的清晰度和質量有重要影響，如圖1所示。

圖1 太陽光照角度

光照角度和方位角關系式如公式（6）所示。

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

1.4 搜救無人機視程約束

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

圖2 搜救無人機動態視程示意圖

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

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

1.5 無人機動態搜救油耗約束

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

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

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

2.1 火勢蔓延模型

模型假設如下。

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

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

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

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

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

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

2.2 基于狀態壓縮動態規劃算法建模

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

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

目標函數min_Tp。

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

3 案例分析

3.1 案例

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

表1 著火點氣象數據

表2 著火點的地理數據

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

圖3 著火點之間距離

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

3.2 仿真結果

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

圖4 算法對比結果一

圖5 算法對比結果二

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

4 結語

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