無人機覆蓋航跡規劃中子區域合并方法設計

王文旭，李 立，李 儼

（西北工業大學 陜西 西安 710072）

無人機區域覆蓋航跡規劃 （Coverage Flight Path Planning，CFPP）定義為：在滿足某種（某些）性能指標最優的前提下，避開障礙物和威脅源，規劃出一條能夠遍歷待覆蓋區域的最優飛行路線。在機器人領域，該技術稱為區域覆蓋路徑規劃（Coverage Path Planning，CPP）技術。

現今，國內外對覆蓋航跡（路徑）規劃技術的研究主要集中在機器人領域，對無人機領域的研究相對較少。在機器人領域，覆蓋路徑規劃技術的應用領域主要包括：室內清潔、擦窗、割草、自動噴漆、耕犁、播撒、檢測探傷、排雷等。在無人機領域，覆蓋航跡規劃技術的應用領域主要包括：安全監控、戰場偵察、目標搜索、地形測繪、礦藏勘測等[1]。

隨著無人機在民用及軍用領域應用范圍的不斷擴大，無人機對覆蓋航跡規劃技術的需求也更加的強烈。由于機器人和無人機所處的環境及特性都有所區別，很多在機器人領域得到成功運用的技術和方法，在無人機領域將不再適用。相對于機器人，無人機覆蓋航跡規劃的特點主要在于以下幾點：

1）無人機不允許飛行過程中出現直角轉彎、停止、側移，甚至倒退等機動，而機器人則很容易實現上述機動；

2）無人機轉彎時有最小轉彎半徑的限制，而機器人一般則沒有；

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

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

1 相鄰子區域合并法

在文獻[2]中，通過將一個復雜的區域分解為簡單子區域的方式來將覆蓋的問題簡化，然后對每個子區域分別進行覆蓋使得每個子區域內無人機的轉彎次數達到最低，最后用盡可能短的路徑將子區域連接起來，這樣就得到了一個相對最優的航跡規劃結果。

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

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

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

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

其中，F，Ft分別代表子區域合并前后轉彎過程的損失函數；n1，n2為子區域合并前兩區域在交界線處的轉彎機動次數；θ1，θ2為兩區域中航跡方向角；Li為相鄰區域交界線的長度；φi為該交界線的方向角；Rc為子區域合并可能帶來的覆蓋率的損失；ε為協同系數。當D＞0時保留區域劃分，當D＞0時，將該條邊分割的兩個子區域合并。

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

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

圖4 相鄰子區域掃描線條數不同Fig.4 One case with unequal numbers of rows on the two sides of the dividing line

2 子區域間軌跡銜接

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

容易計算出，穿過交界線的次數為：

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

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

圖6 損失函數計算示意圖Fig.6 Calculation of cost function

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

圖7 轉彎中平滑過渡示意圖Fig.7 The smooth turning during transition

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

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

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

3 相鄰子區域掃描線配對

對于掃描線數量不相等的相鄰子區域，路徑的連接方法通常有兩種：多出的掃描線可以通過外角連接（如圖9所示），也可以通過內角連接（如圖10所示）。對于這個問題，圖10中的連接方式是更好的選擇，這是因為采用圖9中的連接方式會導致如下問題：當外角的路徑確定后，內角的路徑需要更小的轉彎半徑才能，這會導致內角的路徑需要更小的轉彎半徑完成不同子區域間掃描線的過渡，而無人機存在最小轉彎半徑的限制，因此可能會導致規劃出的路徑是不可用的[5]。

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

圖10 掃描線的內角連接Fig.10 Pair the swaths from inside corner

4 算法實現

下面給出改進后算法的具體實現步驟以及一個實例

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

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

3）對相鄰子區域運用判定函數D進行計算，如果結果D＞0，則將其合并；

4）根據合并后的子區域規劃出無人機的飛行路徑（如圖13所示）。

圖11 待覆蓋區域示意圖Fig.11 Uncovered area

圖12 子區域分解示意圖Fig.12 Decomposition of uncovered area

圖13 子區域合并及路徑規劃Fig.13 Combination of sub－regions and path planning

5 結 論

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

[1]陳海，王新民，焦裕松，等.無人機覆蓋路徑規劃中轉彎機動的運動學分析[J].飛行力學，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]陳海，王新民，焦裕松，等.一種凸多邊形區域的無人機覆蓋航跡規劃算法[J].航空學報，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.