A-Star算法在無人機(jī)路徑規(guī)劃中的研究

談雅婷 呂艷輝 侯英娟

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

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

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

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

1.1 基準(zhǔn)地勢模型建立

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

（1）

為三維數(shù)字地形上某點(diǎn)在水平面的投影坐標(biāo)，為對應(yīng)的地形高程值，到是常系數(shù)負(fù)責(zé)控制基準(zhǔn)地形的起伏狀態(tài)。

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

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

（2）

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

2A-Star算法基本原理

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

2.1 代價函數(shù)選取

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

（3）

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

2.2 節(jié)點(diǎn)擴(kuò)展與路徑點(diǎn)確定

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

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

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

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

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

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

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

3結(jié)束語

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

參考文獻(xiàn)

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

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

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

作者簡介

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