一種基于改進a*算法的無人機航線規劃算法
【專利摘要】本發明涉及一種無人機在大范圍復雜三維空間的航線規劃算法，包括以下步驟，首先基于2.5維網格(每個網格點包含經度、緯度、高程信息)劃分三維空間；然后在雷達、災害天氣、禁飛區等約束條件下，綜合考慮航線高度、被探測概率、航線長度等影響因子改進A*代價函數，基于算法搜索流程，確定初始航線；最后為了滿足無人機性能約束(包括最小步長、轉彎半徑、爬升率、安全高度等)，進行一系列處理得到最終的可飛行航線。本發明涉及算法穩定、收斂性好、效率高、可滿足大范圍低空航線規劃要求，可運用于軍事國防、應急救災等相關領域之中。
【專利說明】—種基于改進A*算法的無人機航線規劃算法
【技術領域】
[0001]本發明具體涉及一種算法，特別是一種用于無人機在大范圍復雜三維空間的航線規劃算法。
【背景技術】
[0002]現代軍事低空突防主要由無人機完成，為了提高無人機低空突防生存概率和作戰效能，需要利用地形的遮蔽作用，在敵防御系統盲區內低空或超低空飛行。其中，關鍵問題是無人機的航線規劃。對于該問題的研究已有多年的歷史，有很多研究成果。一些學者試圖在人工智能等相關領域尋找智能優化算法，但它們解決大范圍無人機路徑搜索問題都有一些常見的弊病。A*算法在二維圖形搜索領域的成熟運用使得它解決該問題具有先天的優勢，但目前成果存在以下問題:(I)目標空間為小范圍人造簡單地形圖，障礙物少且規則，未考慮雷達、惡劣天氣等復雜威脅體。無法體現算法在復雜環境中的適應性、收斂性及效率問題。(2) —些學者使用平面區域劃分(Voronoi圖等)的方法，這類空間劃分是基于一定高度的，因此本質上依然是在二維空間中進行路徑規劃。但山區地形實時截面運算的計算量太大，而且無人機基于一定高度上飛行的理論前提不成立。(3)不考慮無人機的機動性能約束，不是可飛航線。
【發明內容】
[0003]本發明目的在于提供一種表用于無人機在大范圍復雜三維空間的航線規劃算法，所涉及算法可滿足大范圍低空航線規劃要求。
[0004]本發明采用的技術方案如下:
[0005]首先將三維連續空間使用離散二維空間表示，即規劃空間表示為一定經差和緯差離散網格的網絡圖，并且為每個節點賦予當地地形的高程信息；然后在雷達、災害天氣、禁飛區等約束條件下，改進A*代價函數使航線高度、被探測概率、航線長度三項指標同方向作用關系，并進行歸一化處理，在此基礎上使用算法搜索流程，確定初始航線；在無人機最小步長、轉彎半徑、爬升率、安全高度約束下，建立航線保護區模型，進行一系列處理得到最終的可飛行航線，最后檢驗算法的穩定性和收斂性以及效率。
[0006]本發明與現有技術相比具有以下優點:
[0007]基于2.5維網格模型，每個節點的鄰域僅僅存在8個可擴展方向，算法計算效率要遠大于3維網格劃分方式；在雷達、災害天氣、禁飛區等約束條件下，將航線高度、被探測概率、航線長度進行歸一化處理，改進了 A*算法；在無人機最小步長、轉彎半徑、爬升率、安全高度約束下，優化了航線。本發明涉及算法穩定、收斂性好、效率高、可滿足大范圍低空航線規劃要求。
【具體實施方式】
[0008]以下以航線規劃算法流程對本發明作進一步的詳細說明，但本發明的保護范圍并不局限于此。
[0009]I目標空間劃分
[0010]A*算法是一種啟發式搜索算法，需要一個由點和邊組成的網絡空間，在此目標空間中引入啟發信息，由定義好的代價函數確定節點拓展的規則，最終得到兩點之間的最優路徑。但基于DEM和DOM的三維環境本質上是一個連續狀態的柵格空間，并不存在傳統二維路徑搜索中的路由網，從而無法利用路徑搜索算法尋找最短路徑中的節點和邊，必須對其進行空間劃分。
[0011]一些研究嘗試使用規則三維網格的空間劃分方法。該方法的最大問題在于每個節點的可擴展方向在僅僅考慮鄰域的情況下也有26個，要收斂到最優解會耗費大量的時間和內存資源，且隨規劃空間增大呈指數級增長。因此本發明提出如圖1所示的2.5維網格模型，每個網格點包含經度、緯度、高程信息。此時每個節點的鄰域僅僅存在8個可擴展方向，算法計算效率要遠大于3維網格劃分方式。
[0012]2基于A*算法的初始航線確定
[0013]2.1代價函數改進
[0014]對于以上劃分的目標網絡空間，需要定義A*算法的代價函數對可拓展節點進行評估，從而挑選出最優路徑中的節點-邊列表。A*代價函數一般公式如下:
[0015]f (n) = g (n) +h (η)(I)
[0016]其中η是待擴展節點，g(n)是狀態空間中從初始節點到節點η的實際代價，h(n)是從節點η到目標節點的估計代價。A*算法本身的性質決定了代價函數的表達式是影響搜索性能的主要因素。對于無人機低空航線規劃問題，Asseo S.J給出了對代價函數的參考公式，如下所示:
【權利要求】
1.一種無人機航線規劃算法，其特征在于:包括以下步驟:首先基于2.5維網格劃分三維空間；然后在雷達、災害天氣、禁飛區等約束條件下，綜合考慮航線高度、被探測概率、航線長度等影響因子改進A*代價函數，基于算法搜索流程，確定初始航線；最后在最小步長、轉彎半徑、爬升率、安全高度約束下，進行一系列處理得到最終的可飛行航線；該算法穩定、收斂性好、效率高。
2.根據權利要求1所述一種無人機航線規劃算法，其特征在于:所述2.5維網格為2.5維網格模型，每個網格點包含經度、緯度、高程信息，其每個網格點的鄰域存在8個可擴展方向。
3.根據權利要求1所述一種無人機航線規劃算法，其特征在于:基于2.5維網格劃分三維空間，其每個網格點的鄰域存在8個可擴展方向遠小于規則三維網格的空間劃分中每個網格點的鄰域存在26個可擴展方向。
4.根據權利要求1所述一種無人機航線規劃算法，其特征在于:A*代價函數中g(H)首先改進為
，使代價函數的航線高度、被探測概率、航線長度三項指標是同方向的作用關系。
5.根據權利要求1所述一種無人機航線規劃算法，其特征在于:A*代價函數中(進行歸一化處理，進一步改進為
6.根據權利要求 1 所述一種無人機航線規劃算法，其特征在于:A*代價函數中
7.根據權利要求1所述一種無人機航線規劃算法，其特征在于:算法搜索基于2.5維空間劃分和改進Α*代價函數。
8.根據權利要求1所述一種無人機航線規劃算法，其特征在于:在最小步長、轉彎半徑約束下采用FFP算法對航線數據進行數據壓縮，使無人機能夠找出盡可能最長的直線趨勢，從而避免頻繁的轉彎。
9.根據權利要求1所述一種無人機航線規劃算法，其特征在于:在爬升率、安全高度約束下，建立航線保護區模型，計算得到優化后的轉折點，構成航線。
10.根據權利要求1所述一種無人機航線規劃算法，其特征在于:該算法穩定、收斂性好為算法在不同距離、不同網格大小的情況下均可以并且快速的計算出一條最優航線。
【文檔編號】G01C21/20GK104075717SQ201410025640
【公開日】2014年10月1日 申請日期:2014年1月21日 優先權日:2014年1月21日
【發明者】王偉, 江華, 王鵬, 占偉偉 申請人:武漢吉嘉偉業科技發展有限公司
專業數控銑床產品供應商
20年生產經驗，實力工廠，精工品質，質量有保障
