談雅婷 呂艷輝 侯英娟

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

關鍵詞 無人機;數(shù)字地圖;路徑規(guī)劃;安全距離

1飛行環(huán)境建模

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

1.1 基準地勢模型建立

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

（1）

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

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

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

（2）

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

2A-Star算法基本原理

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

2.1 代價函數(shù)選取

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

（3）

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

2.2 節(jié)點擴展與路徑點確定

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

路徑規(guī)劃過程表述如下：

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

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

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

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

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

3結束語

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

參考文獻

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

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

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

作者簡介

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