空中機器人路徑規劃算法研究

林文

（長沙航空職業技術學院，湖南長沙 410014）

1 引言

空中機器人的發展至今已有70多年歷史，已經取得豐碩的研究成果。特別是其典型組成部分無人機技術已經在諸多領域取得了成功應用。當前，空中機器人在軍事領域和民用領域都已經發揮了越來越重要的作用。

在軍事方面，空中機器人既能夠執行殺傷性任務，又能夠執行非殺傷性任務。已經從擔負單純的空中偵察、靶機擴展到情報監視、指揮和控制、火力制導、導彈導航、充當誘餌、電子戰、通信中繼、邊境巡邏、戰場評估甚至戰斗等任務。目前，固定翼空中機器人已經在為軍隊服務，在幾次局部戰爭和反恐戰爭中由于其體積小、成本低、隱蔽性強無、機動靈活、無人員傷亡且戰場生存能力強等特點都發揮了重要作用，取得了良好的軍事效益，具有巨大的應用前景。當前的世界局勢決定了未來戰爭將是高技術條件下的局部戰爭，在這種形式下空中機器人也將有更廣闊的應用空間。

在民用方面，隨著科技的發展，各種微小型的空中機器人憑借采購和使用費用低、使用方式靈活等優點，已經可以替代有人機完成搜救救援、空中巡邏、交通監控、資源勘探、災情監測、電力巡線、森林防火、對地觀測、農藥噴灑等任務，具有光明的應用前景和市場效益。

隨著空中機器人在軍事領域中的作用逐漸增大，我國對于空中機器人的研究也越來越多，越來越深入，也取得了一定的研究成果。路徑規劃是空中機器人的主要技術之一，也成為了很多科研人員的研究方向。本文從軍事角度出發，從戰場威脅方面來對空中機器人的路徑規劃進行研究。

2 戰場環境的Voronoi圖構建

2.1 Voronoi圖定義

Voronoi圖又稱為泰森多邊形或者Dirichlet圖。Voronoi圖是對平面n個離散點而言的，它把平面分為幾個區，每一個區包括一個點，該點所在的區是到該點距離最近點的集合。設P是一離散點集合P1，P2，…Pn∈P，定義Pi的Voronoi區域V（Pi）為所有到Pi距離最小點的集合：V（Pi）={P/d（P，Pi）≤d（P，Pj），j≠i，j=1，2，…n}

假設P是一離散點集合，P1，P2，…Pn∈P，定義P的Voronoi圖V（P）為：V（P）={V（P1）,V（P2）,…,V（Pn）}，其中Pi稱為V圖生成元。

2.2 Voronoi圖的特性

（1）vor（s）把平面劃分為n個多邊形域，每個多邊形域V（pi）包含且只包含S的一個點pi。

（2）vor（s）的邊是S中某對點的中垂線的一個線段或者射線。

（3）V（pi）是無界的，當且僅當pi屬于凸包外界的點集。（4）Voronoi圖之多有2*n-5個頂點和3*n-6條邊。

（5）每個Voronoi點恰好是三條Voronoi邊的交點（假設任何四點都不共圓的話）。也就是說Voronoi點就是形成三邊的三點的外界圓圓心，而且所有的這些外界圓都有個特點：各自內部不含任何S點集的點（空心圓）。

從上面的Voronoi圖特性可以看出，Voronoi圖的邊是能夠最好地規避對應的兩個威脅的線段，因此，選擇Voronoi圖來構造整個戰場，不但可以把路徑規劃的空間進行簡化，而且很大程度上提高了工作效率。

2.3 Voronoi圖的構造

目前，對于Voronoi圖的構造已經有了很成熟的算法，不過，根據算法計算出來的Voronoi圖的頂點沒有包含空中機器人的起始位置和目標位置，要對起始位置和目標位置之間的最佳路徑進行規劃，就必須把這兩個位置添加到Voronoi圖中。具體的方法是將空中機器人的起始位置作為Voronoi圖的一個頂點，然后將這個頂點與Voronoi圖中與之最近的3個點連接起來，對于目標位置也進行相應操作，從而計算出最短路徑的Voronoi圖。

3 路徑段的代價計算

由于在構造Voronoi圖時，是把所有的威脅的中心位置當成母點。然而，在實際的戰場上，所有的威脅都是有一定作用范圍的，因此，要在戰場上對空中機器人進行路徑規劃，就必須要模擬戰場的真實環境。本文從禁飛區、火力威脅和雷達探測威脅三個方面來進行路徑規劃研究。

3.1 禁飛區和威脅的處理

禁飛區、火力威脅和雷達探測威脅都是對空中機器人飛行障礙。具體來說，可以分為兩類威脅，一類是軟殺傷威脅，一類是硬殺傷威脅。軟殺傷威脅包括火力威脅和雷達探測威脅，當空中機器人進入這類區域，可能會被殺傷或者被探測到，但是如果成功穿越了這類威脅的作用區域，就有不被損毀的概率；硬殺傷威脅則是主要指禁飛區，禁飛區是由于政治因素或者物理因素限定不允許飛行的區域，空中機器人一旦穿越，就會被損毀。在對空中機器人進行路徑規劃時，必須對軟殺傷威脅和硬殺傷威脅進行計算，軟殺傷威脅的相關計算信息包括威脅的中心位置，作用半徑和殺傷概率，硬殺傷威脅的計算信息包括禁飛區的中心位置和半徑。對空中機器人進行路徑規劃時，對每個Voronoi圖的邊的代價估計應該要對每個威脅進行相應處理。

3.2 代價計算

在Voronoi圖構造完成之后，圖中的邊是最后規劃路徑的組成，稱為路徑段。要進行路徑規劃，就必須要對每個路徑段進行代價計算，代價計算主要有兩個方面，一個是威脅接近代價，一個是燃料代價。這兩個代價的加權和就是這個路徑段總代價。具體公式如下：

其中，Ji是路徑段的總代價，Jit是威脅接近代價，Jif是燃油代價，k是加權系數，范圍在0-1之間。在計算路徑段總代價的時候，需要根據任務的安全要求和燃油要求，對k的值進行相應調整。根據路徑段總代價的計算方法，對Voronoi圖中的每條邊進行代價計算，然后就對最優路徑進行計算。

4 最優路徑生成

4.1 初始路徑生成

根據上面的步驟完成Voronoi圖中每條邊的代價和之后，再把各條邊的代價值的有向圖G計算出來，G=（V，A，W），V是Voronoi頂點的集合，A是頂點之間Voronoi邊的集合，W表示邊的代價值，其中，V（v1，v2，v3·······vn），n是頂點的個數。利用有解有向圖的Dijstra最短路徑法來進行計算，從而得出指定節點之間的最短路徑，進而得出空中機器人的起始位置和目標位置之間的初始路徑。

4.2 路徑修正

Dijstra算法只是能夠計算出最短路徑，也就是Voronoi圖中的最佳路徑，然而，這是否符合空中機器人的是實際情況，是否適應空中機器人的實際飛行需求，還需要進一步的修正。具體來說，需要從以下幾個方面來進行修正：第一，是否能夠進一步縮短空中機器人的飛行距離；第二，在Voronoi圖中的兩條邊，其夾角是不是滿足空中機器人飛行的最小轉彎半徑，如果不能滿足，就必須要進行相應修正；第三，如果空中機器人的初始航向角與路徑規劃時的起始航向角之間差異太大，也需要進行修正。

4.2.1 縮短距離的處理

從Voronoi圖的定義和特點來看，Voronoi圖的邊會最大程度地避免母點，因此，Voronoi圖是在戰場進行空中機器人路徑規劃的最佳方案。然而，在實際的戰場上面，空中機器人只需要避免威脅，而不需要圍著每個威脅來走折線。因此，在進行路經修正時，可以通過直線化來縮短飛行距離。

具體方法如下：假設初始路徑中的各個點分別是（xs，ys）（x1，y1）（x2，y2）（x3，y3）···（xi，yi）···（xn，yn）（xt，yt）。其中，（xs，ys）為起始位置，（xt，yt）是目標位置，在整條路徑上，總共有n個節點數?？s短路徑的步驟就是把當前點當作目標點，從當前點出發依次向之前的點進行連線，如果連線穿越了威脅，記錄這個點之前的那個點當作當前點，把這個當前點與上一個當前點之間的節點刪除。然后重復這些步驟，重新從這個當前點出發，再繼續往前連線，直到到達初始點位置。

4.2.2 路徑中的拐角的平滑處理

在Voronoi圖中的兩條邊，如果夾角太過尖銳，就會讓空中機器人無法正常轉彎，因此，需要對太過尖銳的夾角進行平滑處理。進行平滑處理就是在尖銳的拐角處加一個圓弧，這個圓弧的半徑通常都是選擇空中機器人的最小轉彎半徑，從而，可以讓空中機器人順利轉彎。

4.2.3 初始航向角處理

如果空中機器人的初始航向角與路徑規劃時的起始航向角之間差異太大，需要對航向角進行相應修正。對航向角進行修正，首先需要沿著與當前位置相連的圓弧進行飛行，然后轉入第二個圓弧，第二個圓弧是與第一個圓弧光滑連接的，然后并接入第一段路徑，第一段圓弧與空中機器人航向光滑銜接。這兩個圓弧的連接點，就是路徑上面空中機器人當前狀態到達期望路徑的轉節點。需要注意的是，兩個圓弧之間的半徑應該要大于等于空中機器人的最小轉彎半徑，從而保證空中機器人能夠順利轉彎。這樣，就可以在路徑出發點不變的情況下，只需要進行少量調整，就可以改變空中機器人的飛行航向角。

通過縮短距離的處理、路徑中的拐角的平滑處理和初始航向角處理，就可以得出空中機器人的最優路徑，這也是在已經給定威脅分布的戰場環境下，空中機器人的飛行最優路徑。

5 結論

本文對已經明確威脅分布的戰場環境下，空中機器人的飛行最優路徑進行了研究。在已經明確威脅分布的戰場環境中，通過Voronoi圖構建避免威脅的初始路徑段，然后根據這些威脅的具體情況，計算出待選路徑段的代價值，再利用Dijstra算法計算出初始路徑，最后再進行縮短距離的處理、路徑中的拐角的平滑處理和初始航向角處理，從而得出空中機器人的飛行最優路徑。

[1]丁希侖；俞玉樹.一種多旋翼多功能空中機器人及其腿式壁面行走運動規劃[J].航空學報，2010，56(10)：175-186.

[2]張銀玲;牛小梅.蟻群算法在移動機器人路徑規劃中的仿真研究[J].計算機仿真，2011，28(06)：237-240.

[3]鄔再新;李艷宏;劉濤.多移動機器人路徑規劃技術的研究現狀與展望 [J].機械，2008，47(01)：6-8+21.