薛鎮(zhèn)濤，陳建,*，張自超, 2，劉旭贊，苗憲盛，胡貴

1. 中國農(nóng)業(yè)大學(xué) 工學(xué)院，北京 100083

2. 武漢大學(xué) 測繪遙感信息工程國家重點(diǎn)實(shí)驗(yàn)室，武漢 430079

在無人系統(tǒng)導(dǎo)航過程中，路徑規(guī)劃已經(jīng)成為最值得研究的問題之一[1]。而其中的全覆蓋路徑規(guī)劃[2](Coverage Path Planning)是無人系統(tǒng)規(guī)劃1條避開所有障礙物且遍歷目標(biāo)地塊的最短路徑過程，在農(nóng)業(yè)生產(chǎn)[3]、城市管理[4]、室內(nèi)清掃[5]等方面都有較多的運(yùn)用。在二維空間下全覆蓋路徑規(guī)劃的運(yùn)用背景和無人系統(tǒng)類型雖然大有不同，但最終規(guī)劃目標(biāo)基本相同，即在路徑覆蓋過程中，在保證覆蓋所有目標(biāo)區(qū)域以及盡量沒有重復(fù)覆蓋的前提下，使得總覆蓋路徑長度最短。

伴隨無人機(jī)的廣泛運(yùn)用以及多無人機(jī)協(xié)同技術(shù)的發(fā)展，無人機(jī)飛行抗擾以及避障技術(shù)逐漸成熟[6]，多無人機(jī)覆蓋路徑規(guī)劃問題也逐漸成為了研究中的重點(diǎn)，如何讓無人機(jī)在覆蓋路徑過程中能夠節(jié)省能源、提高工作效率成為多無人機(jī)覆蓋路徑規(guī)劃的重點(diǎn)和難點(diǎn)。而改善工作效率和能耗的關(guān)鍵就是在覆蓋過程中盡量使得覆蓋路徑有效，通過優(yōu)化縮短轉(zhuǎn)移路徑和減少轉(zhuǎn)彎次數(shù)，可以保證無人系統(tǒng)的工作路徑最優(yōu)。

在以往的研究中，牛耕法作為最早的全覆蓋路徑規(guī)劃方法成為了經(jīng)典的無人系統(tǒng)行進(jìn)規(guī)劃方式。但在標(biāo)準(zhǔn)地塊中，作業(yè)方向顯然成為了影響牛耕法性能的重要因素，且一旦地塊形狀復(fù)雜則會使得作業(yè)軌跡無法閉合，無法完成全覆蓋路徑規(guī)劃。根據(jù)地塊的復(fù)雜程度，學(xué)者們不斷在此基礎(chǔ)上進(jìn)行改進(jìn)，針對不同環(huán)境給出了不同優(yōu)化求解方法，在全覆蓋路徑規(guī)劃綜述[7-9]中也有所介紹。覆蓋路徑的方法大致分為經(jīng)典算法和啟發(fā)式算法，其中經(jīng)典算法又分為圖搜索法、單元分解法、線掃分解法、柵格法、人工勢場法等，而啟發(fā)式算法主要有遺傳算法、模擬退火算法、粒子群(Partical Swarm Optimation, PSO)算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)算法等。

在初始的地塊輪廓方面，針對自然地塊輪廓的不規(guī)則性和復(fù)雜性，有較多學(xué)者進(jìn)行了研究。于靖等[10]就自然矢量岸線壓縮問題提出了1種基于最小二乘法、通過篩選凸點(diǎn)三角形面積大小的改進(jìn)的道格拉斯-普克(Douglas-Peucker)算法，在保證信息丟失度低的前提下有較好的壓縮比。李星燁[11]在對輪廓凹點(diǎn)進(jìn)行劃分的過程中，通過討論凹點(diǎn)形狀，確定決策距離，從而進(jìn)行近似消除，但對于形狀特殊的凹多邊形的處理仍然有缺陷。吳青坡等[12]對外界輪廓采用多邊形寬度和最小外接矩形，對不規(guī)則多邊形離散化求解，給出可以進(jìn)行全覆蓋路徑規(guī)劃的柵格圖。

在凸劃分覆蓋地塊方面，陳海等[13]通過對不含有障礙物的地塊進(jìn)行凸劃分，建立劃分后的銜接關(guān)系，并根據(jù)不同無人機(jī)的性能調(diào)整劃分面積，給出合理的多無人機(jī)覆蓋路徑。戴健等[14]在對非凸區(qū)域的劃分方法的討論中，采用對凹點(diǎn)做分割線并旋轉(zhuǎn)的方法，根據(jù)覆蓋路徑長度來確定凹口的分割角度，達(dá)到合理的凸劃分，但對于其他劃分情況依然沒有考慮完全。Vinh等[15]對凹區(qū)域和復(fù)雜區(qū)域進(jìn)行凸多邊形包圍，再進(jìn)行多無人機(jī)覆蓋路徑任務(wù)的分配和協(xié)調(diào)，但凸多邊形包圍會導(dǎo)致地塊的輪廓失真嚴(yán)重。Nielsen等[16]從多邊形邊上擴(kuò)展，通過組合子地塊保證整體最小寬度，從而保證覆蓋路徑較短，但沒有考慮到算法對復(fù)雜地塊的適用性。

在確保覆蓋路徑滿足作業(yè)需求方面，Rantanen和Juhola[17]采用基于領(lǐng)域的方法過濾掉一些不必要的節(jié)點(diǎn)，改進(jìn)后的隨機(jī)路標(biāo)法仍然保持較好的覆蓋率，能夠保證覆蓋路徑的完整性。Le等[18]將覆蓋機(jī)器人設(shè)計(jì)為四菱形，并將整體地圖設(shè)計(jì)成含有各種鋪貼圖案的多路點(diǎn)連接圖，運(yùn)用遺傳算法以及蟻群算法優(yōu)化最短路徑，但對地塊考慮過于簡單。闞平等[19]為提高多植保無人機(jī)協(xié)同作業(yè)效率，在保證各架無人機(jī)滿足約束的情況下，用改進(jìn)PSO算法實(shí)現(xiàn)了無人機(jī)返航順序和返航點(diǎn)位置的尋優(yōu)。周林娜等[20]融合單元分解法與神經(jīng)網(wǎng)絡(luò)算法對礦區(qū)廢棄地的全覆蓋路徑進(jìn)行了優(yōu)化。李楷等[21]基于回溯法，解決了局部區(qū)域覆蓋過程中存在遺漏區(qū)域的問題，降低了覆蓋路徑的重疊率，給出1條光滑無障礙路徑，但運(yùn)用的是簡單的柵格地圖。Hassan和Liu[22]基于捕獵者-獵物方法通過開發(fā)新型的自適應(yīng)覆蓋路徑規(guī)劃方法，可以有效地實(shí)時(shí)響應(yīng)邊界變化并給出最小的成本實(shí)現(xiàn)完全覆蓋，但是其方法基于簡單的柵格地圖。

而無人機(jī)路徑規(guī)劃也與覆蓋路徑規(guī)劃問題有著較大相關(guān)性，Guo等[23]運(yùn)用改進(jìn)的深度增強(qiáng)學(xué)習(xí)的方法解決了無人機(jī)路徑規(guī)劃問題，并運(yùn)用仿真證明了方法的有效性和優(yōu)越性。Liu等[24]針對粒子群優(yōu)化收斂慢與容易陷入局部最優(yōu)的問題設(shè)計(jì)了1種空間精細(xì)投票機(jī)制，并引入時(shí)空碰撞避免技術(shù)來避免無人機(jī)的碰撞，規(guī)劃出多無人機(jī)四維協(xié)調(diào)路徑。Qu等[25]通過灰狼優(yōu)化器與共生生物搜索混合算法，生成平滑的無人機(jī)飛行路徑，加快了生成路徑的收斂速度并保證整體搜索的能力。Liu等[26]提出1種基于雙層規(guī)劃的無人機(jī)實(shí)時(shí)路徑規(guī)劃方法，嵌入5種啟發(fā)式優(yōu)化策略的離散化算法用于加速規(guī)劃，并在仿真中證明了該方法的效率和適用性。杜楠楠等[27]提出基于無向圖搜索的方式，并通過混合整數(shù)線性規(guī)劃的方法求解每架無人機(jī)的最優(yōu)飛行路徑。

以上文獻(xiàn)都對地塊優(yōu)化和覆蓋路徑規(guī)劃有突出貢獻(xiàn)，但面對更加復(fù)雜的覆蓋地塊環(huán)境時(shí)，會逐漸暴露出以下問題：

1) 沒能避免或減少凹多邊形對于覆蓋路徑的直接影響，消除關(guān)鍵的凹點(diǎn)影響路徑優(yōu)化的最終效果。

2) 沒有考慮有障礙物的凹多邊形如何進(jìn)行覆蓋路徑規(guī)劃或者有障礙物的凹多邊形如何進(jìn)行凸劃分優(yōu)化。

針對以上問題，對含障礙物的復(fù)雜地塊進(jìn)行凸劃分優(yōu)化與覆蓋路徑規(guī)劃研究。

1 復(fù)雜地塊的定義以及輪廓近似壓縮

在一般自然地形下，邊界具有隨機(jī)性，往往并不是規(guī)則圖形，含有曲邊和凹陷，邊界崎嶇，較難針對特征進(jìn)行一定的分割。將不規(guī)則地塊邊界定義為含有曲線邊緣且無頂點(diǎn)的地塊邊界，無法采用分割線DL對其進(jìn)行有效分割，不規(guī)則邊界顯然成為地塊分割的重要障礙，需要進(jìn)行處理后才能進(jìn)行劃分操作，如圖1所示。

圖1 不規(guī)則邊界無劃分特征

復(fù)雜地塊的定義為含有1個(gè)或1個(gè)以上的凹陷邊緣且含有不規(guī)則地塊邊界的輪廓地塊，而含有的復(fù)雜障礙物定義為含有不規(guī)則邊界并完全包含于地塊中的圖塊。因此，本文針對復(fù)雜地塊及復(fù)雜障礙物無法進(jìn)行凸劃分處理，采用近似壓縮的方法。較多前人研究過程中都會涉及到對于邊界的確定，復(fù)雜的地塊邊界會影響覆蓋路徑算法效果，故需要對復(fù)雜地塊進(jìn)行簡化。復(fù)雜地塊輪廓對覆蓋路徑的影響如圖2所示。

圖2 復(fù)雜地塊對覆蓋路徑的影響

多邊形作為1種規(guī)則圖形，將復(fù)雜地塊的邊界輪廓近似壓縮為復(fù)雜多邊形，只要保證邊界壓縮不高于一定的誤差率，就可以使得地塊邊界壓縮成為一定的復(fù)雜多邊形。顯然外輪廓和障礙物輪廓的壓縮近似是不同的，假設(shè)地塊輪廓外是可飛區(qū)域，但無需覆蓋，而障礙物內(nèi)部是禁飛區(qū)域，若覆蓋路徑越過，則會影響飛行安全，故需要分別進(jìn)行討論。

1.1 復(fù)雜地塊的邊界輪廓近似壓縮

當(dāng)目標(biāo)覆蓋地塊的邊界出現(xiàn)如邊界為光滑曲線或者邊界過于彎曲等復(fù)雜情況,使得目標(biāo)地塊為復(fù)雜地塊，此時(shí)需要運(yùn)用改進(jìn)的Douglas-Peucker算法[10]對目標(biāo)地塊進(jìn)行簡化，首先需要對連續(xù)邊界進(jìn)行矢量化規(guī)定，按照逆時(shí)針對邊界進(jìn)行排序，之后運(yùn)用Douglas-Peucker算法對曲線二分近似，得到后期可以進(jìn)行凸劃分的外部輪廓, Douglas-Peucker算法的步驟如圖3所示。整體算法流程如下：

步驟1原本的復(fù)雜邊界，進(jìn)行鏈碼操作，得到邊界各個(gè)像素點(diǎn)的順序。

步驟2邊界線被分割為基于端點(diǎn)的線段，并尋找最遠(yuǎn)點(diǎn)。

步驟3找到相距初始線段垂直距離最遠(yuǎn)頂點(diǎn)并不斷連接，并重復(fù)步驟2。

步驟4當(dāng)循環(huán)后的線段垂直距離平均誤差低于給定誤差，認(rèn)為多邊形近似建立成功，連接各個(gè)頂點(diǎn)。

圖3 改進(jìn)Douglas-Peucker過程[10]

最終通過選擇合適的誤差區(qū)間，得到壓縮后的復(fù)雜地塊輪廓圖，并運(yùn)用到接下來的地塊凸劃分優(yōu)化中。

1.2 復(fù)雜地塊中復(fù)雜障礙物輪廓近似壓縮

不僅復(fù)雜地塊會對覆蓋路徑的生成增加難度，復(fù)雜障礙物也會使得覆蓋路徑規(guī)劃較為困難，故首先要將這些圖形轉(zhuǎn)化為凸包。要在原有的復(fù)雜障礙物基礎(chǔ)上構(gòu)建凸集，即任意兩點(diǎn)的連線都是這個(gè)集合內(nèi)的子集。采用描繪出障礙物輪廓關(guān)鍵點(diǎn)，通過在障礙物輪廓上均勻取樣，從而得到原始點(diǎn)集，并根據(jù)內(nèi)折現(xiàn)象的增加適當(dāng)增加采樣點(diǎn)，規(guī)定每增加一個(gè)內(nèi)折數(shù)nf，采樣點(diǎn)數(shù)nc增加值為nz，故此時(shí)的采樣點(diǎn)數(shù)為

nc=nz·nf+nc0

(1)

式中：初始采樣點(diǎn)數(shù)nc0=50；增加值nz=10，從而達(dá)到復(fù)雜障礙物的所有點(diǎn)連線都在構(gòu)建的凸集內(nèi)。得到邊緣采樣點(diǎn)后，引入平面點(diǎn)集的凸包算法。該方法為經(jīng)典的卷包裹算法，卷包裹算法是從1個(gè)必然在凸包上的點(diǎn)開始向著1個(gè)方向依次選擇最外側(cè)的點(diǎn)，當(dāng)回到最初的點(diǎn)時(shí)，所選出的點(diǎn)集就是所要求的凸包，這里卷包裹算法的步驟如圖4所示，具體為

圖4 復(fù)雜障礙物輪廓采用改進(jìn)卷包裹算法的流程

1) 得到采樣后獲得的原始點(diǎn)集，處理的第1步就是將其中的nc個(gè)采樣點(diǎn)進(jìn)行排序，首先選擇橫坐標(biāo)最小同時(shí)縱坐標(biāo)最小的點(diǎn)，記為a0點(diǎn)，連接該點(diǎn)與其他所有點(diǎn)組成nc-1個(gè)向量。計(jì)算每個(gè)向量與y軸的負(fù)半軸之間的夾角，并按照夾角由小到大對所有點(diǎn)進(jìn)行排序并標(biāo)記，當(dāng)存在方向相同的向量則根據(jù)模的大小進(jìn)行排序，最終nc個(gè)點(diǎn)分別記作a1，a2，…，anc-1。

(2)

根據(jù)以上步驟得到的凸包邊緣點(diǎn)，按照順序連接線段，即可組成點(diǎn)集的二維凸包，如圖5所示。

圖5 具體地圖(頤和園)實(shí)現(xiàn)改進(jìn)卷包裹算法得到凸包

求解過程中卷包裹算法的復(fù)雜度是O(nc·nh)，nc是全部的采樣點(diǎn)數(shù)，nh是最終在凸包上的點(diǎn)數(shù)，算法的復(fù)雜度會隨著內(nèi)折數(shù)nf增大而增大。

2 凹凸頂點(diǎn)定義和凹凸頂點(diǎn)檢驗(yàn)

在得到了近似壓縮的凹凸頂點(diǎn)后，凹凸頂點(diǎn)對于全覆蓋路徑規(guī)劃有著不一樣的影響，需要對各個(gè)頂點(diǎn)凹凸性進(jìn)行廣義的定義。在最外輪廓中，定義外輪廓中的頂點(diǎn)構(gòu)成的矩陣為V=[VcVcc]，假設(shè)多邊形外頂點(diǎn)Vc=[v1v2…vi],多邊形中外凹頂點(diǎn)Vcc=[vi+1vi+2…vi+j]，其中i-2>j。而障礙物輪廓構(gòu)成矩陣為Vh=[VhcVhcc]，假設(shè)障礙物的多邊形內(nèi)頂點(diǎn)為Vhc=[vh1vh2…vhm]；障礙物多邊形中內(nèi)凹頂點(diǎn)為Vhcc=[vhm+1vhm+2…vhm+n]。且假設(shè)多邊形外頂點(diǎn)數(shù)量遠(yuǎn)大于內(nèi)部障礙物多邊形內(nèi)頂點(diǎn)數(shù)量，整體凸劃分過程中不存在邊界寬度的問題。定義了廣義的凹凸性頂點(diǎn)，此時(shí)就要利用凹凸性檢驗(yàn)來驗(yàn)明頂點(diǎn)的凹凸性。

為了將得到的邊界和障礙物進(jìn)行有效地凸劃分，此時(shí)需要對所有頂點(diǎn)的凸凹性進(jìn)行檢驗(yàn)，利用以當(dāng)前頂點(diǎn)為中心的矢量叉乘或者計(jì)算三角形的有符號面積，判斷多邊形的方向以及當(dāng)前頂點(diǎn)的凹凸性。頂點(diǎn)中心矢量叉乘運(yùn)算，也就是計(jì)算三角形面積，當(dāng)三角形面積為正時(shí)，該頂點(diǎn)為凸頂點(diǎn)；同理，當(dāng)三角形面積為負(fù)時(shí)，該頂點(diǎn)為凹頂點(diǎn)。

3 針對近似壓縮后復(fù)雜凹多邊形地塊的凸劃分優(yōu)化

3.1 含有障礙物的地塊凸劃分優(yōu)化

含有障礙物將會大大增加覆蓋路徑優(yōu)化的難度，為了方便覆蓋路徑規(guī)劃以及減少路徑轉(zhuǎn)彎次數(shù)，需要采用凸劃分的方式優(yōu)化地塊，進(jìn)而達(dá)到優(yōu)化覆蓋路徑的目的。

首先，考慮一般情況下，地塊邊緣都為凸多邊形，將內(nèi)頂點(diǎn)理解成偽凹頂點(diǎn)，根據(jù)不同的劃分，將地塊凸劃分的過程復(fù)雜度表示為T(i,0,m,n)，且最小寬度計(jì)算時(shí)間復(fù)雜度為O(i·j)。

地塊凸劃分會涉及到障礙物存在偽凹頂點(diǎn)的情況。主要采用4種策略對目標(biāo)地塊進(jìn)行凸劃分，分別是從偽凹頂點(diǎn)邊延伸進(jìn)行劃分、通過偽頂點(diǎn)連接進(jìn)行劃分、通過畫穿過偽凹頂點(diǎn)的外輪廓劃分、以及偽凹頂點(diǎn)和頂點(diǎn)之間連接劃分。

對于從偽凹頂點(diǎn)延伸進(jìn)行劃分，若非復(fù)雜障礙物情況下，延伸偽凹頂點(diǎn)邊可以有效將含有障礙物地塊的復(fù)雜度降低，此時(shí)地塊凸劃分的過程復(fù)雜度為

T(i,0,m,n)≤T(i1,j1,0,0)+T(i2,j2,0,0)+

O((m+1)·i·j)≤T(i,0,0,0)+

T(i,j2,0,0)+O((m+1)·i·j)≤

T(i,0,0,0)+T(i,m-2,0,0)+

O((m+1)·i·(m-2))=C1·i+

O(i2·(m-2)2)+O((m+1)·i·

(m-2))=O(i2·m2)

(3)

式中：C1為計(jì)算復(fù)雜度系數(shù)。

3.2 含有復(fù)雜障礙物的復(fù)雜地塊凸劃分優(yōu)化

前人研究表明，凹多邊形會使得覆蓋路徑的主線受到攔截，從而降低覆蓋路徑的效率[22]。在算力充裕的情況下，對含有障礙物的復(fù)雜凹多邊形凸劃分可以使得后期覆蓋路徑規(guī)劃算法效率更高。凸劃分就是將可能影響覆蓋路徑規(guī)劃算法的凹頂點(diǎn)劃分為子地塊，使得總覆蓋路徑長度更短。如圖6所示，在復(fù)雜凸多邊形中，主要基于4種凸劃分策略，優(yōu)化全地塊覆蓋路徑分配問題。

圖6 4種凸劃分策略示意圖

3.2.1 從凹頂點(diǎn)的1個(gè)邊緣延伸

凸劃分的目標(biāo)是將凹頂點(diǎn)進(jìn)行分解，由于劃分凹頂點(diǎn)時(shí)盡量保證某一凹頂點(diǎn)分解為1條外輪廓邊與1個(gè)凸頂點(diǎn)，從而降低覆蓋路徑的轉(zhuǎn)彎次數(shù)。而對于存在j個(gè)凹頂點(diǎn)的含障礙物的子地塊，則有2j種劃分方式，此時(shí)最復(fù)雜情況為分解出包含有障礙物的子地塊，此時(shí)凸劃分過程復(fù)雜度為

T(i,j,m,n)≤T(i1,0,m,n)+

O(i3·m3+i·j2)

(4)

根據(jù)復(fù)雜度分析得到凹頂點(diǎn)和凸頂點(diǎn)的數(shù)量，直接決定了算法的復(fù)雜度，且劃分后需要根據(jù)劃分線DL是否穿過障礙物，分析劃分的效果。凸劃分算法策略1具體偽代碼如算法1所示。

3.2.2 內(nèi)頂點(diǎn)與外頂點(diǎn)連接劃分

偽凹頂點(diǎn)與凹頂點(diǎn)是引起覆蓋路徑轉(zhuǎn)彎次數(shù)較多的主要因素，通過凸劃分可以減少2種頂點(diǎn)的數(shù)量。首先要對偽凹頂點(diǎn)進(jìn)行連接，保證外凹頂點(diǎn)優(yōu)先連接，之后是將內(nèi)頂點(diǎn)全部與外頂點(diǎn)相連接，此時(shí)凸劃分的復(fù)雜度為

(5)

算法1 從凹頂點(diǎn)的邊緣延伸Algorithm 1 Extending from an edge of concave vertex

通過連接頂點(diǎn)的劃分線不斷組合，將原先的塊劃分成2個(gè)封閉區(qū)域，從而達(dá)到凸劃分的目的。且對于各個(gè)分解后的地塊，覆蓋路徑最短為各種組合中的最優(yōu)組合。凸劃分算法策略2具體偽代碼如算法2所示。

算法2 內(nèi)外頂點(diǎn)的連接和劃分

3.2.3 平行外輪廓邊并經(jīng)過凹頂點(diǎn)實(shí)現(xiàn)劃分

在凸劃分過程中，保證分割后的地塊寬度盡可能較小，分割線就要與外輪廓線平行且過凹頂點(diǎn)分割，從而減少凹頂點(diǎn)個(gè)數(shù)。對于某1個(gè)凹頂點(diǎn)，那可以選擇的外輪廓邊為i+j-2，此時(shí)地塊劃分的復(fù)雜度為

T(i,j,m,n)≤T(i1,0,m,n)+

O(i3·m3+i2·j2)

(6)

在給出每個(gè)劃分線后，需要對于隨機(jī)選定的地塊給出最優(yōu)的劃分方式。凸劃分算法策略3具體偽代碼如算法3所示。

算法3 平行外輪廓邊并通過凹頂點(diǎn)劃分

3.2.4 連接外凹頂點(diǎn)與其他外頂點(diǎn)實(shí)現(xiàn)劃分

T(i,j,m,n)≤T(i1,0,m,n)+

(7)

通過凸劃分整體地塊，可以得到較好的劃分方式。凸劃分算法策略4具體偽代碼如算法4所示。

算法4 連接凹的頂點(diǎn)和頂點(diǎn)實(shí)現(xiàn)分割

4 凸劃分優(yōu)化與隨機(jī)路標(biāo)法融合進(jìn)行全覆蓋路徑規(guī)劃

無人機(jī)在進(jìn)行覆蓋作業(yè)時(shí)，直線飛行可以提高覆蓋路徑效率，減少重復(fù)覆蓋，故需要選擇平行的1組路線作為主線，而當(dāng)主線與地塊輪廓發(fā)生碰撞，則被截?cái)?，形成?jié)點(diǎn)；為了將主線連接起來形成完整的覆蓋路徑，則需要一些輔助路線將路徑連接起來，稱為輔線。

首先，在含有障礙物的地塊中，可以用1個(gè)像素矩陣M代表需要覆蓋的區(qū)域，而通過前期對于圖像的處理以及存在障礙物的假設(shè)，可以對覆蓋區(qū)域每個(gè)Mij進(jìn)行一定的定義：

i=1,2,…,p1;j=1,2,…,p2

(8)

此時(shí)處理好的目標(biāo)地塊為含有p1個(gè)橫向像素、p2個(gè)縱向像素的像素矩陣。

其次，覆蓋路徑中主線顯然決定了覆蓋路徑算法的效率，在不同的地塊中，對于含有障礙物的地塊，為了保證整體路徑相對最短，需要確定出最短的覆蓋路徑算法，故需要對主線進(jìn)行旋轉(zhuǎn)，尋找最短的主線長度。為了根據(jù)給定地塊選擇合理的主線方向，定義主線及其方向公式如下：

(9)

式中:α表示主線與水平線所成的角度;q1=1,2,…,p2，q2=1,2,…,p1，Lz1、Lz2分別是像素點(diǎn)的橫縱坐標(biāo)值。通過調(diào)整主線角度α，可以得到對應(yīng)的覆蓋路徑主線最優(yōu)值。

對于覆蓋路徑，需要有一定的約束條件，保證路徑與障礙物不重合，而此時(shí)軌跡的長短與軌跡所在的矩陣點(diǎn)可以表示為

(10)

式中:G為主線集;SL為主線軌跡長度，Pij為落在主線上的可行像素點(diǎn)。由式(10)，可得到最優(yōu)主線角度及此時(shí)主線的總長度。

之后需要通過隨機(jī)路標(biāo)法確定輔線，首先構(gòu)建一個(gè)含有主線節(jié)點(diǎn)的節(jié)點(diǎn)概率圖，定義節(jié)點(diǎn)集V公式：

V={i,j|i=1,2,…,nLz;j=1,2,…,nLr}

(11)

式中：nLz表示主線數(shù)量;nLr表示輔線數(shù)量，并且對于避障邊界B定義如下：

B(i,j,k,p,r,l)=

(12)

在節(jié)點(diǎn)集V中，要求節(jié)點(diǎn)和節(jié)點(diǎn)相互連接，所有的主線都通過輔線連接起來。為了縮短整體路徑長度，定義節(jié)點(diǎn)距離函數(shù)：

(13)

式中：距離D代表的是節(jié)點(diǎn)i與節(jié)點(diǎn)j的歐幾里德距離。通過以上方法，可得到無人機(jī)完整的覆蓋路徑。

在凸劃分的基礎(chǔ)上，將覆蓋路徑分為主線和輔線。首先通過不斷旋轉(zhuǎn)主線角度確定主線的最短長度，再構(gòu)建節(jié)點(diǎn)概率圖，對覆蓋路徑碰撞邊界進(jìn)行約束；再比較節(jié)點(diǎn)間距離，最終查詢出相對最短距離，從而得到輔線，結(jié)合主線構(gòu)建出完整的無人機(jī)覆蓋路徑，將凸劃分子地塊的覆蓋路徑長度相疊加，并給出最短路徑長度的凸劃分策略。

5 算法驗(yàn)證

首先隨機(jī)選擇目標(biāo)地塊，由于復(fù)雜地塊無法進(jìn)行凸劃分優(yōu)化，故對壓縮近似前地塊不進(jìn)行仿真實(shí)驗(yàn)。為了驗(yàn)證本文提出的算法的適用性，需要選擇合適的地塊進(jìn)行算法驗(yàn)證。由4種凸劃分復(fù)雜度可以得到，隨著i、j、m和n越大，地塊凸劃分復(fù)雜度越大，故本文隨機(jī)生成含有數(shù)量較多的外多邊形頂點(diǎn)的復(fù)雜地塊與含有數(shù)量較多的內(nèi)凹多邊形的復(fù)雜障礙物，用于驗(yàn)證本文方法的適用性。分別選定1個(gè)隨機(jī)生成的含有復(fù)雜障礙物的復(fù)雜邊界圓整地塊，1個(gè)隨機(jī)生成的含有復(fù)雜障礙物的復(fù)雜長條狀地塊，以及1個(gè)從文獻(xiàn)[15]中通過變換得到的對比地圖。運(yùn)行實(shí)驗(yàn)采用處理器為Intel(R)Core(TM)i7-6500U CPU，內(nèi)存為RAM 12.0 GB，使用編程軟件及版本為MATLAB 2021a。

算例1對于含有復(fù)雜障礙物的復(fù)雜邊界地塊，此時(shí)需要通過2架無人機(jī)對該地塊進(jìn)行覆蓋，地塊為隨機(jī)復(fù)雜輪廓地塊經(jīng)過輪廓近似壓縮得到的多邊形地塊，外邊界為十九邊形，障礙物為六邊形，根據(jù)之前計(jì)算的算法復(fù)雜度，該地塊的復(fù)雜度為T(10,9,6,1)，且具備較多的凹頂點(diǎn)與偽凹頂點(diǎn)，有較高的代表性，該區(qū)域的頂點(diǎn)坐標(biāo)為

(14)

為驗(yàn)證凸劃分優(yōu)化的優(yōu)越性和適用性，首先仿真出該算例地塊形狀，并驗(yàn)證各頂點(diǎn)凹凸性，如圖7所示。其次，需要將沒有進(jìn)行凸劃分優(yōu)化的結(jié)果進(jìn)行仿真，首先進(jìn)行凹凸點(diǎn)判斷，如圖8所示。接下來作為對比驗(yàn)證，記錄此時(shí)覆蓋路徑長度以及算法規(guī)劃時(shí)間。此時(shí)覆蓋寬度為40 m，運(yùn)行結(jié)果如圖9與表1所示。最后，分別運(yùn)用4種凸劃分優(yōu)化并結(jié)合隨機(jī)路標(biāo)法，記錄下劃分最優(yōu)時(shí)的路徑長度與算法規(guī)劃時(shí)間，覆蓋寬度統(tǒng)一為40 m，運(yùn)行結(jié)果如圖10與表1所示。

表1中策略分別為單純使用隨機(jī)路標(biāo)法(PRM),隨機(jī)路標(biāo)法結(jié)合策略1(PRM*CD.1)、策略2(PRM*CD.2)、策略3(PRM*CD.3)、策略4(PRM*CD.4)以及凸劃分策略中路徑長度最短的策略(PRM*CD)所對應(yīng)的結(jié)果，并將各策略的路徑長度與算法規(guī)劃時(shí)間繪制成如圖11所示。

圖7 算例1目標(biāo)地塊

圖8 多邊形凹凸頂點(diǎn)檢驗(yàn)

圖9 算例1不采用凸劃分優(yōu)化的結(jié)果

表1 算例1采用4種凸劃分策略的優(yōu)化程度(算法規(guī)劃時(shí)間不包含實(shí)時(shí)優(yōu)化時(shí)間)

圖10 算例1采用凸劃分優(yōu)化的效果

圖11 算例1采用凸劃分策略覆蓋路徑長度與算法優(yōu)化時(shí)間對比

通過仿真結(jié)果可以看出，凸劃分優(yōu)化策略3得到了較好的優(yōu)化效果，大大減少了路徑長度以及算法規(guī)劃時(shí)間，在覆蓋率相同的情況下，整體覆蓋路徑長度同比縮短32.40%，證明了該方法的優(yōu)越性，且該地塊的復(fù)雜程度較大，也可證明本文提出的算法的有效性。

算例2由于算例1中地塊采用的是較為圓整的地塊，在現(xiàn)實(shí)環(huán)境中存在長條形地塊，故隨機(jī)給出長條形復(fù)雜地塊輪廓，經(jīng)過近似壓縮可以得到，外輪廓為八邊形，內(nèi)輪廓為五邊形的復(fù)雜多邊形地塊，并且通過凸劃分策略實(shí)現(xiàn)2架無人機(jī)覆蓋路徑規(guī)劃，該地塊的凸劃分復(fù)雜度為T(6,2,4,1)，有較高的代表性和復(fù)雜度，能夠代表長條形復(fù)雜地塊，該區(qū)域近似后頂點(diǎn)坐標(biāo)為為驗(yàn)證算法的有效性，將近似壓縮后的多邊形地塊，仿真出該算例地塊形狀，并驗(yàn)證各頂點(diǎn)凹凸性，如圖12所示。

(15)

將沒有進(jìn)行凸劃分優(yōu)化的情況進(jìn)行仿真，作為對比驗(yàn)證，記錄此時(shí)覆蓋路徑長度以及算法規(guī)劃時(shí)間。此時(shí)覆蓋寬度為20 m，運(yùn)行結(jié)果如圖13與表2所示。

分別運(yùn)用4種凸劃分優(yōu)化并結(jié)合隨機(jī)路標(biāo)法，記錄下劃分最優(yōu)時(shí)的路徑長度與算法規(guī)劃時(shí)間。覆蓋寬度統(tǒng)一為20 m，運(yùn)行結(jié)果如圖14與表2所示。表中策略分別為單純使用隨機(jī)路標(biāo)法(PRM)、隨機(jī)路標(biāo)法結(jié)合策略1(PRM*CD.1)、策略2(PRM*CD.2)、策略3(PRM*CD.3)、策略4(PRM*CD.4)以及凸劃分策略中路徑長度最短的策略(PRM*CD)所對應(yīng)的結(jié)果，并將各策略的路徑長度與算法規(guī)劃時(shí)間繪制成如圖15所示。

圖12 算例2目標(biāo)地塊

圖13 算例2不采用凸劃分優(yōu)化的結(jié)果

表2 算例2采用4種凸劃分策略的優(yōu)化程度(算法規(guī)劃時(shí)間不包含實(shí)時(shí)優(yōu)化時(shí)間)

圖14 算例2采用凸劃分優(yōu)化的效果

通過以上的仿真結(jié)果可以看出，凸劃分優(yōu)化策略4得到了較好的優(yōu)化效果，大大減少了路徑長度以及算法規(guī)劃時(shí)間，在覆蓋率相同的情況下，整體覆蓋路徑長度同比縮短45.04%，證明了該方法的優(yōu)越性，且該地塊屬于長條形地塊，地塊劃分復(fù)雜性較高，可以較好地證明本文方法的有效性。

算例3由于目前凸劃分用于含有障礙物的地塊的研究較少，為與現(xiàn)有已知方法進(jìn)行比較，根據(jù)文獻(xiàn)[16]中所對比方法的地塊，此時(shí)需要通過2架無人機(jī)對該地塊進(jìn)行覆蓋，外邊界為十邊形，障礙物為七邊形，該地塊的復(fù)雜度為T(8,1,5,2)，且有較多文獻(xiàn)使用該地塊進(jìn)行算法分析，有較好的普適性，該區(qū)域的頂點(diǎn)坐標(biāo)為為驗(yàn)證算法的優(yōu)越性，與算例1相似，首先仿真出該算例地塊形狀，并驗(yàn)證各頂點(diǎn)凹凸性，如圖16所示。其次，為比較文中凸劃分算法的優(yōu)越性，將近年的凸劃分優(yōu)化算法與本文中的凸劃分優(yōu)化算法進(jìn)行比較，并記錄覆蓋路徑長度與算法規(guī)劃時(shí)間，具體仿真結(jié)果如圖17與表3所示。表中策略分別為單純使用細(xì)胞分解法(Boustrophedon Cellular Decomposition Coverage, BCDC)、隨機(jī)路標(biāo)法(PRM)、隨機(jī)路標(biāo)法結(jié)合文獻(xiàn)[16]的延伸法(PRM*IEE(Interior Extension of Edges))、隨機(jī)路標(biāo)法結(jié)合凸劃分策略中路徑長度最短的策略(PRM*CD)所對應(yīng)的結(jié)果，并將各策略的路徑長度與算法規(guī)劃時(shí)間繪制成如圖18所示。

圖15 算例2采用凸劃分策略覆蓋路徑長度與算法優(yōu)化時(shí)間對比

(16)

圖16 算例3目標(biāo)地塊

圖17 算例3采用不同凸劃分方法的效果

表3 算例3中不同凸劃分方法覆蓋路徑優(yōu)化程度對比(算法規(guī)劃時(shí)間不包含實(shí)時(shí)優(yōu)化時(shí)間)

圖18 算例3采用不同凸劃分方法覆蓋路徑長度與算法優(yōu)化時(shí)間對比

由仿真結(jié)果可以分析出在該地塊中，凸劃分策略3與隨機(jī)路標(biāo)法融合后可以得到最優(yōu)的路徑長度，且通過本文方法的優(yōu)化后，減少了2個(gè)偽凹頂點(diǎn)。通過圖18的對比可以得出，對于相同的地塊，本文的凸劃分優(yōu)化算法在劃分次數(shù)較少的情況下，依然減少了3.17%的覆蓋路徑長度，能夠較好地適應(yīng)復(fù)雜地塊的覆蓋路徑規(guī)劃問題，可以證明本文算法的優(yōu)越性和有效性。

7 結(jié)論與展望

針對凸劃分優(yōu)化以及全覆蓋路徑規(guī)劃問題進(jìn)行了研究，得出如下結(jié)論：

1) 針對復(fù)雜地塊輪廓以及復(fù)雜障礙物輪廓進(jìn)行不同的處理，將復(fù)雜地塊輪廓進(jìn)行壓縮近似，將復(fù)雜障礙物輪廓進(jìn)行凸包處理，并進(jìn)行凹凸點(diǎn)檢測，可得到易進(jìn)行凸劃分優(yōu)化的地塊輪廓；

2) 提出了4種策略融合隨機(jī)路標(biāo)法解決復(fù)雜地塊含復(fù)雜障礙物的覆蓋路徑規(guī)劃問題，通過對比其他凸劃分算法，可以得到本文的算法對覆蓋路徑規(guī)劃有較好的優(yōu)化效果,減少了覆蓋路徑長度與算法規(guī)劃時(shí)間，并可以適應(yīng)更復(fù)雜的地塊，對隨機(jī)圓整復(fù)雜地塊優(yōu)化路徑同比縮短 32.40%，對隨機(jī)長條形復(fù)雜地塊優(yōu)化路徑同比縮短45.04%，有較好的推廣性，在與其他方法相同地塊的對比中也能達(dá)到相對最優(yōu)，可以推廣至各種地面機(jī)器人、地面無人系統(tǒng)。

未來的研究工作將聚焦于所提出的覆蓋路徑規(guī)劃算法運(yùn)用到遙感無人機(jī)的路徑規(guī)劃問題中，提高遙感作業(yè)效率，并進(jìn)一步探究考慮最小轉(zhuǎn)彎半徑的無人機(jī)覆蓋路徑規(guī)劃方法，有針對性地研究4種凸劃分優(yōu)化策略，使其適合優(yōu)化多種凹頂點(diǎn)分布位置的復(fù)雜地塊覆蓋路徑規(guī)劃問題。