王文旭,李 立,李 儼
(西北工業(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ū)域進行合并,從而有效地簡化覆蓋的過程,加快無人機覆蓋速率。
在文獻[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
整個轉(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
對于掃描線數(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
下面給出改進后算法的具體實現(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
文中通過分析二維平面上多邊形區(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.