一種凹多邊形區(qū)域的無(wú)人機(jī)覆蓋路徑規(guī)劃算法

王紅星 馬學(xué)嬌 張長(zhǎng)森

摘 要：區(qū)域覆蓋路徑規(guī)劃技術(shù)對(duì)于提高無(wú)人機(jī)搜索的效率和正確率具有重要的意義。 本文針對(duì)凹多邊形區(qū)域， 提出一種區(qū)域覆蓋算法， 旨在使無(wú)人機(jī)能夠更加高效地完成對(duì)指定區(qū)域的無(wú)遺漏覆蓋搜索。 首先， 給出了處理凹多邊形區(qū)域的凹點(diǎn)、 利用凸分解進(jìn)行區(qū)域劃分的的算法流程; 其次， 給出了無(wú)人機(jī)基于最小多余路徑的子區(qū)域遍歷順序， 詳細(xì)描述了無(wú)人機(jī)對(duì)區(qū)域的無(wú)遺漏覆蓋遍歷; 最后， 根據(jù)仿真實(shí)驗(yàn)分析， 證明了該算法的正確性與有效性。

關(guān)鍵詞：???? 無(wú)人機(jī); 區(qū)域覆蓋; 路徑規(guī)劃; 凹多邊形; 凸分解

中圖分類(lèi)號(hào)：???? TJ760; V279? 文獻(xiàn)標(biāo)識(shí)碼：??? A? 文章編號(hào)：???? 1673-5048（2021）06-0046-07

0 引? 言

無(wú)人機(jī)（Unmanned Aerial Vehicle， ?UAV）與有人機(jī)相比， 具有無(wú)需考慮機(jī)載生命的突出特點(diǎn)， 且制造、 維護(hù)成本相對(duì)較低， 利用率高， 明顯契合了時(shí)代的需求， 成為有人機(jī)的完美補(bǔ)充， 可以替代有人機(jī)執(zhí)行枯燥、 惡劣、 危險(xiǎn)、 隱蔽的任務(wù)[1]。

隨著無(wú)人機(jī)自主能力和智能化水平不斷提高，? 無(wú)人機(jī)不僅在任務(wù)偵察、 目標(biāo)打擊等軍事領(lǐng)域被廣泛應(yīng)用，? 在農(nóng)業(yè)植保、 遙感測(cè)繪、 森林消防及影視航拍等民用領(lǐng)域也被大量應(yīng)用[2-4]。 如何對(duì)區(qū)域進(jìn)行高效的無(wú)遺漏覆蓋一直是無(wú)人機(jī)技術(shù)研究的重點(diǎn)。 文獻(xiàn)[5]證明了無(wú)人機(jī)在轉(zhuǎn)彎過(guò)程中比直線飛行耗能高， 并提出了一種基于最小轉(zhuǎn)彎次數(shù)的無(wú)人機(jī)區(qū)域覆蓋算法; 文獻(xiàn)[6]提出了基于最短時(shí)間的無(wú)人機(jī)覆蓋路徑規(guī)劃; 文獻(xiàn)[7]將凹多邊形區(qū)域凸分解為若干個(gè)子區(qū)域后， 采用之字形覆蓋策略實(shí)現(xiàn)了對(duì)多邊形區(qū)域的無(wú)遺漏覆蓋， 但凸分解時(shí)沒(méi)有考慮到區(qū)域形態(tài)， 容易產(chǎn)生狹長(zhǎng)等飛行覆蓋難度較大的區(qū)域; 文獻(xiàn)[8]采用直接將凹點(diǎn)刪除的方法將凹多邊形區(qū)域轉(zhuǎn)化成凸多邊形區(qū)域， 但容易產(chǎn)生大量的多余覆蓋區(qū)域， 加大了無(wú)人機(jī)的覆蓋任務(wù)量; 文獻(xiàn)[9]直接對(duì)凹多邊形區(qū)域進(jìn)行遍歷， 雖然簡(jiǎn)單便捷， 但凹多邊形區(qū)域往往存在狹長(zhǎng)區(qū)域， 直接進(jìn)行遍歷容易產(chǎn)生大量轉(zhuǎn)彎路徑以及多余路徑; 文獻(xiàn)[10]提出了一種鄰近凹點(diǎn)角平分線的凸分解算法， 該算法不增加新節(jié)點(diǎn)， 且分解得到的凸多邊形的形態(tài)、 大小質(zhì)量較好。

本文在以上文獻(xiàn)研究的基礎(chǔ)上， 提出了一種針對(duì)凹多邊形區(qū)域的無(wú)人機(jī)覆蓋路徑規(guī)劃算法， 通過(guò)對(duì)凹點(diǎn)選擇性地刪除來(lái)消除凹多邊形的狹長(zhǎng)區(qū)域， 在文獻(xiàn)[10]的基礎(chǔ)上進(jìn)行改進(jìn)， 對(duì)剩余凹多邊形進(jìn)行凸分解， 然后基于多余路徑最短原則確定子區(qū)域遍歷順序， 通過(guò)尋找最小寬度所對(duì)應(yīng)的邊來(lái)確定無(wú)人機(jī)的飛行方向， 利用Dubins算法進(jìn)行無(wú)人機(jī)轉(zhuǎn)彎的規(guī)劃， 實(shí)現(xiàn)區(qū)域的無(wú)遺漏覆蓋遍歷。

1 問(wèn)題描述

無(wú)人機(jī)區(qū)域覆蓋問(wèn)題描述如下： 給定一架無(wú)人機(jī)U和待覆蓋有界區(qū)域P， 設(shè)置無(wú)人機(jī)的起點(diǎn)和飛行方向， 當(dāng)無(wú)人機(jī)完成一次飛行時(shí)可實(shí)現(xiàn)對(duì)區(qū)域P的無(wú)遺漏覆蓋， 并在不產(chǎn)生遺漏區(qū)域的前提下使覆蓋路徑盡可能少、 覆蓋時(shí)間盡可能短。 實(shí)際上， 待覆蓋區(qū)域多為不規(guī)則的凹多邊形區(qū)域。

為方便研究， 做如下假設(shè)： （1）無(wú)人機(jī)視為一個(gè)質(zhì)點(diǎn); （2）無(wú)人機(jī)在飛行過(guò)程中飛行高度不變; （3）待覆蓋區(qū)域地形相對(duì)平緩， 地勢(shì)起伏的影響可忽略不計(jì); （4）無(wú)人機(jī)的最小轉(zhuǎn)彎半徑和探測(cè)器的探測(cè)半徑相等。 根據(jù)假設(shè)， 簡(jiǎn)化的無(wú)人機(jī)探測(cè)器探測(cè)模型如圖1所示。 無(wú)人機(jī)以速度v飛行， O為無(wú)人機(jī)在地面上的投影， H， α， β分別為無(wú)人機(jī)的飛行高度、 水平視場(chǎng)角和垂直視場(chǎng)角。 矩形區(qū)域ABCD為無(wú)人機(jī)的探測(cè)區(qū)域， 探測(cè)面積為L(zhǎng)×W， 其中L=2H×tanα， W=2H×tanβ。

2 路徑規(guī)劃算法流程

2.1 凹多邊形區(qū)域的處理

文獻(xiàn)[5]證明了無(wú)人機(jī)在轉(zhuǎn)彎過(guò)程中消耗的能量比直線飛行過(guò)程大得多， 給出了凸多邊形跨度和寬度的定義， 并提出了覆蓋凸多邊形區(qū)域時(shí)最短飛行路徑的方法， 即無(wú)人機(jī)沿著垂直于寬度的方向飛行， 可得到最少轉(zhuǎn)彎次數(shù)和最短飛行路徑。 此算法針對(duì)凸多邊形搜索區(qū)域， 若搜索區(qū)域?yàn)椴灰?guī)則的凹多邊形， 需要將凹多邊形區(qū)域處理為凸多邊形區(qū)域， 然后進(jìn)行遍歷。 在對(duì)凹點(diǎn)進(jìn)行處理時(shí)， 首先要找到凹點(diǎn)， 一般采用向量的叉積來(lái)判斷頂點(diǎn)是否為凹點(diǎn)。 設(shè)存在兩個(gè)向量P（x1， y1）和Q（x2， y2）， 則兩向量的叉積可表示為

王紅星， 等： 一種凹多邊形區(qū)域的無(wú)人機(jī)覆蓋路徑規(guī)劃算法

P×Q=x1·y2-x2·y1

該結(jié)果是一個(gè)標(biāo)量， 且具有以下性質(zhì)：

（1） 若P×Q>0， 則Q在P的逆時(shí)針?lè)较颉?/p>

（2） 若P×Q=0， 則Q和P共線。

（3） 若P×Q<0， 則Q在P的順時(shí)針?lè)较颉?/p>

因此， 設(shè)Vi-1（xi-1， yi-1）， Vi（xi， yi）， Vi+1（xi+1， yi+1）為多邊形區(qū)域的三個(gè)相鄰頂點(diǎn)， 構(gòu)成的兩個(gè)向量為Vi-1Vi和ViVi+1， 則兩向量叉積為

F=Vi-1Vi×ViVi+1=（xi-xi-1）·（yi+1-yi）-（xi+1-xi）·（yi-yi-1）

根據(jù)叉積性質(zhì)判斷， 當(dāng)F>0時(shí)， 頂點(diǎn)Vi為凸點(diǎn); 當(dāng)F<0時(shí)， 兩向量的公共頂點(diǎn)Vi為凹點(diǎn)所在位置。

文獻(xiàn)[8]通過(guò)遍歷凹多邊形頂點(diǎn)， 連接凹點(diǎn)兩邊相鄰的頂點(diǎn)， 可將凹點(diǎn)刪除， 以此將凹多邊形轉(zhuǎn)換為凸多邊形。 如圖2所示， 凹多邊形ABCDEF經(jīng)過(guò)遍歷找到凹點(diǎn)C， 刪除邊BC和邊CD后連接頂點(diǎn)B和D， 以此刪除凹點(diǎn)C， 得到了凸多邊形ABDEF。 這種方式雖然簡(jiǎn)單便捷并且可以在一定程度上減少轉(zhuǎn)彎次數(shù)， 但產(chǎn)生的多余搜索區(qū)域BCD面積過(guò)大， 過(guò)多地增加了無(wú)人機(jī)直線飛行距離， 加重了無(wú)人機(jī)的搜索任務(wù)量， 降低搜索效率。 因此這種處理方法是不合理的， 并不適用于所有的凹多邊形。

為了避免產(chǎn)生過(guò)多的多余搜索區(qū)域以及得到形態(tài)較好的區(qū)域， 本文對(duì)凹點(diǎn)進(jìn)行選擇性地消除， 對(duì)此引入兩個(gè)參考量： Parea， θ 。 其中Parea=Sredu/Sall， Sredu為連接凹點(diǎn)兩邊相鄰頂點(diǎn)后產(chǎn)生的多余三角形區(qū)域面積， Sall為整個(gè)區(qū)域的面積， 設(shè)定合適的面積比例閾值， 當(dāng)Parea不超過(guò)所設(shè)閾值， 即產(chǎn)生的多余覆蓋面積相對(duì)于整個(gè)區(qū)域可以忽略不計(jì)時(shí)， 可以用連接上一頂點(diǎn)與下一頂點(diǎn)的方法來(lái)消除凹點(diǎn)。 多余三角形面積公式Sredu=1/2·a·b·sinθ， 其中a和b為凹點(diǎn)相鄰兩邊長(zhǎng)度， θ為凹點(diǎn)外角角度， 由正弦函數(shù)單調(diào)性可知， 在0°到90°之間θ的值與sinθ的值成正比， 在90°到180°之間， θ的值與sinθ的值成反比。 當(dāng)Parea超過(guò)閾值但sinθ的值較小時(shí)， 說(shuō)明凹點(diǎn)相鄰兩邊邊長(zhǎng)較長(zhǎng)， 此時(shí)θ值較大或較小， 當(dāng)θ值較小時(shí)如圖3（a）所示將產(chǎn)生狹長(zhǎng)的搜索區(qū)域， 增加無(wú)人機(jī)的轉(zhuǎn)彎次數(shù)， 不利于無(wú)人機(jī)的機(jī)動(dòng)轉(zhuǎn)彎， 因此， 將θ也作為一個(gè)參考量， 設(shè)定合適的角度閾值， 當(dāng)θ超過(guò)所設(shè)閾值時(shí)， 用同樣的方法消除凹點(diǎn)。

圖3是凹多邊形處理的一個(gè)實(shí)例， 將凹多邊形的頂點(diǎn)按順時(shí)針輸入， 并設(shè)置好面積覆蓋比例閾值N和角度閾值θmin， 按頂點(diǎn)順序依次進(jìn)行遍歷， 在圖3（a）中遍歷到頂點(diǎn)C為凹頂點(diǎn)， 然后依次計(jì)算三角形BCD的面積與ABCDEF整個(gè)區(qū)域面積的比值， 以及頂點(diǎn)C的外角度數(shù)。 若所得面積比值小于設(shè)定的閾值， 或者頂點(diǎn)C的外角在設(shè)定的角度閾值范圍內(nèi)， 則如圖3（b）所示， 刪除邊BC和CD， 連接BD， 消除凹頂點(diǎn)C并更新頂點(diǎn)集。 該過(guò)程偽代碼如圖4所示，? 其中a和 b為凹點(diǎn)兩邊邊長(zhǎng)， θ為凹點(diǎn)外角角度。 對(duì)凹點(diǎn)有選擇性地消除， 可以減少凹多邊形的狹長(zhǎng)區(qū)域或面積過(guò)小的區(qū)域， 在一定程度上減少無(wú)人機(jī)的轉(zhuǎn)彎次數(shù)， 有利于無(wú)人機(jī)任務(wù)的執(zhí)行。

將符合條件的凹點(diǎn)刪除后， 若剩余頂點(diǎn)中還存在凹點(diǎn)， 則在文獻(xiàn)[10]中鄰近凹點(diǎn)角平分線的凸分算法基礎(chǔ)上進(jìn)行剖分。 圖5是凹點(diǎn)剖分的一個(gè)實(shí)例， 首先遍歷多邊形找到凹點(diǎn)V1， 為了使剖分后得到的多邊形形態(tài)更好， 在凹點(diǎn)兩邊反向延長(zhǎng)線之間的區(qū)域中選擇剖分點(diǎn)， 即選擇區(qū)域A中的點(diǎn)， 為了成功剖分， 判斷區(qū)域中的可視點(diǎn)， 將可視點(diǎn)作為候選剖分點(diǎn)。 可視點(diǎn)的定義為： 多邊形中的頂點(diǎn)與凹點(diǎn)連接形成的線段， 全部在多邊形內(nèi)部或上面， 這樣的頂點(diǎn)就是凹點(diǎn)的可視點(diǎn)。 根據(jù)可視點(diǎn)定義， 頂點(diǎn)V1位于區(qū)域A中的可視點(diǎn)有V4， V5， V6 ， V8 和V9， 即作為V1的候選剖分點(diǎn)， 然后做V1的角平分線， 為了盡可能多地消除凹點(diǎn)， 判斷候選剖分點(diǎn)的凹凸性， 若存在凹點(diǎn)， 則只計(jì)算凹點(diǎn)與角平分線間的垂直距離; 若只存在凸點(diǎn)， 則計(jì)算所有凸點(diǎn)與角平分線間的垂直距離， 選擇距離最短的點(diǎn)作為剖分點(diǎn)。 若候選剖分點(diǎn)為空， 則以凹點(diǎn)角平分線與多邊形的交點(diǎn)為剖分點(diǎn)。 如圖5所示， V1的候選剖分點(diǎn)中存在V5， V8兩個(gè)凹點(diǎn)， 因此， 只需計(jì)算V5， V8與角平分線間的垂直距離， 經(jīng)計(jì)算， 頂點(diǎn)V8距離角平分線距離最短， 因此選擇頂點(diǎn)V8作為凹點(diǎn)V1的剖分點(diǎn)。 剖分后得到多邊形V1V2V3V4V5V6V7V8和V8V9V10V11V1， 判斷兩個(gè)多邊形的凹凸性， 若還存在凹多邊形， 則重復(fù)以上步驟， 若都是凸多邊形， 則停止凸分解， 該過(guò)程偽代碼如圖6所示。

2.2 無(wú)人機(jī)區(qū)域覆蓋算法

2.2.1 子區(qū)域的遍歷

將區(qū)域完成凸分解后將形成若干個(gè)子區(qū)域， 接下來(lái)的任務(wù)是對(duì)子區(qū)域進(jìn)行覆蓋搜索， 根據(jù)文獻(xiàn)[5]中的寬度求解算法， 可求出各個(gè)子區(qū)域的寬度及對(duì)應(yīng)的飛行方向。 如圖7所示， 設(shè)無(wú)人機(jī)的探測(cè)半徑為R， 凸多邊形ABCD最小寬度所對(duì)應(yīng)的邊為CD， 最小寬度所對(duì)應(yīng)的頂點(diǎn)為A， 做兩條平行于CD的直線， 其中一條與邊CD的距離為R， 另一條與頂點(diǎn)A的距離為R， 分別交多邊形于p1， p2， p3， p4， 這四個(gè)點(diǎn)皆可作為區(qū)域的駛?cè)朦c(diǎn)， 是區(qū)域的候選駛?cè)朦c(diǎn)。 當(dāng)駛?cè)朦c(diǎn)確定后， 駛出點(diǎn)也就確定了， 即一個(gè)駛?cè)朦c(diǎn)對(duì)應(yīng)一個(gè)駛出點(diǎn)。 兩個(gè)子區(qū)域由上一子區(qū)域的駛出點(diǎn)和下一子區(qū)域的駛?cè)朦c(diǎn)連接， 兩點(diǎn)（x1， y1）、 （x2， y2）間的路徑距離為歐式距離， 計(jì)算公式為： d=（x2-x1）2+（y2-y1）2。 兩點(diǎn)間的路徑為子區(qū)域間的連接路徑， 連接路徑為多余路徑。 為了節(jié)省無(wú)人機(jī)的能量消耗， 應(yīng)使多余路徑盡可能短， 因此， 當(dāng)選擇子區(qū)域駛?cè)朦c(diǎn)時(shí)， 總是選擇與上一子區(qū)域駛出點(diǎn)路徑距離d最小的候選駛?cè)朦c(diǎn)作為下一子區(qū)域駛?cè)朦c(diǎn)。

確定子區(qū)域遍歷順序時(shí)， 需要找到一條覆蓋所有子區(qū)域， 并且多余路徑最少的區(qū)域遍歷順序。 這個(gè)問(wèn)題類(lèi)似于旅行商問(wèn)題（Traveling Salesman Problem，? TSP）， TSP是一個(gè)NP-hard問(wèn)題， 國(guó)內(nèi)外學(xué)者對(duì)此進(jìn)行了大量研究。 結(jié)合實(shí)際， 由于現(xiàn)實(shí)中研究的子區(qū)域數(shù)量相對(duì)較少， 可以將問(wèn)題抽象為小規(guī)模的TSP。 本文結(jié)合DFS深度優(yōu)先搜索算法進(jìn)行求解， 規(guī)定兩個(gè)子區(qū)域若有公共點(diǎn)， 則這兩個(gè)子區(qū)域是相鄰關(guān)系， 創(chuàng)建子區(qū)域鄰接表， 用1表示兩個(gè)子區(qū)域相鄰， 0表示不相鄰。 首先確定初始子區(qū)域以及初始駛?cè)朦c(diǎn)， 根據(jù)子區(qū)域鄰接表， 利用DFS深度優(yōu)先搜索算法找到所有從初始子區(qū)域出發(fā)的遍歷順序， 然后根據(jù)遍歷區(qū)域個(gè)數(shù)找到遍歷所有子區(qū)域的遍歷順序， 最后計(jì)算各個(gè)遍歷順序的總的多余路徑（所有子區(qū)域間多余路徑之和）， 選擇總多余路徑最少的遍歷順序進(jìn)行遍歷。 在此注意， 若從規(guī)定的初始子區(qū)域找不到一條可以遍歷全部子區(qū)域的遍歷路線， 則更換初始子區(qū)域。

2.2.2 覆蓋算法分析

根據(jù)文獻(xiàn)[5]中的方法， 可求出凸多邊形區(qū)域的最小寬度以及最小寬度所對(duì)應(yīng)的邊和頂點(diǎn)。 本文采用掃描線方式進(jìn)行覆蓋遍歷， 掃描線與最小寬度所對(duì)應(yīng)的邊平行。 即無(wú)人機(jī)沿著掃描線直線飛行， 當(dāng)飛行至區(qū)域邊界時(shí)轉(zhuǎn)向， 反方向沿下一掃描線直線飛行， 如此反復(fù)， 直至覆蓋完整個(gè)區(qū)域。 為方便描述， 本文將無(wú)人機(jī)的最小轉(zhuǎn)彎半徑和探測(cè)半徑記為R， 待探測(cè)多邊形區(qū)域的最小寬度記為w， 最小寬度所對(duì)應(yīng)的邊記為E， 最小寬度所對(duì)應(yīng)的頂點(diǎn)記為V。 要想將整個(gè)子區(qū)域完全遍歷， 最少需要[w/2R]+1條掃描線覆蓋區(qū)域。 為方便研究， 在此規(guī)定： （1）搜索區(qū)域的最小寬度w遠(yuǎn)遠(yuǎn)大于無(wú)人機(jī)的探測(cè)半徑R; （2）當(dāng)?shù)趎-1條掃描線掃描后的剩余區(qū)域?qū)挾却笥赗并小于2R時(shí)， 第n條掃描線與第n-1條掃描線之間的距離為R， 若剩余區(qū)域?qū)挾却笥?R， 則掃描線間距為2R， 若小于R， 則掃描線覆蓋完畢。 因此， 每一條掃描線與子區(qū)域都有兩個(gè)交點(diǎn)， 兩交點(diǎn)間距離即為掃描線的探測(cè)長(zhǎng)度， 記為L(zhǎng)scan， 則無(wú)人機(jī)的探測(cè)區(qū)域?yàn)長(zhǎng)scan×2R的矩形區(qū)域， 而當(dāng)無(wú)人機(jī)到達(dá)區(qū)域邊界就轉(zhuǎn)彎時(shí)， 探測(cè)到的區(qū)域可能不會(huì)完全覆蓋掃描線的待探測(cè)區(qū)域， 此時(shí)需要無(wú)人機(jī)飛行更多的路程， 然后轉(zhuǎn)彎。 因此要根據(jù)情況更新每條掃描線的起點(diǎn)和終點(diǎn)， 以確保沒(méi)有遺漏區(qū)域。

以對(duì)掃描線終點(diǎn)更新為例， 如圖8（a）所示， 待探測(cè)區(qū)域?yàn)槎噙呅蜛BCDE， 區(qū)域最小寬度所對(duì)應(yīng)的邊為CD， 最小寬度所對(duì)應(yīng)的頂點(diǎn)為A， 無(wú)人機(jī)從靠近邊CD的一側(cè)開(kāi)始遍歷， 虛線PQ為無(wú)人機(jī)沿掃描線的一條直線飛行航跡， 起點(diǎn)和終點(diǎn)為P和Q， 航跡待探測(cè)區(qū)域?yàn)槎噙呅蜦GCD。 若無(wú)人機(jī)到達(dá)區(qū)域邊界就進(jìn)行轉(zhuǎn)彎， 則無(wú)人機(jī)的實(shí)際探測(cè)區(qū)域?yàn)镕HID， 產(chǎn)生了遺漏區(qū)域QCI， 不能完全覆蓋待探測(cè)區(qū)域， 因此無(wú)人機(jī)需要多行進(jìn)一段距離至點(diǎn)N， 才能完成對(duì)區(qū)域的無(wú)遺漏覆蓋。

求點(diǎn)N的方法為： 按輸入頂點(diǎn)順序順時(shí)針對(duì)頂點(diǎn)和邊進(jìn)行編號(hào)1， 2， …， n， 規(guī)定第n條邊包含第n個(gè)頂點(diǎn)， 不包含第n+1個(gè)頂點(diǎn)。 設(shè)置兩個(gè)參數(shù)LE， LV。 因?yàn)闊o(wú)人機(jī)從靠近邊CD的一側(cè)開(kāi)始遍歷， 令LE=R， 需要計(jì)算PQ與頂點(diǎn)A的距離D′V， 若D′V≥R， 令LV=R， 否則， 令LV=D′V。 若無(wú)人機(jī)是從靠近頂點(diǎn)A的一側(cè)開(kāi)始遍歷的， 則令LV=R， 計(jì)算PQ與邊CD的距離DE， 若DE≥R， 令LE=R， 否則， 令LE=DE。 分別在PQ靠近邊CD和頂點(diǎn)A的兩端做平行于PQ且與PQ距離分別為L(zhǎng)E和LV的直線， 如圖8（a）所示， 兩條直線為FG和DC， 與多邊形分別相交于點(diǎn)F， G和點(diǎn)D， C， 過(guò)掃描線終點(diǎn)一側(cè)的交點(diǎn)G和C分別做垂直于PQ的兩條直線， 垂足點(diǎn)為M和N。 根據(jù)各交點(diǎn)的坐標(biāo)與邊的坐標(biāo)范圍， 判斷交點(diǎn)在哪條邊上， 判斷交點(diǎn)G和C是否在多邊形的同一條邊上， 若是， 則說(shuō)明交點(diǎn)G和C之間是直線段， 沒(méi)有出現(xiàn)其他頂點(diǎn)， 若不是， 如圖8（b）所示， 說(shuō)明兩交點(diǎn)之間不是直線段， 而含有其他頂點(diǎn)， 此時(shí)需過(guò)兩交點(diǎn)之間的所有頂點(diǎn)做垂直于PQ的直線， 并記錄垂足點(diǎn)。 最后， 根據(jù)各垂足點(diǎn)坐標(biāo)與線段PQ的關(guān)系判斷垂足點(diǎn)是否在線段PQ上， 若都在， 則不需要更新掃描線終點(diǎn)， 否則， 選取不在線段PQ上且與掃描線終點(diǎn)Q距離最遠(yuǎn)的垂足點(diǎn)作為新的掃描線終點(diǎn)。 圖8（a）中選擇點(diǎn)N代替點(diǎn)Q， 更新后無(wú)人機(jī)的掃描區(qū)域變?yōu)镕JCD， 完全包含了待覆蓋區(qū)域FGCD， 實(shí)現(xiàn)了區(qū)域的無(wú)遺漏覆蓋。 起點(diǎn)的更新方法與終點(diǎn)的更新方法相同。 上述過(guò)程的流程圖如圖9所示。

無(wú)人機(jī)到達(dá)掃描線終點(diǎn)時(shí)， 需要進(jìn)行轉(zhuǎn)彎進(jìn)入下一條掃描線。 無(wú)人機(jī)具有最小轉(zhuǎn)彎半徑的限制， 如圖10所示， 若無(wú)人機(jī)的最小轉(zhuǎn)彎半徑R小于等于二分之一的兩條航跡之間距離d時(shí)， 在完成轉(zhuǎn)彎運(yùn)動(dòng)后， 兩條航帶之間沒(méi)有縫隙的緊密銜接， 不會(huì)出現(xiàn)搜索盲區(qū)[2]。 而當(dāng)無(wú)人機(jī)的最小轉(zhuǎn)彎半徑大于二分之一航跡間距離時(shí)， 如圖11所示， 由于不能緊密銜接會(huì)產(chǎn)生掃描盲區(qū)。 因此本文采用Dubins曲線算法進(jìn)行無(wú)人機(jī)轉(zhuǎn)彎處的航跡規(guī)劃。

Dubins曲線是在確定起始點(diǎn)切線方向和滿(mǎn)足曲率約束的條件下， 連接兩個(gè)二維平面的最短路徑， Dubins曲線證明了兩點(diǎn)之間的路徑必然存在， 任何路徑都可以由兩段圓弧航線和一條直線組成[11]。 如圖12所示， 由A點(diǎn)到B點(diǎn)的Dubins曲線一共有LSL， RSR， RSL， LSR， RLR

和LRL六種類(lèi)型， 其中L表示逆時(shí)針圓弧運(yùn)動(dòng)， R表示順時(shí)針圓弧運(yùn)動(dòng)， S表示直線運(yùn)動(dòng)， 箭頭方向代表物體的運(yùn)動(dòng)方向。 因此， 當(dāng)確定了無(wú)人機(jī)轉(zhuǎn)彎的起始點(diǎn)運(yùn)動(dòng)方向以及最小轉(zhuǎn)彎半徑時(shí)， 可利用Dubins曲線來(lái)規(guī)劃無(wú)人機(jī)轉(zhuǎn)彎路徑。

3 仿真示例

給定一個(gè)頂點(diǎn)數(shù)為15的多邊形P， 按順時(shí)針排序坐標(biāo)為

V=（v1， v2， v3…， v15）{（2 050， 6 450）， （4 430， 8 670）， （2 050， 12 650）， （6 450， 11 440）， （7 150， 10 150）， （10 420， 10 940）， （9 550， 8 550）， （11 050， 11 150）， （11 120， 8 580）， （15 450， 7 510）， （11 530， 5 140）， （8 230， 2 480）， （8 950， 8 000）， （7 750， 2 350）， （7 070， 6 490）}

無(wú)人機(jī)的探測(cè)半徑及最小轉(zhuǎn)彎半徑為0.18×103 m， 待覆蓋區(qū)域如圖13所示。 設(shè)置面積覆蓋比例閾值為0.025， 當(dāng)消除凹點(diǎn)后產(chǎn)生的多余覆蓋區(qū)域與整個(gè)區(qū)域的面積比值小于等于0.025時(shí)， 可將凹點(diǎn)刪除， 角度閾值為10°， 即當(dāng)區(qū)域角度小于10°， 產(chǎn)生過(guò)于狹長(zhǎng)的區(qū)域時(shí)， 將凹點(diǎn)進(jìn)行刪除。 將凹點(diǎn)刪除后的區(qū)域如圖14所示。

判斷消除凹點(diǎn)后的多邊形區(qū)域是否還存在凹點(diǎn)， 若不存在則直接遍歷， 若還存在凹點(diǎn)則對(duì)區(qū)域進(jìn)行凸分解， 分解后的區(qū)域如圖15所示。 設(shè)置區(qū)域1為初始區(qū)域， 無(wú)人機(jī)起始點(diǎn)如圖16中所示， 從區(qū)域1出發(fā)共有四條可以完全遍歷區(qū)域的路徑， 根據(jù)各子區(qū)域起始點(diǎn)確定各子區(qū)域間的多余路徑， 四條路徑及其產(chǎn)生的多余路徑長(zhǎng)度如表1所示， 因此選擇路徑1作為子區(qū)域遍歷順序。 根據(jù)各子區(qū)域起始點(diǎn)， 用掃描線覆蓋各個(gè)子區(qū)域， 掃描線即為無(wú)人機(jī)的覆蓋直線航跡。 為了避免出現(xiàn)掃描盲區(qū)， 根據(jù)區(qū)域形態(tài)更新掃描線起始點(diǎn)， 更新后的掃描線如圖16所示， 最后無(wú)人機(jī)通過(guò)Dubins曲線進(jìn)行轉(zhuǎn)彎覆蓋， 無(wú)人機(jī)的覆蓋路徑如圖17所示。

表2為三種不同覆蓋方式下無(wú)人機(jī)在區(qū)域P內(nèi)航跡的總路程和總轉(zhuǎn)彎次數(shù)的比較， 其中， 分割預(yù)處理覆蓋

算法是將凹多邊形凸分解為若干個(gè)子區(qū)域， 然后對(duì)各個(gè)子區(qū)域進(jìn)行覆蓋， 凸多邊形覆蓋算法是通過(guò)消除凹點(diǎn)的方法， 先將凹多邊形轉(zhuǎn)換成最小凸多邊形， 然后再對(duì)區(qū)域進(jìn)行覆蓋。 由表2可見(jiàn)， 本文提出的算法通過(guò)消除待覆蓋區(qū)域中的狹長(zhǎng)區(qū)域， 可大大減少轉(zhuǎn)彎次數(shù)， 相比于直接進(jìn)行凸分解， 極大減少了轉(zhuǎn)彎次數(shù)， 降低了無(wú)人機(jī)轉(zhuǎn)彎過(guò)程中能量的損耗， 而相較于凸多邊形覆蓋算法， 則極大降低了多余覆蓋區(qū)域， 減少了覆蓋總路徑， 提高了無(wú)人機(jī)的效率。

4 結(jié)? 論

本文針對(duì)現(xiàn)有無(wú)人機(jī)區(qū)域覆蓋算法的不足， 提出了一種改進(jìn)的凹多邊形區(qū)域覆蓋算法， 通過(guò)消除凹多邊形狹長(zhǎng)及不易進(jìn)行機(jī)動(dòng)轉(zhuǎn)彎的區(qū)域， 減少了無(wú)人機(jī)的轉(zhuǎn)彎次數(shù)， 同時(shí)也避免了過(guò)多多余覆蓋區(qū)域的產(chǎn)生， 并且對(duì)凸分解后的區(qū)域找到了產(chǎn)生多余路徑最少的區(qū)域遍歷順序， 通過(guò)對(duì)掃描線起始點(diǎn)的更新， 可避免掃描盲區(qū)的產(chǎn)生， 實(shí)現(xiàn)對(duì)區(qū)域的無(wú)遺漏覆蓋。 本文算法有效幫助無(wú)人機(jī)降低能量損耗， 提高搜索效率和正確率。

在實(shí)際應(yīng)用中， 無(wú)人機(jī)的搜索區(qū)域往往是不規(guī)則的曲變形區(qū)域， 此時(shí)可以將不規(guī)則的區(qū)域逼近為多邊形區(qū)域， 然后再用本文算法對(duì)其進(jìn)行覆蓋， 同時(shí)可以根據(jù)各區(qū)域目標(biāo)出現(xiàn)的概率和以往搜索的成功率等為參考， 進(jìn)一步優(yōu)化無(wú)人機(jī)的遍歷路徑。

參考文獻(xiàn)：

[1] Austin R. Unmanned Aircraft Systems[M]. Chichester： John Wiley & Sons，? Ltd，? 2010.

[2] 段海濱，? 申燕凱，? 趙彥杰，? 等. 2019年無(wú)人機(jī)熱點(diǎn)回眸[J]. 科技導(dǎo)報(bào)，? 2020，? 38（1）： 170-187.

Duan Haibin，? Shen Yankai，? Zhao Yanjie，? et al. Review of Technological Hotspots of Unmanned Aerial Vehicle in 2019[J]. Science & Technology Review，? 2020，? 38（1）： 170-187.（in Chinese）

[3] 段海濱，? 張岱峰，? 范彥銘，? 等. 從狼群智能到無(wú)人機(jī)集群協(xié)同決策[J]. 中國(guó)科學(xué)： 信息科學(xué)，? 2019，? 49（1）： 112-118.

Duan Haibin，? Zhang Daifeng，? Fan Yanming，? et al. From Wolf Pack Intelligence to UAV Swarm Cooperative Decision-Making[J]. Scientia Sinica ： Informationis，? 2019，? 49（1）： 112-118.（in Chinese）

[4] Duan H B，? Yang Q，? Deng Y M，? et al. Unmanned Aerial Systems Coordinate Target Allocation Based on Wolf Behaviors[J]. Science China Information Sciences，? 2018，? 62（1）： 1-3.

[5] 陳海，? 王新民，? 焦裕松，? 等. 一種凸多邊形區(qū)域的無(wú)人機(jī)覆蓋航跡規(guī)劃算法[J]. 航空學(xué)報(bào)，? 2010，? 31（9）： 1802-1808.

Chen Hai，? Wang Xinmin，? Jiao Yusong，? et al. An Algorithm of Coverage Flight Path Planning for UAVs in Convex Polygon Areas[J]. Acta Aeronautica et Astronautica Sinica，? 2010，? 31（9）： 1802-1808.（in Chinese）

[6] Avellar G S，? Pereira G A，? Pimenta L C，? et al. Multi-UAV Routing for Area Coverage and Remote Sensing with Minimum Time[J]. Sensors，? 2015，? 15（11）： 27783-27803.

[7] Li Y，? Chen H，?? Er M J，? et al. Coverage Path Planning for UAVs Based on Enhanced Exact Cellular Decomposition Method[J]. Mechatronics，? 2011，? 21（5）： 876-885.

[8] Vinh K，? Gebreyohannes S，? Karimoddini A. An Area-Decomposition Based Approach for Cooperative Tasking and Coordination of UAVs in a Search and Coverage Mission[C]∥ IEEE Aerospace Conference，? 2019.

[9] 王自亮，? 羅德林，? 吳順祥. 凹多邊形區(qū)域覆蓋無(wú)人機(jī)航跡規(guī)劃方法[J]. 航空兵器，? 2019，? 26（1）： 95-100.

Wang Ziliang，? Luo Delin，? Wu Shunxiang. A UAV Path Planning Method for Concave Polygonal Area Coverage[J]. Aero Weaponry，? 2019，? 26（1）： 95-100.（in Chinese）

[10] 何立恒，? 鮑其勝，? 王志杰. 鄰近凹點(diǎn)角平分線的多邊形頂點(diǎn)快速凸分算法研究及應(yīng)用[J]. 南京林業(yè)大學(xué)學(xué)報(bào)： 自然科學(xué)版，? 2013，? 37（5）： 165-168.

He Liheng，? Bao Qisheng，? Wang Zhijie. Research and Application on Algorithm for Decomposing a Concave Polygon into Convex Poly-gons of Adjacent Angle Bisector of Concave Point and Vertex of Polygon[J]. Journal of Nanjing Forestry University： Natural Sciences Edition，? 2013，? 37（5）： 165-168.（in Chinese）

[11] Dubins L E. On Curves of Minimal Length with a Constraint on Average Curvature，? and with Prescribed Initial and Terminal Positions and Tangents[J]. American Journal of Mathematics，? 1957，? 79（3）： 497.

An Algorithm of Coverage Path Planning for

UAV in Concave Polygon Area

Wang Hongxing， Ma Xuejiao*， Zhang Changsen

（Henan Polytechnic University， Jiaozuo 454002，? China）

Abstract： Coverage path planning technologies is of great significance for improving the efficiency and accuracy of UAV search. This paper proposes a area coverage path planning（CPP） algorithm for the concave polygon area，? which aims to enable UAV to complete the coverage search of the specified area more efficiently. Firstly，? the algorithm flow is given by dealing with concave points in concave polygon area and dividing the area by convex decomposition. Secondly，? the traverse sequence of the subarea is given based on the minimum redundant path，? and the covering traverse without omission of the area by UAV are discribed in detail. Finally，? the correctness and effectiveness of the proposed algorithm are proved by simulation experiments.

Key words： UAV; area coverage; path planning; concave polygon; convex decomposition