王文旭，李 立，李 儼

（西北工業(yè)大學(xué) 陜西 西安 710072）

無人機(jī)區(qū)域覆蓋航跡規(guī)劃 （Coverage Flight Path Planning，CFPP）定義為：在滿足某種（某些）性能指標(biāo)最優(yōu)的前提下，避開障礙物和威脅源，規(guī)劃出一條能夠遍歷待覆蓋區(qū)域的最優(yōu)飛行路線。在機(jī)器人領(lǐng)域，該技術(shù)稱為區(qū)域覆蓋路徑規(guī)劃（Coverage Path Planning，CPP）技術(shù)。

現(xiàn)今，國內(nèi)外對覆蓋航跡（路徑）規(guī)劃技術(shù)的研究主要集中在機(jī)器人領(lǐng)域，對無人機(jī)領(lǐng)域的研究相對較少。在機(jī)器人領(lǐng)域，覆蓋路徑規(guī)劃技術(shù)的應(yīng)用領(lǐng)域主要包括：室內(nèi)清潔、擦窗、割草、自動(dòng)噴漆、耕犁、播撒、檢測探傷、排雷等。在無人機(jī)領(lǐng)域，覆蓋航跡規(guī)劃技術(shù)的應(yīng)用領(lǐng)域主要包括：安全監(jiān)控、戰(zhàn)場偵察、目標(biāo)搜索、地形測繪、礦藏勘測等[1]。

隨著無人機(jī)在民用及軍用領(lǐng)域應(yīng)用范圍的不斷擴(kuò)大，無人機(jī)對覆蓋航跡規(guī)劃技術(shù)的需求也更加的強(qiáng)烈。由于機(jī)器人和無人機(jī)所處的環(huán)境及特性都有所區(qū)別，很多在機(jī)器人領(lǐng)域得到成功運(yùn)用的技術(shù)和方法，在無人機(jī)領(lǐng)域?qū)⒉辉龠m用。相對于機(jī)器人，無人機(jī)覆蓋航跡規(guī)劃的特點(diǎn)主要在于以下幾點(diǎn)：

1）無人機(jī)不允許飛行過程中出現(xiàn)直角轉(zhuǎn)彎、停止、側(cè)移，甚至倒退等機(jī)動(dòng)，而機(jī)器人則很容易實(shí)現(xiàn)上述機(jī)動(dòng)；

2）無人機(jī)轉(zhuǎn)彎時(shí)有最小轉(zhuǎn)彎半徑的限制，而機(jī)器人一般則沒有；

3）無人機(jī)攜帶成像傳感器的探測范圍會(huì)隨著無人機(jī)飛行高度、俯仰角、偏航角和滾轉(zhuǎn)角的變化而變化，而機(jī)器人則不會(huì)出現(xiàn)這種情況。

文獻(xiàn)[2]中給出了一種較為完整的2維平面上的無人機(jī)覆蓋航跡規(guī)劃的實(shí)現(xiàn)算法，其核心是子區(qū)域的分解。子區(qū)域分解的目的是為了將復(fù)雜的地形盡可能的簡單化。其基本思想是運(yùn)用分類的方法，將基本的幾何圖形從待覆蓋區(qū)域表面分離出來。而后將每個(gè)區(qū)域沿著按照既定的規(guī)則生成覆蓋的軌跡進(jìn)行覆蓋規(guī)劃。本文考慮到在分解之后，應(yīng)當(dāng)重新合并一些相鄰的子區(qū)域。由于在之前的區(qū)域分解步驟中將算法的步驟嚴(yán)格限定為覆蓋完一個(gè)子區(qū)域之前不能進(jìn)入下一個(gè)子區(qū)域，所以應(yīng)當(dāng)重新合并一些分解過多的區(qū)域。將一些區(qū)域合并到相鄰的區(qū)域中可以降低整個(gè)算法設(shè)計(jì)的復(fù)雜度。因此，本文提出了一種相鄰子區(qū)域間合并的算法，通過計(jì)算子區(qū)域的特性，設(shè)計(jì)相關(guān)規(guī)則對子區(qū)域進(jìn)行合并，從而有效地簡化覆蓋的過程，加快無人機(jī)覆蓋速率。

1 相鄰子區(qū)域合并法

在文獻(xiàn)[2]中，通過將一個(gè)復(fù)雜的區(qū)域分解為簡單子區(qū)域的方式來將覆蓋的問題簡化，然后對每個(gè)子區(qū)域分別進(jìn)行覆蓋使得每個(gè)子區(qū)域內(nèi)無人機(jī)的轉(zhuǎn)彎次數(shù)達(dá)到最低，最后用盡可能短的路徑將子區(qū)域連接起來，這樣就得到了一個(gè)相對最優(yōu)的航跡規(guī)劃結(jié)果。

然而，由于方法選擇的限制，無人機(jī)在將一個(gè)子區(qū)域完全覆蓋前不會(huì)進(jìn)入到下一個(gè)子區(qū)域中，這使得在覆蓋某些相鄰區(qū)域時(shí)，將帶來很多不必要的轉(zhuǎn)彎機(jī)動(dòng)，如果用平滑的路徑從一個(gè)區(qū)域過渡到另一個(gè)區(qū)域，將極大的減少這種損耗。如圖1所示，按照原來的方法，整個(gè)區(qū)域?qū)?huì)被劃分成兩個(gè)子區(qū)域，然后按照順序依次進(jìn)行覆蓋，在一個(gè)區(qū)域覆蓋完成之前，無人機(jī)飛行到兩區(qū)域的交界線時(shí)，將進(jìn)行180度轉(zhuǎn)彎，繼續(xù)在原區(qū)域飛行，這樣在兩個(gè)區(qū)域的交界線上無人機(jī)會(huì)進(jìn)行大量的轉(zhuǎn)彎機(jī)動(dòng)，這將帶來極大的燃油和時(shí)間上的損耗（如圖1所示）。我們可以通過制定更靈活的飛行策略來避免這種損耗，當(dāng)無人機(jī)飛行到區(qū)域交界線時(shí)，用平滑的軌跡進(jìn)入到下一個(gè)區(qū)域中，讓兩個(gè)區(qū)域在無人機(jī)的往復(fù)飛行中同時(shí)被覆蓋（如圖2所示）。這樣，交界線上的大量轉(zhuǎn)彎能夠得到避免，以此節(jié)約大量的時(shí)間和燃油成本。

圖1 依次覆蓋子區(qū)域示意圖Fig.1 An example of covering sub-regions one-by-one

圖2 兩個(gè)子區(qū)域過渡示意圖Fig.2 Transition between sub-regions can save turning cost and head land area

下面我們開始討論用以上思路，即合并一些相鄰的子區(qū)域以此來減少區(qū)域邊界上的轉(zhuǎn)彎消耗，對航跡進(jìn)行優(yōu)化的具體方法。在子區(qū)域劃分的步驟完成之后，子區(qū)域的邊界可以分為兩類，“原始邊”（原區(qū)域邊界，圖3中實(shí)線所示）以及“插入邊”（為分割子區(qū)域所加入的邊，圖3中虛線所示）。由于合并子區(qū)域時(shí)所消除的邊一定是后來加入的，所以首先應(yīng)當(dāng)做的挑出出所有的“插入邊”，然后逐個(gè)判斷是否應(yīng)當(dāng)合并其所相鄰的兩個(gè)子區(qū)域。判斷的結(jié)果可以根據(jù)如下判定函數(shù)來決定：

其中，F(xiàn)，F(xiàn)t分別代表子區(qū)域合并前后轉(zhuǎn)彎過程的損失函數(shù)；n1，n2為子區(qū)域合并前兩區(qū)域在交界線處的轉(zhuǎn)彎機(jī)動(dòng)次數(shù)；θ1，θ2為兩區(qū)域中航跡方向角；Li為相鄰區(qū)域交界線的長度；φi為該交界線的方向角；Rc為子區(qū)域合并可能帶來的覆蓋率的損失；ε為協(xié)同系數(shù)。當(dāng)D＞0時(shí)保留區(qū)域劃分，當(dāng)D＞0時(shí)，將該條邊分割的兩個(gè)子區(qū)域合并。

圖3 子區(qū)域分解示意圖Fig.3 Decomposition of the uncovered region

一般來講，由于θ1，θ2與φi夾角的不同，兩側(cè)子區(qū)域與交界線相交的平行航跡的條數(shù)也不相同（如圖4所示），這將會(huì)帶來兩個(gè)問題：第一，如何將交界線兩邊的航跡線兩兩配對，將之連接成一條新的整體的可行航跡，第二，兩個(gè)子區(qū)域中平行航跡與交界線的交點(diǎn)是交錯(cuò)的，在完成配對后如何從一條航跡過渡到另外一條航跡[5]。

圖4 相鄰子區(qū)域掃描線條數(shù)不同F(xiàn)ig.4 One case with unequal numbers of rows on the two sides of the dividing line

2 子區(qū)域間軌跡銜接

整個(gè)轉(zhuǎn)彎過程的損失，其實(shí)就是無人機(jī)轉(zhuǎn)過|θ1－θ2|度角的過程的飛行消耗。首先想到的方法是不改變原有的航跡，在兩條航跡與邊界線的交點(diǎn)中間添加對應(yīng)的過渡航跡。L.E.Dubin在1957年提出了名為Dubins曲線的理論[3]，在給定曲率的情況下尋找連接同一平面內(nèi)具有特定方向向量的任意兩點(diǎn)的最短軌跡曲線。如圖5所示，對于起始向量和結(jié)束向量分別作兩個(gè)切圓，其半徑為無人機(jī)的最小轉(zhuǎn)彎半徑。Dubins曲線的最短路徑即為兩圓公切線和對應(yīng)的過渡圓弧所連成的軌跡。

容易計(jì)算出，穿過交界線的次數(shù)為：

設(shè)內(nèi)切線長度為L’，的方向角為φ’，沿內(nèi)切線方向作輔助圓，可以得到 η=п/2－φ’（如圖 6 所示）。此時(shí)（忽略直線飛行L’所帶來的影響）：

圖5 Dubins曲線過渡法Fig.5 Transition using Dubins curves

圖6 損失函數(shù)計(jì)算示意圖Fig.6 Calculation of cost function

可以看出，采用這種方法，從一個(gè)區(qū)域過渡到另一個(gè)區(qū)域的過程中，仍然需要進(jìn)行大量的轉(zhuǎn)彎機(jī)動(dòng)，對于覆蓋效率的提升并不明顯，于是考慮一種更簡單的方法：將兩條航跡延長至相交，然后在兩條航跡的交角處用最短的圓弧過渡（如圖7所示）。此時(shí)

圖7 轉(zhuǎn)彎中平滑過渡示意圖Fig.7 The smooth turning during transition

在轉(zhuǎn)彎的過程中，由于兩條相鄰航跡間距離的不均勻，在拐角處會(huì)有一定的區(qū)域遺漏，如圖8所示。兩條航跡間損失區(qū)域的面積為

其中 α=|θ1-θ2|/2，全部面積損失為：

圖8 覆蓋損失面積計(jì)算示意圖Fig.8 Calculation of cost area

3 相鄰子區(qū)域掃描線配對

對于掃描線數(shù)量不相等的相鄰子區(qū)域，路徑的連接方法通常有兩種：多出的掃描線可以通過外角連接（如圖9所示），也可以通過內(nèi)角連接（如圖10所示）。對于這個(gè)問題，圖10中的連接方式是更好的選擇，這是因?yàn)椴捎脠D9中的連接方式會(huì)導(dǎo)致如下問題：當(dāng)外角的路徑確定后，內(nèi)角的路徑需要更小的轉(zhuǎn)彎半徑才能，這會(huì)導(dǎo)致內(nèi)角的路徑需要更小的轉(zhuǎn)彎半徑完成不同子區(qū)域間掃描線的過渡，而無人機(jī)存在最小轉(zhuǎn)彎半徑的限制，因此可能會(huì)導(dǎo)致規(guī)劃出的路徑是不可用的[5]。

圖9 掃描線的外角連接Fig.9 Pair the swaths from outside corner

圖10 掃描線的內(nèi)角連接Fig.10 Pair the swaths from inside corner

4 算法實(shí)現(xiàn)

下面給出改進(jìn)后算法的具體實(shí)現(xiàn)步驟以及一個(gè)實(shí)例

1）獲取待覆蓋區(qū)域的信息，將其邊界簡化為多邊形的形式（如圖11所示）；

2）根據(jù)無人機(jī)的飛行特性以及區(qū)域的特性，將帶覆蓋區(qū)域分解為凸多邊形區(qū)域（如圖12所示）；

3）對相鄰子區(qū)域運(yùn)用判定函數(shù)D進(jìn)行計(jì)算，如果結(jié)果D＞0，則將其合并；

4）根據(jù)合并后的子區(qū)域規(guī)劃出無人機(jī)的飛行路徑（如圖13所示）。

圖11 待覆蓋區(qū)域示意圖Fig.11 Uncovered area

圖12 子區(qū)域分解示意圖Fig.12 Decomposition of uncovered area

圖13 子區(qū)域合并及路徑規(guī)劃Fig.13 Combination of sub－regions and path planning

5 結(jié) 論

文中通過分析二維平面上多邊形區(qū)域的特性，給出的無人機(jī)覆蓋航跡規(guī)劃中子區(qū)域合并的算法。按照本方法在整體的規(guī)劃后需進(jìn)行一次子區(qū)域的合并，將具有特定幾何特性的相鄰子區(qū)域合并為一個(gè)區(qū)域，這樣就克服了之前一些算法在某些情形下子區(qū)域劃分過多的缺點(diǎn)。無人機(jī)按照本方法規(guī)劃的路徑進(jìn)行飛行時(shí)，可獲得更少的轉(zhuǎn)彎次數(shù)以及更短的航程，這樣就節(jié)約了飛行成本并且提高的任務(wù)執(zhí)行的效率，因此具有更好的實(shí)用性。

[1]陳海，王新民，焦裕松，等.無人機(jī)覆蓋路徑規(guī)劃中轉(zhuǎn)彎機(jī)動(dòng)的運(yùn)動(dòng)學(xué)分析[J].飛行力學(xué)，2010（2）:31－34.CHEN Hai，WANG Xin-min，JIAO Yu-song，et al.Kinematics analysis of UAV turning motion in coverage path planning[J].Flight Dynamics，2010（2）:31－34.

[2]陳海，王新民，焦裕松，等.一種凸多邊形區(qū)域的無人機(jī)覆蓋航跡規(guī)劃算法[J].航空學(xué)報(bào)，2010（9）:1802－1808.CHEN Hai，WANG Xin-min，JIAO Yu-song，et al.An algorithm of coverage flight path planning for UAVs in convex polygon areas[J].Acta Aeronautica et Astronautica Sinica，2010（9）:1802－1808.

[3]Dubins L.On plane curves with curvature[J].Pacific Journal of Mathematics，1961，11（2）:471－481.

[4]Shkel A M，Lumelsky V.Classification of the Dubins set[J].Robotics and Autonomous Systems，2001，34（4）:179－202.

[5]Jin J.Optimal field coverage path planning on 2D and 3D surfaces[J].Dissertations&Theses Gradworks，2009:152.

[6]Chazelle B.Dobkin D.Optimal convex decompositions[C]//In:Toussaint G.T.Ed.Computational GeometryAmslerdam:North－Holland，1985:63－133.

[7]Huang Y Q，Liu Y K.An algorithm for the clipping against a polygon based on shearing transformation [J].Computer Graphics Forum，2002，21（4）:683－688.