無人機(jī)覆蓋路徑規(guī)劃中基于能量感知網(wǎng)格的三維避障算法的研究

趙其定，汪夏榮

（1.江西經(jīng)濟(jì)管理干部學(xué)院 飛行技術(shù)學(xué)院，江西 南昌 330088；2.深圳市大疆創(chuàng)新科技有限公司，上海 200120）

0 引言

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

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

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

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

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

1 基于能量感知的三維網(wǎng)格避障

1.1 基本原理

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

圖1 兩種不同的避障方式

1.2 系統(tǒng)準(zhǔn)備工作

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

圖2 無人機(jī)覆蓋路徑俯視圖

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

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

圖3 無人機(jī)飛行正視圖

2 掃描尺寸及熱圖的生成

2.1 掃描框架尺寸的確定

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

圖4 無人機(jī)在A 點(diǎn)的正面視圖

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

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

圖5 無人機(jī)掃描區(qū)域尺寸

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

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

2.2 熱圖的生成及無人機(jī)避障路徑

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

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

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

Γ表示為網(wǎng)格中一組非零單元（Γ=Γ）：

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

圖6 框架中樹狀熱圖

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

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

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

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

圖7 反向螺旋循環(huán)模式尋找外圍為0 單元

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

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

圖8 獲取的周邊網(wǎng)格

圖9 細(xì)分后的熱圖新的解決方案集

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

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

圖11 障礙物檢測與規(guī)避算法流程圖

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

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

3 評估指標(biāo)和結(jié)果

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

3.1 評估指標(biāo)

網(wǎng)格中的單元可以被看作是一個類似圖的結(jié)構(gòu)（，）中的頂點(diǎn)，其中是頂點(diǎn)列表，是邊的列表。表示的是細(xì)分前的網(wǎng)格單元中心，將其視為圖中一個頂點(diǎn)，如圖12所示，每個頂點(diǎn)在笛卡爾平面上都有坐標(biāo)。

圖12 無人機(jī)轉(zhuǎn)彎角度

3.1.1 轉(zhuǎn)彎角度

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

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

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

3.1.2 完成時間

優(yōu)化軌跡長度和任務(wù)完成時間對于節(jié)能至關(guān)重要，無人機(jī)的路徑規(guī)劃技術(shù)，任務(wù)完成時間主要是飛行時間和依靠公式11 來表示為的完成時間：

其中為路徑長度，為無人機(jī)速度，而v 為轉(zhuǎn)彎次數(shù)，Φ為第次轉(zhuǎn)彎的角度，為無人機(jī)旋轉(zhuǎn)速率。

3.1.3 能量消耗

無人機(jī)的總能量成本表示為是行駛總距離所消耗的能量，表示（）和執(zhí)行轉(zhuǎn)彎所消耗的能量表示為（）：

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

3.2 結(jié)果

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

圖13 飛行區(qū)域網(wǎng)格圖

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

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

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

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

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

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

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

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

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

圖18 基本方法無人機(jī)總路徑

圖19 EATOA 方法無人機(jī)總路徑

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

表1 基本方法和EAEO 方法仿真結(jié)果參數(shù)

仿真結(jié)果表明在三維路徑中，與基本方法獲得的結(jié)果相比任務(wù)完成時間平均減12.40%，無人機(jī)能量消耗節(jié)省了10.89%。應(yīng)該指出的是，速度和旋轉(zhuǎn)率之間的變化對完成任務(wù)的時間有影響，但對能耗沒有影響。能源增加10.89%，這是因?yàn)楹褪瞧骄偰芎模畹漠a(chǎn)生是由于距離、轉(zhuǎn)彎的平均能耗。

4 結(jié)論

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