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

談雅婷 呂艷輝 侯英娟

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

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

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

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

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

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

（1）

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

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

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

（2）

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

2A-Star算法基本原理

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

2.1 代價(jià)函數(shù)選取

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

（3）

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

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

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

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

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

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

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

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

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

3結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

作者簡(jiǎn)介

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