趙其定，汪夏榮

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

0 引言

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

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

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

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

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

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

1.1 基本原理

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

圖1 兩種不同的避障方式

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

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

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

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

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

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

2 掃描尺寸及熱圖的生成

2.1 掃描框架尺寸的確定

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

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

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

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

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

因此，幀的長(zhǎng)度可以按以下方式計(jì)算。

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

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

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

步驟1：生成幀的熱圖，舉例來(lái)說(shuō)，如圖6所示，顯示了一個(gè)20×40 一棵樹(shù)的熱圖。

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

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

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

圖6 框架中樹(shù)狀熱圖

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

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

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

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

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

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

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

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

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

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

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

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

在周?chē)鷮ふ铱赡芙?span id="ldphhfj" class="emphasis_italic">S的列表，從開(kāi)始以螺旋模式包圍網(wǎng)格周?chē)?，解決方案列表通過(guò)篩選以選擇最接近的可能解決方案單到，這可能是下一個(gè)無(wú)人機(jī)的位置。

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

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

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

3.1 評(píng)估指標(biāo)

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

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

3.1.1 轉(zhuǎn)彎角度

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

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

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

3.1.2 完成時(shí)間

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

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

3.1.3 能量消耗

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

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

3.2 結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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