無人機覆蓋航跡規(guī)劃中子區(qū)域合并方法設計

王文旭，李 立，李 儼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一般來講，由于θ1，θ2與φi夾角的不同，兩側(cè)子區(qū)域與交界線相交的平行航跡的條數(shù)也不相同（如圖4所示），這將會帶來兩個問題：第一，如何將交界線兩邊的航跡線兩兩配對，將之連接成一條新的整體的可行航跡，第二，兩個子區(qū)域中平行航跡與交界線的交點是交錯的，在完成配對后如何從一條航跡過渡到另外一條航跡[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ū)域間軌跡銜接

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算法實現(xiàn)

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

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

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

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

4）根據(jù)合并后的子區(qū)域規(guī)劃出無人機的飛行路徑（如圖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ū)域的特性，給出的無人機覆蓋航跡規(guī)劃中子區(qū)域合并的算法。按照本方法在整體的規(guī)劃后需進行一次子區(qū)域的合并，將具有特定幾何特性的相鄰子區(qū)域合并為一個區(qū)域，這樣就克服了之前一些算法在某些情形下子區(qū)域劃分過多的缺點。無人機按照本方法規(guī)劃的路徑進行飛行時，可獲得更少的轉(zhuǎn)彎次數(shù)以及更短的航程，這樣就節(jié)約了飛行成本并且提高的任務執(zhí)行的效率，因此具有更好的實用性。

[1]陳海，王新民，焦裕松，等.無人機覆蓋路徑規(guī)劃中轉(zhuǎn)彎機動的運動學分析[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]陳海，王新民，焦裕松，等.一種凸多邊形區(qū)域的無人機覆蓋航跡規(guī)劃算法[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.