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

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

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

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

中圖分類號：???? TJ760; V279? 文獻標識碼：??? A? 文章編號：???? 1673-5048（2021）06-0046-07

0 引? 言

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

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

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

1 問題描述

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

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

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

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

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

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

P×Q=x1·y2-x2·y1

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

（1） 若P×Q>0， 則Q在P的逆時針方向。

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

（3） 若P×Q<0， 則Q在P的順時針方向。

因此， 設(shè)Vi-1（xi-1， yi-1）， Vi（xi， yi）， Vi+1（xi+1， yi+1）為多邊形區(qū)域的三個相鄰頂點， 構(gòu)成的兩個向量為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時， 頂點Vi為凸點; 當(dāng)F<0時， 兩向量的公共頂點Vi為凹點所在位置。

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

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

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

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

2.2 無人機區(qū)域覆蓋算法

2.2.1 子區(qū)域的遍歷

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

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

2.2.2 覆蓋算法分析

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

以對掃描線終點更新為例， 如圖8（a）所示， 待探測區(qū)域為多邊形ABCDE， 區(qū)域最小寬度所對應(yīng)的邊為CD， 最小寬度所對應(yīng)的頂點為A， 無人機從靠近邊CD的一側(cè)開始遍歷， 虛線PQ為無人機沿掃描線的一條直線飛行航跡， 起點和終點為P和Q， 航跡待探測區(qū)域為多邊形FGCD。 若無人機到達區(qū)域邊界就進行轉(zhuǎn)彎， 則無人機的實際探測區(qū)域為FHID， 產(chǎn)生了遺漏區(qū)域QCI， 不能完全覆蓋待探測區(qū)域， 因此無人機需要多行進一段距離至點N， 才能完成對區(qū)域的無遺漏覆蓋。

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

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

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

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

3 仿真示例

給定一個頂點數(shù)為15的多邊形P， 按順時針排序坐標為

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）}

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

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

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

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

4 結(jié)? 論

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

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

參考文獻：

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

[2] 段海濱，? 申燕凱，? 趙彥杰，? 等. 2019年無人機熱點回眸[J]. 科技導(dǎ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] 段海濱，? 張岱峰，? 范彥銘，? 等. 從狼群智能到無人機集群協(xié)同決策[J]. 中國科學(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ū)域的無人機覆蓋航跡規(guī)劃算法[J]. 航空學(xué)報，? 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ū)域覆蓋無人機航跡規(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] 何立恒，? 鮑其勝，? 王志杰. 鄰近凹點角平分線的多邊形頂點快速凸分算法研究及應(yīng)用[J]. 南京林業(yè)大學(xué)學(xué)報： 自然科學(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