無人機覆蓋路徑規劃中基于能量感知網格的三維避障算法的研究

趙其定，汪夏榮

（1.江西經濟管理干部學院 飛行技術學院，江西 南昌 330088；2.深圳市大疆創新科技有限公司，上海 200120）

0 引言

無人駕駛飛行器（Unmanned Aerial Vehicle,UAV）也稱為無人機，近年來的使用率增長非常迅速，在很多領域都有應用，如電力巡檢、攝影攝像、應急救援、地形探測、智慧警務等等。在無人機的研究中如何規避障礙，尋找安全的飛行路徑也是無人機研究的熱門領域之一。覆蓋路徑規劃（Coverage Path Planning,CPP），在無人機飛行區域中為其建立一條路徑能夠探索該區域中關鍵的位置點，CPP 主要的關注點是時間效率和覆蓋的完整性。CPP 工作主要有以下幾個方面的性能指標，如路徑長度、任務完成時間和轉彎次數，同時這些指標與無人機能量消耗有關。

覆蓋路徑規劃CPP 的主要挑戰之一是區域中出現障礙物或突發的威脅建立路徑。在規劃區域中可能存在障礙物和禁飛區域區，障礙物可能是靜態的或移動的，如樹木和鳥類。突發性的威脅是無人機在事先不知道的情況下出現影響無人機安全的物體，不同的路徑規劃方法主要依賴于區域場景的二維或三維信息來構建飛行軌跡。

目前三維路徑規劃的最新方法是利用三維視圖來檢測和避開障礙物，這種方法沒有考慮無人機在避障過程中的資源消耗。在本文的工作中，提出了一種具有能量感知的三維避障方法（Energy-Aware Grid Based 3D Obstacle Avoidance,EGTOA），使用基于網格技術在三維視圖中避開障礙物的能力為無人機區域覆蓋規劃合理路徑。

三維路徑規劃有著明顯的優勢，與二維路徑規劃不同，二維路徑規劃有圖形上的限制。二維解決方案不僅受到無人機尺寸、重量和飛行機制的限制，還應該考慮航路長度、區域覆蓋率和能量消耗間的最優化解決方案。無人機在覆蓋任務中的轉彎次數也是一個需要考慮的問題，轉彎次數盡量減少，能夠節約更多的無人機能源消耗。

本文提出了一個基于能量網格的覆蓋路徑規劃和一個三維避障技術，結合了包括障礙物在內區域的頂視圖和正面視圖，在包括障礙物的區域內利用該算法頂視圖離線生成第一條路徑，然后用場景的正視圖重新規劃。文中處理的障礙物是靜態障礙物，這些障礙物的位置對無人機來說是預先知道的，目標是以最短的路徑和最少的轉彎次數避開障礙物，還要考慮到兩個主要因素，就是無人機的能源消耗和完成時間。

1 基于能量感知的三維網格避障

1.1 基本原理

基于網格原理的避障是通過移動來避開包含障礙物的整個單元格而移動到另一個相鄰的網格單元。如圖1所示，第二行中的障礙物1 是通過移動到單元格的邊緣來避免，但是在第三行中，另一個障礙物2 是通過繞行來避開障礙物。這兩種方式中繞道而行的轉彎次數少，路徑也相對較短。在2.2 節中，展示了采用這種方法進行障礙物的規避，由于利用二維頂視圖并不提供最短的路徑或確保最佳的覆蓋范圍，通過利用三維信息擴展了基本方法，依靠該區域的正面視圖來決定障礙物的位置和形狀以及要繞行的路線從而降低轉彎次數及距離。

圖1 兩種不同的避障方式

1.2 系統準備工作

在網格避障原理中，區域被劃分為網格單元，每個網格單元有一個矩形的形狀這是無人機需要在飛行過程中覆蓋的區域。為了達到良好的區域覆蓋，無人機的飛行軌跡是一個環形軌跡。在飛行過程無人機投射的飛行軌跡覆蓋相應的單元格。如圖2所示，深色代表自由區域，淺色是障礙區域，初始的計劃軌跡從網格單元邊緣開始，并穿過單元格的中心。

圖2 無人機覆蓋路徑俯視圖

在圖1 中，用G表示一個網格單元，用P表示經過G中心的垂直平面，同一網格列上的兩個連續平面P和P距l 個單位，其中l 是G的長度。在本文中，假設障礙物的位置是固定且已知的，通過三維信息來避免它們，利用二維圖所規劃的原始路徑，無人機將按照該路徑飛行，并在包含障礙物的單元前，無人機捕獲前面區域的圖像，以便決定無人機接下來的飛行路徑。

如圖3所示，假設在平面中有障礙物，圖中虛線代表圖3 中的原始路徑，實線代表新的軌跡，是無人機根據障礙物的位置。這項工作的目的是為無人機確定一個新的位置并且在維持總路徑和能量不變的情況下使得無人機的能量消耗最低。

圖3 無人機飛行正視圖

2 掃描尺寸及熱圖的生成

2.1 掃描框架尺寸的確定

無人機在飛行過程中要確定正視圖的框架尺寸，這樣在避障過程中才通過能量感知網格進行判斷定位無人機的下一個位置。如圖4所示三維視圖中，（i，j）平面表示無人機飛行區域俯視圖，（i，k）平面表示表示無人機飛行的正視圖。

圖4 無人機在A 點的正面視圖

確定無人機在（i，j）平面上的位置后，通過規劃確定無人機的最小和最大允許高度范圍分別表示為和，這個范圍將指定面對區域的框架尺寸，把表示為掃描的正面框架，假設無人機位于點，高度為h。

如圖5所示，框架由矩形ABCD 表示面積為×，其中和分別矩形的長度和寬度，矩形的長=（-），假設主視圖是以相機角度=62°拍攝的在這個角度之外檢測到的任何物體都不會對無人機造成任何危險。點是點的投影，這兩點實際上都是平面上兩個連續網格單元的中心（i，j），為了計算掃描框架的長度（BC）和寬度（AB），先要確定從矩形金字塔的尺寸（ABCDP），通過采取等腰三角形（PFH），其角度為，高度=PM。邊PF（表示為）可以從以下方程（1）計算出來，因為PM 是已知的，并且等于俯視圖網格單元的長度。

圖5 無人機掃描區域尺寸

因此，幀的長度可以按以下方式計算。

現在已經知道了框架的尺寸，下一步是將轉換為基于網格的形式用表示，中每個單元的尺寸與無人機的高度和寬度相適應。v表示為位于網格中第行和第列的單元，其尺寸為×（為長度，為寬度）。

2.2 熱圖的生成及無人機避障路徑

在本節中，目的是確定無人機必須移動的最近位置，以便于避開途中的障礙物，主要步驟如下：

步驟1：生成幀的熱圖，舉例來說，如圖6所示，顯示了一個20×40 一棵樹的熱圖。

其中v代表中的一個網格單元元素，Γ表示網格中零單元的集合。

Γ表示為網格中一組非零單元（Γ=Γ）：

如圖6所示，是框架中樹狀熱圖的例子，無人機的位置是（12，13），圖中虛線方框代表邊界單元，而實線方框代表解決方案的單元。

圖6 框架中樹狀熱圖

步驟2：代表的是無人機在框架中的投影，檢查它在網格中的位置，如果位于Γ中的一個單元，那么無人機的道路上就沒有障礙物，當前路徑就不會被修改。如果位于一個非零單元（即Γ中的一個單元），那么障礙物就存在于無人機的飛行路徑上，此時無人機飛行的路徑就需要修改，同時需要檢查周圍網格列表，為無人機找到一個合理路徑避開障礙物。用N來表示一個網格單元v的鄰居，它是直接圍繞著v的單元的列表。

用B表示為Γ中與最近的非零單元格見公式（7），稱為邊界單元，將（，）表示為兩點和之間的歐幾里得距離：

為了找到距離v最接近和B，使得v屬于Γ，用S的集合它的解，其中表示直接包圍B低能量值網格的數量：

為了找到列表S的解，從開始以反向螺旋循環模式如圖7所示，直到找到一個包含v=0 的外圍單元。

圖7 反向螺旋循環模式尋找外圍為0 單元

如圖6所示，無人機的投影位于網格中的單元格（12，13）。一組邊界單元B由實線框表示（|B|=3），可能的解S是由實線框表示（|S|=3），需要注意的是，如果S=null，則規劃必須增加框架尺寸。

步驟3：從S中選擇最便捷的解決方案，表示為=B∪S；如圖8所示，將每個單元格分成四個子單元格，如圖9所示，這是為了更好地了解障礙物的位置，以確定無人機移動最近的下一個位置。單元格細分后，一個新的解集?S生成，如圖10所示，深色背景區域代表無人機必須移動到的單元格以遍避開障礙物。

圖8 獲取的周邊網格

圖9 細分后的熱圖新的解決方案集

圖10 細分后的熱圖—陰影部分是最佳解決方案

如圖11所示的流程圖展示了工作中的主要步驟，算法檢查當前無人機在面對區域中的單元格位置，如果位于一個零值單元中，它將成為無人機的位置，否則該算法將檢查鄰近的單元，以找到最近的非零值單元格。

圖11 障礙物檢測與規避算法流程圖

在周圍尋找可能解S的列表，從開始以螺旋模式包圍網格周圍，解決方案列表通過篩選以選擇最接近的可能解決方案單到，這可能是下一個無人機的位置。

為了確定周圍障礙物的邊界，找到邊界單元的列表，表示為B，將S和B組合在一個分組框中，并決定無人機是否會安全地通過求解單元，對單元進行細分，這有助于找到比細分之前找到的更接近的更好解決方案。將每四個零值子單元分組在一個頂點中（表示為），這些頂點的列表表示為（S）0，稍后使過濾以找到確切的無人機位置（表示為Sposition）。

3 評估指標和結果

在無人機飛行避障過程中，沿無人機路徑具有不同物形狀的障礙物體，需要評估無人機的工作效果，主要從能源消耗、完成時間、路徑長度和轉彎角度進行評估。

3.1 評估指標

網格中的單元可以被看作是一個類似圖的結構（，）中的頂點，其中是頂點列表，是邊的列表。表示的是細分前的網格單元中心，將其視為圖中一個頂點，如圖12所示，每個頂點在笛卡爾平面上都有坐標。

圖12 無人機轉彎角度

3.1.1 轉彎角度

無人機的功耗受轉彎角度的影響，在飛行期間轉多少個彎是一個主要問題，假設無人機從頂點到并且將在處轉彎，稍后前往，如圖12所示。轉彎角計算公式為：

其中cos（∠）是根據中的余弦定律計算的。因此可以找到角度從頂點之間的歐幾里得距離，公式如下。

其中e=（v，v）是兩個頂點v和v之間的歐幾里得距離。

3.1.2 完成時間

優化軌跡長度和任務完成時間對于節能至關重要，無人機的路徑規劃技術，任務完成時間主要是飛行時間和依靠公式11 來表示為的完成時間：

其中為路徑長度，為無人機速度，而v 為轉彎次數，Φ為第次轉彎的角度，為無人機旋轉速率。

3.1.3 能量消耗

無人機的總能量成本表示為是行駛總距離所消耗的能量，表示（）和執行轉彎所消耗的能量表示為（）：

其中是單位距離消耗的能量，是每角度消耗的能量，在這項工作中，假設=0.116 4 kJ/m 和=0.017 3 kJ/°。

3.2 結果

假設一個情景飛行的區域是100 m×115 m，俯視網格是6 行10 列，如圖13所示，圖中無人機在虛線內覆蓋飛行，四角形標記的單元包含障礙物，將總的軌跡路徑將與基本方案中獲得的軌跡路徑進行比較。對于框架的尺寸，假設中每個網格單元為0.7×0.5，為40 行×24 列，假設無人機位于10.2 m 高處，面對中的（12，13）單元，下一步將介紹能量圖和無人機在每個障礙物上的位置。

圖13 飛行區域網格圖

第一步，假設障礙物為一棵高度為15 m 的樹，如圖6所示。無人機在障礙物的投影為（12，13），無人機選擇通過網格解決方案如圖14所示，執行水平左轉彎3°，垂直向下轉3°，然后減掉11.57 m 的距離。初始無人機的位置和新無人機的位置Sposition，為了到達樹后的初始高度，執行6°的垂直回升，跨越同樣的距離。

圖14 無人機在障礙物1 的投影位置熱圖

障礙物二假設無人機位于障礙物棕櫚樹的網格單元（13，5）處，無人機的投影是（13，5）如圖15所示。圖15 顯示了細分后的能量圖，最近的邊界單元是（13，1），無人機通過該單元時進行了16°的垂直向上轉彎，然后減掉11.985 m 的距離，接著是一個垂直向下的轉彎33°，無人機返回到障礙物后面的初始高度，畫實線的單元代表解決方案單元即最終的無人機位置Sposition。

圖15 無人機在障礙物2 的投影位置熱圖

障礙三假設無人機飛到樹的一個地方，該地方的無人機位置投影是（8，9），最近的邊界和解決方案單元格如圖16所示，線框代表解決方案單元格即最終無人機位置Sposition。無人機穿過障礙物，首先進行水平轉彎2°，然后垂直向上轉彎2°，減去11.506 m，然后垂直向下轉彎3°，回到障礙物后面的初始高度，再轉一圈，回到初始方向。

圖16 無人機在障礙物3 的投影位置熱圖

障礙四假設障礙物是建筑物的一部分，熱圖如圖17所示。無人機的位置投影是單元格（6，8），細分單元格（3，8）被選為解Sposition，虛線單元代表邊界集B，實線方框單元代表解單元S，最終的無人機位置在圖17 中表示實線方框。無人機將通過該單元，它進行了一個28°的水平轉彎，減少了13.07 m 的距離，然后又進行了一次57°的水平轉彎，之后返回到初始路徑方向。

圖17 無人機在障礙物4 的投影位置熱圖

在任務結束時，基本方法的結果路徑如圖18所示，采用EATOA 獲得的總路徑如圖19所示。

圖18 基本方法無人機總路徑

圖19 EATOA 方法無人機總路徑

這些路徑是從俯視圖看到的，采用不同軌跡規避算法的總軌跡路徑。從不同的角度來看，工作軌跡計劃與基本方法進行了比較，無人機速度是8 m/s，無人機旋轉速度為30 °/s，如表1所示，顯示了EATOA 比基本方法的完成時間縮短12.40%，能量減低了10.89%。應該注意到三維路徑比基本方法中的二維路徑短4.1%，總轉角減少25.1%。

表1 基本方法和EAEO 方法仿真結果參數

仿真結果表明在三維路徑中，與基本方法獲得的結果相比任務完成時間平均減12.40%，無人機能量消耗節省了10.89%。應該指出的是，速度和旋轉率之間的變化對完成任務的時間有影響，但對能耗沒有影響。能源增加10.89%，這是因為和是平均總能耗，偏差的產生是由于距離、轉彎的平均能耗。

4 結論

在路徑規劃任務期間提出了一種基于能量感知網格的3D 避障。該算法被命名為EATOA 并且有兩個階段，它首先使用區域頂視圖網格，然后掃描該區域的正面視圖以檢測無人機路徑上的障礙物，通過得到的能量感知網格算法在線重新規劃路徑，尋找合理路徑繞過障礙物。結果顯示EATOA方法能夠節省能量和完成時間。在未來的工作中測試算法在嘈雜環境和動態障礙中的實際飛行情況，還打算利用動態規劃來優化算法提高算法的性能。