宋志強， 陳少博

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

0 引言

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

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

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

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

1 覆蓋問題描述

1.1 感興趣區(qū)域

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

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

圖1 完全覆蓋航跡示例

1.2 航線方向設(shè)置

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

覆蓋行數(shù)

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

飛行線之間的距離

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

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

1.3 邊-點路徑構(gòu)建

為構(gòu)建邊-點路徑，通過迭代將線Lflight與多邊形相交將航點添加到航跡中（見算法1）。該算法需要輸入多邊形、初始頂點b，相鄰頂點bmate，頂點b的對映頂點a以及飛行線之間的距離dx。對于固定翼無人機，取dx=2Rmin。首先，創(chuàng)建一條Lflight，平行于邊（b，bmate），其垂直于掃描方向且位移一個偏移量Δinit=d/2（見圖2）。Lflight與多邊形相交，得到點ip1和ip2，通過CheckAndConnect函數(shù)建立垂直約束，并按照正確的順序連接起來以形成無人機的航線，對于固定翼無人機來說，這有利于杜賓曲線的構(gòu)建。不斷將直線向a方向移動并與多邊形相交，最后算法返回航跡ρ=｛p0，…，pm｝。構(gòu)造的邊-點路徑從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 改進的旋轉(zhuǎn)卡尺航跡規(guī)劃

2.1 算法簡介

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

圖3 算法總體流程圖

2.2 航跡規(guī)劃

2.2.1 對映點對計算

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

算法2旋轉(zhuǎn)卡尺航跡規(guī)劃。得到包含起點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 計算每組對映點對的最優(yōu)航跡

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

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

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

輸出：ρ

/*順時針旋轉(zhuǎn)卡尺*/

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

2. b ←j；

3. a ←i；

4. else

5. b ←i；

6. a ←j；

/*逆時針旋轉(zhuǎn)卡尺*/

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）；

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

圖4 卡尺順時針旋轉(zhuǎn)示意圖

逆時針方向旋轉(zhuǎn)卡尺以找到另一條可能的航跡，基邊為（b2，b2+1）。從嵌入式系統(tǒng)角度考慮，采用同一個angle（）函數(shù)，基于此，測量相對于直線B的角度，直線B與（b，b+1）重合（見圖5）。角γb即邊（b-1，b）和直線B之間的角度。角γa為邊（a-1，a）和直線A之間的角度，直線A為經(jīng)過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 卡尺最后位置與之前多邊形邊之間的角度

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

3 實驗結(jié)果與分析

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

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

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

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

4 結(jié)語

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

·名人名言·

我們應(yīng)該不虛度一生，應(yīng)該能夠說，“我已經(jīng)做了我能做的事?！?/p>

——居里夫人