無人機地理圍欄越界探測算法改進與分析

謝東岑，梁曉龍，張佳強，付其喜，張凱

(1.中國人民解放軍95140部隊，惠州 516200) (2.空軍工程大學 國家空管防相撞技術重點實驗室，西安 710051) (3.空軍工程大學 陜西省電子信息系統綜合集成重點實驗室，西安 710051) (4.中國人民解放軍94582部隊，駐馬店 463225) (5.空軍工程大學 空管領航學院，西安 710051)

0 引 言

在無人機行業不斷興起、無人機駕駛員成為了一種新職業的大背景下，無人機的使用越來越頻繁；同時，涉及無人機的事故數量也在增加，而目前各國均缺少對無人機的相關規定，只能向無人機運營商提供建議[1]。一系列無人機空中交通事故的發生，讓人們意識到低空空域無人機監管的重要性和必要性。地理圍欄的發展讓無人機監管越來越簡單高效，無人機地理圍欄是一個虛擬的柵欄邊界，由垂直高度的限制和水平方向的邊界組成[2]，它可以將通過GPS或雷達獲取的位置信息作為輸入，經運行地理圍欄越界探測算法判斷其是否在指定的空域內飛行，一旦無人機的飛行航向將與地理圍欄邊界發生沖突，它就會提前告警，并配合機載傳感器和規避系統做出相應的反應，有助于提高無人機自主水平。

由于無人機地理圍欄能夠有效地解決無人機監管過程中的問題，國內外越來越重視這方面的研究發展。國內大疆無人機[3]的GEO(Geospatial Environment Online)就有地理圍欄技術的應用，能為大疆用戶提供相關信息，幫助用戶在飛行時間和地點上做出合理決定，但其存在兩點不足：一是技術不夠成熟，不能完全可靠地實現地理圍欄越界探測；二是只適用于部分機型。強明輝等[4]利用無人機感知與規避系統、基于地理圍欄的地面站避讓系統模型、添加了高度參數的地理圍欄優化算法，實現了基于無人機地面站避讓系統的地理圍欄算法設計與仿真，將地理圍欄算法與無人機的機載定位導航系統結合起來，不需要雷達等其他機載探測設備，具有很強的實際應用性與創新性；付其喜等[5]提出了無人機地理圍欄預控制層生成算法，實現了自主飛行的無人機地理圍欄算法設計，能保證自主飛行的無人機在地理圍欄內安全飛行。但上述文獻均未對無人機越界探測功能進行深入研究。國外同樣也在開發類似的地理圍欄技術。T.Gurriet等[6]利用優化方法和盡可能微小的飛行指令變動，在避免地理圍欄越界的前提下，實現了平滑規避軌跡的生成，但該方法僅適用于圓形地理圍欄，難以適應無人機復雜的飛行環境；M.N.Stevens等[7]提出并實現了二維和三維方向上的TWC(Triangle Weight Characterization)算法，適用于任意復雜不自相交的多邊形，并且運行速度大幅提高，但是一旦地理圍欄邊界有所變化，則該算法的初始化步驟又要重新進行。

本文在國內外地理圍欄相關研究的基礎上，針對射線算法的不足進行改進，避免射線法出現錯誤判斷的情況，提高算法的準確性；并通過仿真實現基于改進射線法的無人機地理圍欄越界探測算法，對影響其運行時間的因素進行深入研究和分析說明，以便適用于復雜多變的飛行環境和更多種類的無人機。

1 無人機地理圍欄算法的一般流程

地理圍欄有兩種類型：一種是禁出型地理圍欄，它為無人機定義了一個有界的可飛空域，無人機不能飛出這一圍欄空域；另一種是禁入型地理圍欄，是為了防止無人機進入并且與其保持一定距離而定義的一個圍欄空域。地理圍欄有水平的邊界和垂直高度的限制。一般地，地理圍欄可以由一個禁出型地理圍欄和若干個禁入型地理圍欄組成，其算法基本流程如圖1所示。

圖1 地理圍欄算法基本流程Fig.1 Basic flow of violation detection algorithm

輸入參數為r和g，r=(x,y)為當前無人機橫向平面位置，用于探測是否存在地理圍欄沖突。地理圍欄由G=[gi,go]指定，其中gi為禁出型地理圍欄邊界多邊形；go={go1，…，gon}是一組禁入型地理圍欄邊界；gok是n個禁入型地理圍欄邊界多邊形的第k個。pointinpolygon()函數是一種點包容算法，可以是射線算法，也可以是TWC算法，如果地理圍欄邊界為圓形，還可以是圓形地理圍欄算法。只要沒有發生地理圍欄沖突，它就會為每個新的狀態執行循環。

2 無人機地理圍欄越界探測算法改進

無人機地理圍欄越界探測算法根據地理圍欄邊界的形狀可以分為：圓形地理圍欄算法、矩形地理圍欄算法、復雜多邊形地理圍欄算法[8]。復雜多邊形地理圍欄算法更符合實際應用，也能節省更多的空域資源，提高空域利用率。該算法中目前用得最多的是射線法算法[9]。

2.1 基于射線法的地理圍欄越界探測算法

(1) 算法原理

從無人機測試點r投影出一條射線s(如圖2所示)，如果這條射線相交于奇數條多邊形的邊，則測試點r包含在地理圍欄p中，否則r在p之外。

圖2 射線法示意圖Fig.2 Schematic diagram of ray cast algorithm

(2) 判定規則

①若為禁入型地理圍欄，設置“c為奇數”為地理圍欄沖突事件，具體判定規則如下：

判定規則1：c為奇數時，無人機此時已進入禁飛區，其飛行器系統相應模塊應作出反應。

判定規則2：c為偶數時，無人機沒有進入禁飛區。

②若為禁出型地理圍欄，設置“c為偶數”為地理圍欄沖突事件，具體判定規則如下：

判定規則1：c為偶數時，無人機此時已飛出指定空域，其飛行器系統相應模塊應作出反應。

判定規則2：c為奇數時，無人機此時在指定空域內飛行。

2.2 基于改進射線法的地理圍欄越界探測算法

使用原始射線法可能出現特殊情況(如圖3所示)，即射線會與多邊形頂點相交、射線經過多邊形的一條邊[10]，甚至測試點p就在多邊形邊上[11]。若仍使用原始射線法進行交點計數，則會產生錯誤的判斷，因此將射線法原理進行改進，提高其準確性。

圖3 原始射線法可能出現的特殊情況Fig.3 Special cases that may occur with the original ray cast algorithm

(1) 算法原理

在原始射線法的基礎上，設置一個用于判斷特殊情況的緩沖距離D，規定引出的射線是y方向的，當測試點的x坐標在地理圍欄邊界頂點的x坐標的緩沖距離內時，將地理圍欄邊界頂點的x坐標減去2倍的緩沖距離，即2D，使得測試點引出的y方向的射線避開地理圍欄邊界的頂點；再進行測試點與邊的判斷：當測試點在邊的緩沖距離內時，直接視為該測試點在地理圍欄之外；隨后判斷射線與地理圍欄每條邊是否只有一個交點，若是，則交點計數加1；通過交點計數的奇偶性判定測試點與地理圍欄的位置關系，判定規則同原始射線法。

改進射線法的具體流程如圖4所示，其中rx和ry分別為測試點r的橫坐標和縱坐標；地理圍欄g={p1,p2,…,pi,…,pn}由p1,p2,…,pn點順時針或逆時針連接而得；s為從點r沿y軸方向引出的一條射線；pix為pi點的橫坐標；pix,D為pi點在經緩沖距離D處理之后的橫坐標。

圖4 改進的射線算法流程圖Fig.4 Improved ray cast algorithm flow chart

圖4與原始射線法不同之處就是圖中灰色部分，不僅解決了射線與非凸地理圍欄邊界頂點相交的問題、測試點在地理圍欄邊上的問題，還解決了射線經過地理圍欄邊界邊的問題。

(2) 判定規則

具體判定規則同原始射線法。

3 仿真與實驗結果分析

3.1 改進射線法假設背景

(1) 為了凸顯可解決的問題，繪制橫向地理圍欄邊界，如圖5所示，黑色實線邊界為禁出型地理圍欄，灰色虛線邊界為禁入型地理圍欄。

(2) 地理圍欄邊界在無人機飛行期間保持不變。

(3) 為了給無人機定義一個可飛空域，地理圍欄包含了垂直方向和水平方向的邊界。

圖5 橫向地理圍欄邊界Fig.5 The horizontal geo-fence boundary

(4) 垂直地理圍欄邊界(高度上限和下限)在地面(AGL)或平均海平面(MSL)以上是恒定的。

(5) 無人機飛行高度恒定，使研究重點集中在橫向地理圍欄越界探測算法上，應注意，該算法在未來的工作中可以進行擴展優化，以消除高度等假設帶來的影響。

(6) 每個地理圍欄邊界都不是自相交的，自相交多邊形如圖6所示。

圖6 自相交的多邊形Fig.6 Self-intersecting polygon

(7) 邊界指定為按順時針或逆時針順序的頂點列表，可以是GPS緯度和經度，也可以是相對位置點。

3.2 基于改進射線法的地理圍欄越界探測算法仿真與分析

為了驗證改進射線法的可行性，在Matlab R2014a的環境下對地理圍欄越界探測算法進行仿真驗證。首先，通過plot()函數將各個頂點逆時針連接起來建立多邊形地理圍欄邊界，隨機生成若干個測試點，然后，分別進行頂點緩沖距離的判斷和邊緩沖距離的判斷，以及射線與邊的交點判斷，執行圖4中算法灰色部分，進而進行與射線交叉的邊的數目的計算，最后判定測試點是否在多邊形內。

實驗分三個步驟進行：

(1) 驗證改進射線法的可行性，并與原始射線法在準確性上作比較分析；

(2) 分析測試點個數對地理圍欄越界探測算法運行時間的影響，并與原始射線法作比較；

(3) 分析地理圍欄邊界的頂點數對基于改進射線法的地理圍欄越界探測算法運行時間的影響。

對實驗結果的分析：

(1) 改進射線法可行性驗證及其與原始射線法在特殊情況下的比較。

為了對改進射線法進行可行性驗證，隨機產生50 000個測試點，仿真結果如圖7所示，將被判定在規定區域外的點標為淺灰色，被判定在規定區域內的點標為深色。

圖7 改進射線法隨機生成50 000個測試點仿真結果Fig.7 Simulation results of 50 000 test points randomly generated by the improved ray cast algorithm

從圖7可以看出：在隨機生成的50 000個測試點中，判定結果基本正確，在地理圍欄邊界附近能看到有個別測試點被判定為淺灰色，這是由于緩沖距離的設置，同時也能起到提前告警的作用，以便無人機及時做出規避動作。表明本文改進的射線法在地理圍欄越界探測中是可行的。

另外，還仿真出原始射線法和改進射線法在其中一特殊情況下的判斷，即當測試點引出的y方向射線與地理圍欄頂點相交。程序設置時仍將射線與邊的交點為奇數的點判定在地理圍欄內，用深色標記；為偶數的點判定在地理圍欄外，用淺灰色標記，均取500個隨機點。原始射線法和改進射線法在類似情況下的仿真結果分別如圖8～圖9所示。

圖8 原始射線法特殊情況下的仿真結果Fig.8 Simulation results of the original ray cast algorithm under special circumstances

圖9 改進射線法特殊情況下的仿真結果Fig.9 Simulation results of the improved ray cast algorithm under special circumstances

從圖8～圖9可以看出：原始射線法在該特殊情況下的判斷全錯，但是改進射線法解決了這一問題。此外，圖7的結果也表明：基于改進射線法的地理圍欄越界探測算法還可以解決測試點在地理圍欄邊界上的問題和射線經過地理圍欄邊界的問題，這都是原始射線法無法解決的。因此，改進射線法的準確性相比原始射線法大幅提高。

(2) 測試點個數對地理圍欄越界探測算法運行時間的影響，并將改進射線法與原始射線法作比較。

為了得到原始射線法和改進射線法的運行時間與測試點個數的關系，設置在圖5所示地理圍欄中測試點隨機產生的個數分別為1、10、50、100、150、200、250、300個，利用tic/toc函數分別計時，各進行100次實驗，結果如圖10(a)所示；分別計算出100次結果的平均值，將8個點連接起來，如圖10(b)所示。

(a) 地理圍欄越界探測算法運行不同測試點數的時間

(b) 地理圍欄越界探測算法運行不同測試點數的時間平均值圖10 地理圍欄越界探測算法運行時間與測試點數的關系Fig.10 The relationship between the running time of the geo-fence violation detection algorithm and the test points

從圖10可以看出：地理圍欄越界探測算法運行時間與測試點個數成正比，測試點越多，算法運行的時間越長。因此地理圍欄越界探測系統需安裝在無人機上，在飛行之前就輸入地理圍欄各個參數，由無人機自行根據其GPS模塊或雷達傳輸的數據進行判斷，這樣每架無人機每個時刻只運行自己的位置點，速度快，能及時反應；相反，如果地理圍欄越界探測由地面設備來運行，一旦同一時刻同一地理圍欄內的無人機過多，算法運行時間就會增長，加之由地面反饋到無人機也需要一定的時間，無法保證實時性。

此外，原始射線法運行時間比改進射線法快，但是將地理圍欄系統應用到機載設備上，每次只進行一個測試點的判斷，改進射線法的運行時間與原始射線法相差不大，對于無人機這樣“低、慢、小”的飛行器，這個差值可以忽略不計。即在保證準確性的前提下，改進射線法的越界探測功能優于原始射線法。

(3)地理圍欄邊界的頂點數對基于改進射線法的地理圍欄越界探測算法運行時間的影響。

因為實驗(1)和實驗(2)已經證明改進射線法優于原始射線法，所以在此不再考慮原始射線法。為了得到基于改進射線法的地理圍欄越界探測算法運行時間與地理圍欄邊界頂點數的關系，設置相同的測試點數1個，一個隨機生成的禁出型地理圍欄，且頂點數分別為3、6、9、12、15、18、21、24個，分別進行100次實驗，結果如圖11(a)所示，計算各頂點數運行時間的平均值，結果如圖11(b)所示。

(a) 地理圍欄越界探測算法不同頂點數的運行時間

(b) 地理圍欄越界探測算法不同頂點數的運行時間平均值圖11 地理圍欄越界探測算法運行時間與邊界頂點數的關系Fig.11 The relationship between running time of geo-fence violation detection algorithm and the number of boundary vertices

從圖11可以看出：基于改進射線法的地理圍欄越界探測算法運行時間與邊界頂點數成正相關，邊界頂點越多，算法運行的時間越長，因為此算法要遍歷每一條邊。之所以不完全成正比例的關系，從編程角度上來說，只有當從測試點引出的y方向射線與地理圍欄其中一條邊相交，才會執行相應的條件語句，如果不相交，就會直接跳過，節省時間，圖11(a)中的時間分布也能印證這點，當地理圍欄頂點數較少時，地理圍欄邊界相對簡單，隨機產生的測試點引出的射線與地理圍欄相交的邊數普遍較少，算法執行時間短，分布集中；當地理圍欄頂點數較多時，邊界相對復雜，隨機產生的測試點引出的射線與地理圍欄相交的邊數有多有少，所以不同點執行算法的時間跨度相對較大。

綜上所述，基于改進射線法的地理圍欄越界探測算法運行時間不僅與地理圍欄邊界頂點數成正相關的關系，還與測試點在地理圍欄中的相對位置有關系，從測試點引出的y方向射線與地理圍欄邊界相交的邊數越多，算法的運行時間越長，相交的邊數越少，運行時間越短。

4 結 論

(1) 基于改進射線法的無人機地理圍欄越界探測算法的運行時間與測試點個數成正比，測試點個數越多，算法運行時間越長。因此應將地理圍欄系統主要應用于機載設備上。

(2) 基于改進射線法的無人機地理圍欄越界探測算法的運行時間與地理圍欄邊界頂點數成正相關的關系，頂點數越多，算法運行時間越長。控制地理圍欄邊界頂點數可以提高無人機地理圍欄越界探測的效率和實時性。

(3) 基于改進射線法的無人機地理圍欄越界探測算法的運行時間與測試點在地理圍欄中的相對位置有關，從測試點引出的y方向射線與地理圍欄邊界相交的邊數越多，算法的運行時間越長。因此對相對于地理圍欄較為復雜的位置，地面人員應加強監督和管控，保證空域內的飛行安全。