A-Star算法在無人機路徑規劃中的研究

談雅婷 呂艷輝 侯英娟

摘 要 無人機消費市場飛速上升，而無人機的技術研究中，路徑規劃是重要的組成部分，對周圍環境建立數字地圖，依據數字地圖，通過A-Star算法進行路徑規劃，針對無人機飛行任務，尋找一條最短路徑。A-Star算法將 Dijkstra 算法和BFS算法搜索策略融合，既擁有啟發式算法快速搜索路徑的優點，同時還能保證找到一條最短路徑，但對于無人機飛行需要一定的安全距離，因此對A-Star算法進行相應改進可以很好地解決規劃路徑距離障礙物很近的情況。

關鍵詞 無人機;數字地圖;路徑規劃;安全距離

1飛行環境建模

無人機路徑規劃過程中，對威脅回避和地形分別考慮，這樣會使路徑規劃算法獲取環境信息時間比較長，導致整個規劃過程復雜，因此，采用將無人機飛行前環境已知地形及相應威脅信息融合，簡化路徑規劃算法，減少數字地圖[1]存儲空間。

1.1 基準地勢模型建立

無人機路徑規劃問題需結合無人機飛行的真實地理環境，在路徑規劃之前，首先需要對飛行環境建模。構建環境模型時主要考慮山體地貌信息、基準地形信息。本文采取構建基準地形的方式如（1）所示。

（1）

為三維數字地形上某點在水平面的投影坐標，為對應的地形高程值，到是常系數負責控制基準地形的起伏狀態。

1.2 模擬山地建模及威脅建模

通過信息融合的方式構建模型，用山地模型代表障礙和威脅。在無人機執行任務時，將環境中的障礙及威脅信息進行快速建模，融合到數字地圖中，便于無人機進行實時的在線路徑規劃策略，及時規劃出可行路徑。構建山地模型的數學表達式如（2）所示。

（2）

為數字地圖中點處的高程值，n控制山峰的個數，控制高度，為第m個山峰的中心坐標。對公式中相關變量賦值不同，可得到不同高度，數目的模擬山地模型。

2A-Star算法基本原理

A-Star算法是經典的路徑規劃算法之一，A-Star算法繼承Dijkstra 算法的貪心性質，同時繼承了最佳優先搜索策略的啟發式性質，將兩者結合，通過啟發式函數選擇代價值最小的節點作為下一節點，從而能夠是其規劃處一條從起點到終點最短的路徑，同時具有較少的運算量。

2.1 代價函數選取

代價函數的設計在A-Star算法中起著決定性作用，節點代價計算過高或過低都會影響節點擴展時丟失本來為最優路徑上的節點。A-Star的代價函數[2]通用表達式如（3）所示。

（3）

式中為起點與當前點m的代價值，為當前點m與終點的估算代價。為了計算和，需要確定起點與終點之間的距離，常見的距離算法有曼哈頓距離、對角線距離和歐幾里得距離。本文研究中，將無人機視為質點，可以在其八鄰域范圍內搜索路徑，所以采用歐幾里得距離作為距離計算方法。

2.2 節點擴展與路徑點確定

A-Star算法的整個規劃過程可總結為：從起始點，檢查八鄰域范圍內節點代價，不斷尋找代價值最小的節點，向終點方向擴展直到達到終點。

路徑規劃過程表述如下：

（1）定義開啟集，關閉集，起始節點為0，將起始點放入開啟集，搜索領域節點，計算代價放入開啟集。

（2）開啟集中刪除起點，將起點加入關閉集，在開啟集中尋找代價值最小的函數，放入關閉集中，將最小代價節點作為當前節點，繼續擴展節點，計算其鄰域內節點代價。

（3）擴展當前節點，計算鄰域內的所有可行節點，并且去掉關閉集中存放的節點，當開啟集中沒有終點時，跳轉到第二步，繼續搜索節點，否則，進行下一步。

（4）從終點開始回溯，通過追溯父節點指針，確定路徑節點，將節點反序輸出即為最終路徑。

傳統A-Star算法僅考慮了選擇最優路徑進行路徑規劃，但在無人機實際飛行過程中，無人機自身有一定體積，并且無人機容易受到天氣因素影響，在小范圍內漂移，所以為了確保無人機更安全的飛行，本文提出增加代價函數的方法，對障礙物一定范圍內設置代價函數。改進 A-Star算法的評價函數之后，在原有的評價函數中增加了新的約束條件，即無人機與建筑物邊緣的距離。整個路徑的評價因素不再僅僅是距離的長短，而是無人機防止與建筑物擦碰最優的路徑[3]。

3結束語

本文首先通過對無人機飛行環境進行建模，其次分析傳統的A-Star路徑規劃算法，根據無人機自身體積及飛行特點，對傳統算法進行增加代價函數設計，使A-Star算法從僅考慮最短路徑到將路徑長短為影響整個系統的關鍵因素，規劃路徑時也考慮到與障礙物之間的安全距離，從而確保規劃出一條安全的飛行路徑。

參考文獻

[1]田疆.基于固定翼無人機的航跡規劃優化模型[J].西北民族大學學報（自然科學版），2017，38（1）：7-10.

[2] 譚寶成，王培.A-Star路徑規劃算法的改進及實現[J].西安工業大學學報，2012，32（4）：325-329.

[3] 姚雨，李慶，陳曦.優化的A-Star算法在航跡規劃上的應用[J].微電子學與計算機，2017，34（7）：51-55.

作者簡介

談雅婷（1995-），女，甘肅蘭州人;學歷：碩士研究生，現就職單位：沈陽理工大學，研究方向：圖像處理與分析技術。