基于復雜地塊凸劃分優化的多無人機覆蓋路徑規劃

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

1. 中國農業大學 工學院，北京 100083

2. 武漢大學 測繪遙感信息工程國家重點實驗室，武漢 430079

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

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

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

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

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

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

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

以上文獻都對地塊優化和覆蓋路徑規劃有突出貢獻，但面對更加復雜的覆蓋地塊環境時，會逐漸暴露出以下問題：

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

2) 沒有考慮有障礙物的凹多邊形如何進行覆蓋路徑規劃或者有障礙物的凹多邊形如何進行凸劃分優化。

針對以上問題，對含障礙物的復雜地塊進行凸劃分優化與覆蓋路徑規劃研究。

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

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

圖1 不規則邊界無劃分特征

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

圖2 復雜地塊對覆蓋路徑的影響

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

1.1 復雜地塊的邊界輪廓近似壓縮

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

步驟1原本的復雜邊界，進行鏈碼操作，得到邊界各個像素點的順序。

步驟2邊界線被分割為基于端點的線段，并尋找最遠點。

步驟3找到相距初始線段垂直距離最遠頂點并不斷連接，并重復步驟2。

步驟4當循環后的線段垂直距離平均誤差低于給定誤差，認為多邊形近似建立成功，連接各個頂點。

圖3 改進Douglas-Peucker過程[10]

最終通過選擇合適的誤差區間，得到壓縮后的復雜地塊輪廓圖，并運用到接下來的地塊凸劃分優化中。

1.2 復雜地塊中復雜障礙物輪廓近似壓縮

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

nc=nz·nf+nc0

(1)

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

圖4 復雜障礙物輪廓采用改進卷包裹算法的流程

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

(2)

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

圖5 具體地圖(頤和園)實現改進卷包裹算法得到凸包

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

2 凹凸頂點定義和凹凸頂點檢驗

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

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

3 針對近似壓縮后復雜凹多邊形地塊的凸劃分優化

3.1 含有障礙物的地塊凸劃分優化

含有障礙物將會大大增加覆蓋路徑優化的難度，為了方便覆蓋路徑規劃以及減少路徑轉彎次數，需要采用凸劃分的方式優化地塊，進而達到優化覆蓋路徑的目的。

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

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

對于從偽凹頂點延伸進行劃分，若非復雜障礙物情況下，延伸偽凹頂點邊可以有效將含有障礙物地塊的復雜度降低，此時地塊凸劃分的過程復雜度為

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為計算復雜度系數。

3.2 含有復雜障礙物的復雜地塊凸劃分優化

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

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

3.2.1 從凹頂點的1個邊緣延伸

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

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

O(i3·m3+i·j2)

(4)

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

3.2.2 內頂點與外頂點連接劃分

偽凹頂點與凹頂點是引起覆蓋路徑轉彎次數較多的主要因素，通過凸劃分可以減少2種頂點的數量。首先要對偽凹頂點進行連接，保證外凹頂點優先連接，之后是將內頂點全部與外頂點相連接，此時凸劃分的復雜度為

(5)

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

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

算法2 內外頂點的連接和劃分

3.2.3 平行外輪廓邊并經過凹頂點實現劃分

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

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

O(i3·m3+i2·j2)

(6)

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

算法3 平行外輪廓邊并通過凹頂點劃分

3.2.4 連接外凹頂點與其他外頂點實現劃分

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

(7)

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

算法4 連接凹的頂點和頂點實現分割

4 凸劃分優化與隨機路標法融合進行全覆蓋路徑規劃

無人機在進行覆蓋作業時，直線飛行可以提高覆蓋路徑效率，減少重復覆蓋，故需要選擇平行的1組路線作為主線，而當主線與地塊輪廓發生碰撞，則被截斷，形成節點；為了將主線連接起來形成完整的覆蓋路徑，則需要一些輔助路線將路徑連接起來，稱為輔線。

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

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

(8)

此時處理好的目標地塊為含有p1個橫向像素、p2個縱向像素的像素矩陣。

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

(9)

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

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

(10)

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

之后需要通過隨機路標法確定輔線，首先構建一個含有主線節點的節點概率圖，定義節點集V公式：

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

(11)

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

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

(12)

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

(13)

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

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

5 算法驗證

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

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

(14)

為驗證凸劃分優化的優越性和適用性，首先仿真出該算例地塊形狀，并驗證各頂點凹凸性，如圖7所示。其次，需要將沒有進行凸劃分優化的結果進行仿真，首先進行凹凸點判斷，如圖8所示。接下來作為對比驗證，記錄此時覆蓋路徑長度以及算法規劃時間。此時覆蓋寬度為40 m，運行結果如圖9與表1所示。最后，分別運用4種凸劃分優化并結合隨機路標法，記錄下劃分最優時的路徑長度與算法規劃時間，覆蓋寬度統一為40 m，運行結果如圖10與表1所示。

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

圖7 算例1目標地塊

圖8 多邊形凹凸頂點檢驗

圖9 算例1不采用凸劃分優化的結果

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

圖10 算例1采用凸劃分優化的效果

圖11 算例1采用凸劃分策略覆蓋路徑長度與算法優化時間對比

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

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

(15)

將沒有進行凸劃分優化的情況進行仿真，作為對比驗證，記錄此時覆蓋路徑長度以及算法規劃時間。此時覆蓋寬度為20 m，運行結果如圖13與表2所示。

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

圖12 算例2目標地塊

圖13 算例2不采用凸劃分優化的結果

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

圖14 算例2采用凸劃分優化的效果

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

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

圖15 算例2采用凸劃分策略覆蓋路徑長度與算法優化時間對比

(16)

圖16 算例3目標地塊

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

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

圖18 算例3采用不同凸劃分方法覆蓋路徑長度與算法優化時間對比

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

7 結論與展望

針對凸劃分優化以及全覆蓋路徑規劃問題進行了研究，得出如下結論：

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

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

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