[發明專利]基于自適應A星算法的飛行器最優路徑確定方法

無效

• 申請號: 201410010003.3
• 申請日: 2014-01-09
• 公開（公告）號: CN103697895A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 于昕;焦李成;朱振強;馬晶晶;馬文萍;劉軍強;李陽陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

技術領域

本發明屬于空間數據處理技術領域，特別涉及飛行器的路徑規劃，該方法可用于開展智能導航、無人駕駛等領域的路徑規劃。

背景技術

飛行器是依靠地形信息和敵情信息來進行路徑規劃，即在一定約束條件下，飛行器從起始點到終止點，搜尋能優先滿足特定目的最優的飛行路徑，其中飛行路徑用一系列航路點表示。

隨著軍事技術、實際戰爭需求的不斷發展，飛行器的路徑規劃建模從單一的系統發展到復雜多變的系統。飛行器的路徑規劃問題呈現出實時性、多維性、不確定性和非線性等復雜特征。建立在傳統系統下的模型，仍習慣于從障礙物地形信息已知且不會改變的角度出發，以靜態、理想化為主的方式來研究飛行器路徑規劃的建模問題，忽視了從實際的角度來看待整個飛行過程。目前大多數路徑規劃方法對于復雜的貼近真實環境的障礙物地形場景效果較差。這是因為傳統算法采用的是簡單的靜態的規劃方法，即在實際飛行器在飛行之前根據障礙物地形場景來進行路徑規劃，在飛行過程中路徑不可改變以及障礙物符合特定規律，這與真實場景的差距較大。顯然這種規劃方法將障礙物地形場景進行了理想化的處理，而實際上飛行場景的地形信息是無規律無規則的。

目前主要有三類技術解決路徑規劃問題：1.傳統算法，如柵格法，Voronoi圖法；2.智能優化算法，如遺傳算法；3.其他算法，如動態規劃算法。

傳統算法是根據經典的數學方程式進行計算，較一般地理想的障礙物地圖用此類算法計算出的路徑在全局上較優，但對障礙物的要求較為理想化，針對實際地形地圖的規劃效果很大程度受到算法本身和障礙物理想化程度的影響。智能優化算法，如遺傳算法是在1975年由John?Holland提出，是一類借鑒生物界的進化規律，即利用適者生存、優勝劣汰遺傳機制演化而來的隨機化搜索方法，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱并行性和更好的全局尋優能力；采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。在魯棒性上較傳統算法有了明顯的提高，對障礙物理想化的依賴程度減低，但智能優化算法的計算時間普遍過長，無法適應動態的，可變的更接近真實情景的地圖進行路徑規劃。對于其他算法，如動態規劃算法，由于算法自身限制，在局部路徑上可以達到最優以及適應動態地圖，但在全局規劃上無法保證，可能會出現路徑結果不穩定和計算不出總體路徑的情況。

發明內容

本發明的目的在于針對已有技術的不足，提出一種基于自適應A星算法的飛行器最優路徑確定方法，以提高對多種不同地圖規劃出的路徑的正確度，同時提高對同一幅地圖進行多次路徑規劃的路線的穩定性，增強對不同地圖路徑規劃的魯棒性。

本發明的技術思路是：將所需的各類數據進行預處理，獲得起止點和障礙物區域坐標，由起止點坐標差值比例，計算縱坐標方向網格尺寸大小，通過傳統A星算法得出其路徑規劃的路徑，并把搜索方向發生改變時的第一個航路點作為新的起始點，重新定義網格尺寸大小，用A星算法進行搜索，當滿足終止點條件時，路徑規劃結束，輸出所有的有效航路點。其具體步驟包括如下：

（1）在地圖中設置飛行器的起始點SP和終止點EP；

（2）生成障礙物區域：

2a）根據飛行器的起始點SP和終止點EP的位置，建立直角坐標系；

2b)設p_i，q_i分別為飛行器需繞過的每一個障礙物的起點和終點的坐標，對p_i點分別做垂直于直角坐標系X軸和Y軸的直線，對q_i點分別做垂直于直角坐標系X軸和Y軸的直線，用這四條直線圍成的一個矩形，表示障礙物區域T_i，其中i為障礙物的個數；

（3）將障礙物區域進行網格劃分，得到網格地圖；

（4）在網格地圖中，設飛行器的起始點SP所在的網格為SG、終止點EP所在的網格為EG；

（5）根據飛行器的起始點所在網格SG和終止點所在網格EG，進行路徑規劃：