考慮最短轉彎半徑的無人機區域覆蓋航跡規劃

宋志強， 陳少博

（1.無錫學院自動化學院，江蘇 無錫 214105；2.南京信息工程大學濱江學院自動化學院，江蘇 無錫 214105）

0 引言

無人機應用越來越廣泛，將無人機應用于測繪［1］、環境監測［2］、搜救［3］、精確農業［4］等，得益于無人機機載傳感器獲取地面信息并實現區域覆蓋。此類應用中，高效的無人機航跡規劃算法非常重要，從圖像提取信息的時間、成本和質量直接關系到規劃質量。在各種應用中，二維覆蓋尤為成功。覆蓋任務分兩步驟進行，一是準備階段，選擇運載工具、相機配置和任務規劃，二是執行階段，無人機自主飛行并收集數據。要實現任務的完全自動化，就必須解決任務規劃問題，其核心是覆蓋航跡規劃，定義為計算無人機航跡的任務，使得感興趣區域（Region of Interest，ROI）的所有點都能被監測到［5］。現有的規劃器沒有考慮連接路徑，即無人機起飛點到ROI 的路徑以及從ROI 到無人機著陸點的航跡，不考慮連接路徑通常并不是無人機執行任務的完整路徑，且當任務由多個ROI 和多個連接路徑組成時，路徑長度增量更大。因此，有必要規劃一條考慮任務起點和終點的路徑。此外，固定翼無人機的最小轉彎半徑也是需要考慮的因素。

直線飛行形成來回航跡（Back and Forth Path，BFP）需要計算路線的方向，以往的研究僅在舍棄起點和終點的航線上定義路徑最優性。一般來說，如果想保持BFP作為覆蓋模式，必須結合起點、終點提供最小成本的BFP 執行搜索。一個簡單的策略是循環BFP直到出現最小值，但這不是有效策略。本文提出一種改進的旋轉卡尺路徑規劃算法，考慮無人機的起飛點和著陸點，并考慮固定翼無人機的最小轉彎半徑，使算法更具實用性。

Huang［6］提出一種移動機器人排雷作業的覆蓋方法，使用無人機覆蓋航跡規劃大多遵循Huang 定義的最優準則，即航線數量最少的路徑為最優路徑。Huang提出機器人來回運動的掃描方向必須垂直于感興趣區域多邊形的最小寬度，方法沒有考慮從起點到感興趣區域的距離。一些文獻研究非凸區域的覆蓋問題，涉及凹多邊形凸分解［7］，Li 等［8］將非凸ROI 分解為凸單元，通過設置垂直于單元最小寬度的飛行線來計算路徑的最優方向。王自亮等［9］采用對凹多形區域直接遍歷的方法，實現對區域的覆蓋，但凹多邊形區域存在狹長區域時，容易產生多個轉彎路徑。王紅星等［10］針對凹多邊形區域進行凸分解，研究區域覆蓋算法，使無人機對指定區域進行覆蓋搜索。劉旭林等［11］選取凹多邊形及其凸包的邊所在的方向分別為主方向，得到全局最優解。Coombes 等［12］考慮風速對無人機航跡的影響，旨在減少固定翼飛機測量飛行時間。多無人機協同搜索［13-15］可提高任務的完成速度，一般的方法是將其分為區域劃分和區域覆蓋搜索路徑規劃兩個子問題處理。Fevgas 等［16］通過無人機的合作策略以實現節能的覆蓋航跡規劃。對無人機區域覆蓋中的轉彎控制［17-19］，也是值得研究的問題。文獻［20］中提出一種包含無人機飛行起點和終點的邊-點來回掃描覆蓋航跡規劃，但主要針對凸多邊形區域，且沒有考慮固定翼無人機的最小轉彎半徑。

綜上，以前的方法很少考慮無人機起飛點到達ROI的連接路徑，考慮連接路徑和ROI凹凸性以及固定翼無人機最小轉彎半徑的覆蓋航跡規劃，更具實用價值。

1 覆蓋問題描述

1.1 感興趣區域

假設ROI 為二維平面圖形Q=｛V，E｝，其中V=｛1，2，…，n｝為頂點集，E=｛（1，2），…，（n-1，n），（n，1）｝為邊集。

對于凸多邊形區域，第一步是尋找覆蓋最優方向，其垂直于多邊型區域的最小高度，在這一方向上，區域可被最少行覆蓋，即無人機的轉彎次數也最少，完全覆蓋航跡如圖1 所示。轉彎次數和覆蓋指定區域的時間直接相關，具有最少轉彎次數的航線在航線長度、無人機續航時間、能量消耗等方面更優。

圖1 完全覆蓋航跡示例

1.2 航線方向設置

假設無人機將飛越要覆蓋的區域，并在垂直于給定掃描方向的行中來回運動。為找到給定多邊形的最佳覆蓋方向，可使多邊形在平面內繞水平軸旋轉，并測量其高度。最佳方向是產生最小高度hmin的方向。一旦找到最佳掃描方向，就可在該區域規劃航跡。假設圖像傳感器平行于地平面，已知圖像傳感器的寬度l，相機鏡頭的焦距為f，均以mm 為單位，相機到地面的距離H（飛行高度），單位為m，則相機在地面上的覆蓋寬度（m）

覆蓋行數

式中，α∈（0，1）為兩幅圖像之間的重疊比例，這種重疊通常是連接圖像以組成航空地圖所必需的。

飛行線之間的距離

對于固定翼無人機，還須考慮其最小轉彎半徑

式中：v為無人機飛行速度；g為重力加速度；φmax為無人機最大滾轉角。

1.3 邊-點路徑構建

為構建邊-點路徑，通過迭代將線Lflight與多邊形相交將航點添加到航跡中（見算法1）。該算法需要輸入多邊形、初始頂點b，相鄰頂點bmate，頂點b的對映頂點a以及飛行線之間的距離dx。對于固定翼無人機，取dx=2Rmin。首先，創建一條Lflight，平行于邊（b，bmate），其垂直于掃描方向且位移一個偏移量Δinit=d/2（見圖2）。Lflight與多邊形相交，得到點ip1和ip2，通過CheckAndConnect函數建立垂直約束，并按照正確的順序連接起來以形成無人機的航線，對于固定翼無人機來說，這有利于杜賓曲線的構建。不斷將直線向a方向移動并與多邊形相交，最后算法返回航跡ρ=｛p0，…，pm｝。構造的邊-點路徑從b開始到bmate，并掃向a。如果航跡包含起飛點和著陸點，則可表示為：τ=｛ps，p0，…，pm，pe｝。

算法1獲取多邊形的邊-頂點路徑（GetPath（b，bmate，a））。該算法計算多邊形Q=｛V，E｝的來回路徑（ρ=｛p0，p1，…，pm｝）。路徑從初始頂點b開始，指向bmate，然后掃向a。

輸入：Q，d，b，bmate，a

輸出：ρ

1. Δinit= d/2；

2. Lflight←GenerateLine（b，bmate）；

3. Lflight←OffSet（Lflight，Δinit）；

4. ρ ←?；

5. while Intersects（C（Lflight），Q）do

6. ip1，ip2←IntersectEdges（Lflight，E）；

7. ρ ←CheckAndConnect（ρ，ip1，ip2）；

8. Lflight←OffSet（Lflight，d）；

9. return ρ；

2 改進的旋轉卡尺航跡規劃

2.1 算法簡介

改進的旋轉卡尺航跡規劃總體流程如圖3 所示，該算法對固定翼無人機和多旋翼無人機均適用，路徑規劃開始時，輸入RoI的頂點坐標，算法根據RoI是否為凸多邊形而作相應處理，如果是凸多邊形，則對凸多邊形作旋轉卡尺航跡規劃。如果是凹多邊形則先將RoI分割成最少個數的凸多邊形［21］，再對子區域做旋轉卡尺航跡規劃。在得到航點后，如果無人機是固定翼的，則標記相應轉彎航點，以便將算法應用于實際時，對轉彎航跡進行離散化處理后上傳至飛控。

圖3 算法總體流程圖

2.2 航跡規劃

2.2.1 對映點對計算

考慮任務起止點，采用旋轉卡尺航跡規劃［20］來得到覆蓋RoI的航跡。建立覆蓋RoI的來回搜索模式，以找到結合起點和終點的最少路徑。如果不考慮任務的起點和終點，那么最優路徑是飛行線垂直于最小寬度的路徑。一般來說，為解決這個問題，必須測試具有起點和終點的來回路徑的所有可能組合。發現所有來回路徑的覆蓋都始于和終于對映點對，對映點對的數量被限制在x=（3/2）·n。若已知一組給定對映點對的最優路徑，則與起點和終點的組合也能計算出來。算法2 為旋轉卡尺航跡規劃，第1 行ComputeAntipodalPairs函數用于獲得對映點對集，輸入為頂點集V，返回凸多邊形的對映點對集，即A=｛（i1，j1），（i2，j2），…，（in，jn）｝，在O（n）時間內計算所有對映點對，其中n是多邊形的頂點數。對于每組對映點對（第3 行），計算最優路徑（第4 行），并將其附加到起點和終點（第5 行）。BestPath（）函數將在2.2.2 節中解釋。由于路徑的順序很重要，按照正序和逆序進行測試，并選擇距離最小的路徑（第5 行）。如果當前路徑的代價更小，則將其保留為最優完整航跡（τ）。最后，一旦測試完所有的對映點對，返回τ。

算法2旋轉卡尺航跡規劃。得到包含起點ps，邊-點路徑ρ和終點pe的完全航跡τ。

輸入：V，ps，pe

輸出：τ

1. A ←ComputeAntipodalPairs（V）；

2. c*←∞

3. foreach（i，j）∈A do

4. ρ ←BestPath（V，i，j）；

5. τaux←minCost（｛ps，ρ，pe｝，｛pe，ρ，ps｝）；

6. if cost（τaux）＜c*then

7. τ ←τaux；

8. c*←cost（τ）；

9. return τ；

2.2.2 計算每組對映點對的最優航跡

計算對映點對i和j的最優來回航跡，參見算法3。其主要思想是找到通過頂點i和j的一組平行線，它們之間的距離最小，然后得到與這些線匹配的來回航跡。該過程給出一組對映點對和一個接觸該對的卡尺，順時針旋轉卡尺，直到和邊接觸并測量多邊形的高度，然后逆時針旋轉卡尺，直到第2 條邊接觸并測量高度，最后，比較2 個高度以找到最小高度。假設n個頂點從0 到n-1 標號，angle（m，n）函數用于計算一條直線從平行于邊（m，m+1）的位置順時針旋轉到平行于邊（n，n+1）的位置時所掠出的角度。

算法3BestPath（V，i，j）函數計算對映點對的最優航跡ρ，輸入為邊集V和對映點對（i，j）。

輸入：V=｛1，2，…，n｝，（i，j）

輸出：ρ

/*順時針旋轉卡尺*/

1.if angle（i，j）-π ＜0 then

2. b ←j；

3. a ←i；

4. else

5. b ←i；

6. a ←j；

/*逆時針旋轉卡尺*/

7. φ←angle（b，a）-π；

8. γb←angle（b-1，b）；

9. γa←angle（a-1，a）-φ；

10. if γb＜γathen

11. b2←b-1；

12. a2←a；

13. else

14. b2←a-1；

15. a2←b；

/*尋找航線最少的路徑*/

16. if dist（b，a）＜dist（b2，a2）then

17. ρ ←GetPath（b，b+1，a）；

18. else

19. ρ ←GetPath（b2+1，b2，a2）；

首先，順時針旋轉卡尺，找到接觸的第一條邊，以（b，b+1）表示并且它將是一條可能的BFP 的基邊。以圖4 為例，如果在對映點i和j上旋轉直線L和M，第一條接觸邊將是（j，j+1），其與M′相重合。找到邊（b，b+1）的一種方法是找到αi和αj兩者的較小角度，即從假想的支撐線順時針方向旋轉到多邊形最近邊的角度。通過測量從線L′到線M′旋轉的差值而非測量αi和αj確定基邊，參見算法3 的第1 ～6 行。如果角度減去π的差小于零，則邊（j，j+1）被視為航跡的基邊。否則，將邊（i，i+1）作為基邊。一種特殊情況是兩個角度相等，在這種情況下，航線的數量是相同的，就航線數量而言，選擇哪個基邊并不重要。為使算法簡單，在角度相等的情況下，選擇邊（i，i+1）作為基邊。一旦找到邊（b，b+1），就將其存儲為第一個可能的基邊。

圖4 卡尺順時針旋轉示意圖

逆時針方向旋轉卡尺以找到另一條可能的航跡，基邊為（b2，b2+1）。從嵌入式系統角度考慮，采用同一個angle（）函數，基于此，測量相對于直線B的角度，直線B與（b，b+1）重合（見圖5）。角γb即邊（b-1，b）和直線B之間的角度。角γa為邊（a-1，a）和直線A之間的角度，直線A為經過a點的直線B的平行線。角φ與角γa互補以到達邊（a，a+1）、邊（b，b+1）在邊（a，a+1）之前接觸卡尺，因此角φ大于或等于0。角γb和γa的較小值決定兩種可能性中的邊：（b-1，b）或（a-1，a）。一旦確定則第2 個基邊（b2，b2+1）就找到了，則最遠的頂點就是對映點對，參見算法3 第7 ～15 行。

圖5 卡尺最后位置與之前多邊形邊之間的角度

現有2 種可能的航跡：一條以（b，b+1）為基邊的航跡，在頂點a處結束；另一條以（b2，b2+1）為基邊的航跡，在頂點a2處結束。選擇飛行路線最少的路徑，參見算法3 的第16 ～19 行，其中函數dist（b，a）計算與邊（b，b+1）重合的直線與頂點a之間的距離，函數getPath（b，bmate，a）計算原點位于頂點b的BFP，掃描方向垂直于（b，bmate）。

3 實驗結果與分析

對本文所提改進的旋轉卡尺路徑規劃（IRCPP）用Matlab仿真，并和文獻［20］中的RCPP對比，無人機飛行參數如下：無人機飛行速度，v=5 m·s-1，航距，dx=20 m，無人機飛行高度，H=50 m，無人機最小轉彎半徑，Rmin=10 m。

IRCPP與RCPP比較結果如圖6 所示。圖6（a）、（b）分別為IRCPP 和RCPP 對于凸多邊形ROI 時，無人機分別為固定翼和多旋翼時的仿真。當無人機為固定翼時，RCPP并不適用，而IRCPP可根據無人機的類型作出相應的航跡規劃。圖6（c）、（d）分別為IRCPP和RCPP對于凹多邊形RoI 時，無人機分別為固定翼和多旋翼時的仿真。IRCPP首先進行凹多邊形區域凸分解，然后再做規劃，而RCPP 對于凹多邊形ROI，雖然也能完成航跡規劃，但對于具有狹長區域的地形，其轉彎次數多于IRCPP，如圖6（c）、（d）所示，IRCPP 轉彎17 次，RCPP轉彎21 次。

圖6 兩種算法在固定翼和多旋翼無人機路徑規劃中的比較

綜上，RCPP 只適合于ROI 是凸多邊形的多旋翼無人機航跡規劃，而IRCPP可根據ROI的形狀和無人機類型作出相應的航跡規劃，更具實用性。

4 結語

改進的旋轉卡尺路徑規劃算法考慮被測區域的凹凸性，如果被測區域是凹多邊形，則先將其分割為具有最少個數的凸邊形，使算法更具實用性。將無人機飛行起點和著陸點包括在內，計算最優邊-點來回航跡，構成完整覆蓋航跡，更符合實際應用場景，算法復雜度為O（n），其中n為感興趣區域的邊數。考慮無人機類型，如果是固定翼無人機，則需考慮其最小轉彎半徑，使算法更具適用性。實驗仿真表明了算法的實用性和適用性。

·名人名言·

我們應該不虛度一生，應該能夠說，“我已經做了我能做的事。”

——居里夫人