(沈陽理工大學(xué) 遼寧 沈陽 110159)

一、引言

路徑規(guī)劃問題成為機(jī)器人領(lǐng)域中一個重要的研究課題。研究者提出了多種算法，如Dijkstra 算法，蟻群算法，模擬退火算法、粒子群算法等。這些算法沒有將實際工作中的機(jī)器人與算法緊密的結(jié)合起來。

二、路徑規(guī)劃問題描述

機(jī)器人路徑規(guī)劃問題是指在工作區(qū)域中,機(jī)器人通過已知的環(huán)境信息或者對周圍環(huán)境進(jìn)行感知,按照預(yù)先設(shè)計的代價函數(shù)，通過一系列的算法，從起點開始找到一條代價最小的到終點的運(yùn)動路徑,該路徑能避開工作空間中的障礙物。

根據(jù)機(jī)器人對環(huán)境信息的掌握程度可以分為全局規(guī)劃方法,局部規(guī)劃方法以及混合規(guī)劃方法三種。

(1)全局規(guī)劃方法必須知道整個環(huán)境地圖中障礙物分布的大體情況。該方法可以找到最佳路徑，但是考慮全局信息導(dǎo)致計算量大，效率低，不適用于未知環(huán)境或動態(tài)環(huán)境。

(2)局部規(guī)劃方法中依靠機(jī)器人當(dāng)前得到的局部環(huán)境信息,根據(jù)制定的規(guī)則來實現(xiàn)避障導(dǎo)航,該方法可以滿足實時性要求，缺點是易陷入局部極值點,機(jī)器人可能在中途停止，無法到達(dá)目標(biāo)點。

(3)混合型方法結(jié)合了全局規(guī)劃和局部規(guī)劃,具有良好的實用性。

三、基于改進(jìn)的A*算法的路徑規(guī)劃

(一)A*算法原理

A*算法基于啟發(fā)式搜索結(jié)構(gòu)，它是 Dijkstra 算法的擴(kuò)展，通過評估擴(kuò)展節(jié)點的代價值，并比較其大小加以選擇，使得在起點與終點之間尋找到一條代價最小的路徑。廣度優(yōu)先(BFS)和深度優(yōu)先(DFS)是簡單的狀態(tài)空間搜索策略。BFS方法的原理是從初始節(jié)點逐層向下查找，將當(dāng)前節(jié)點按照可拓展的策略一層一層展開，直到找到目標(biāo)節(jié)點。該方法能找到最優(yōu)路徑，但節(jié)點展開的數(shù)量是和距離成級數(shù)增加的，不適用于大規(guī)模復(fù)雜的環(huán)境，效率低。DFS方法的原理是按照一定的順序先查找完一個分支，再查找另一個分支，直到找到目標(biāo)節(jié)點。

A*算法與BFS和DFS不同，就在于選擇下一步節(jié)點時，通過估值函數(shù)對節(jié)點進(jìn)行評估，通過排序并選擇代價最小的節(jié)點作為下一步搜索節(jié)點進(jìn)行拓展，如果存在一個以上代價最小的節(jié)點，選擇距離當(dāng)前節(jié)點最近的一個節(jié)點，該方法避免了搜索的盲目性，提高了算法的搜索效率。估值函數(shù)如公式(1)所示。

f(n)=g(n)+h(n)

(1)

其中，f(n)為節(jié)點n的估值函數(shù)，g(n)表示從初始節(jié)點到當(dāng)前節(jié)點n的實際代價，h(n)表示從節(jié)點n行進(jìn)到目標(biāo)節(jié)點的估算代價。

估價函數(shù)h(n)的選取決定了是否能找到最優(yōu)路徑，如果估價值h(n)的小于或等于當(dāng)前節(jié)點 n 到目標(biāo)節(jié)點的真實代價，將導(dǎo)致搜索范圍大，算法效率低，但能得到最優(yōu)路徑。如果估價值大于實際代價，算法的搜索范圍小，效率高，但不一定能找到最優(yōu)路徑。

A*算法 與廣度優(yōu)先和深度優(yōu)先的聯(lián)系在于，當(dāng)g(n)=0時，改算法雷石榆DFS，當(dāng)h(n)=0時，該算法類似于BFS；如果實際代價函數(shù) g(n)遠(yuǎn)大于估算代價函數(shù) h(n)，則啟發(fā)式函數(shù) h(n)沒有作用，A*算法退化成了 Dijkstra 算法。

本文中，將起始節(jié)點與當(dāng)前節(jié)點之間的距離作為實際代價函數(shù)，估計代價函數(shù) h(n)的采用曼哈頓方法。估計代價函數(shù)如公式(2)所示。

h(n)=|nx-px|+|ny-py|

(2)

其中，nx、ny為當(dāng)前節(jié)點的橫、縱坐標(biāo)，px、py為目標(biāo)節(jié)點橫、縱坐標(biāo)。

(二)改進(jìn)的A*算法

在 A*算法中，若搜索方向為 8 方向搜索，則路徑中存在的轉(zhuǎn)彎方向角只有 45°。因為轉(zhuǎn)向存在時間，機(jī)器人路徑規(guī)劃整個系統(tǒng)中的最短路徑不僅僅式路徑的長度。改進(jìn)的策略是在原有的 A*算法評價函數(shù)上加一項t(n)表示轉(zhuǎn)向過程所需要的時間，根據(jù)新的評價函數(shù)判斷路徑中的單位柵格代價。改進(jìn) A*算法的評價函數(shù)如式(3)所示。

f(n)=g(n)+h(n)+t(n)

(3)

改進(jìn) A*算法的評價函數(shù)之后，在原有的評價函數(shù)中增加了新的約束條件，即機(jī)器人自身特性所限制的運(yùn)動轉(zhuǎn)向時間。整個路徑的評價因素不再僅是距離的長短，而是整個系統(tǒng)運(yùn)行的時間。

得到規(guī)劃后初始路徑為F，遍歷F內(nèi)的所有節(jié)點，當(dāng)兩個節(jié)點之間的連線中沒有障礙物節(jié)點時，將連線中的節(jié)點設(shè)置為空結(jié)點，最終刪除集合 F內(nèi)的所有空節(jié)點，將非空節(jié)點依次連接得到最終的路徑。

(三)改進(jìn)的A*算法流程

A*算法需要維護(hù)開表和閉表。開表存放拓展節(jié)點的可通行的相鄰節(jié)點，閉表存放已訪問過的節(jié)點。選擇開表中總代價 f 最小的那個節(jié)點作為拓展節(jié)點，不斷的向周圍拓展。算法的具體流程如下：

(1)初始化開表和閉表，將起始節(jié)點添加到開表中。

(2)將開表中f 最小的節(jié)點作為拓展節(jié)點。

(3)按照如下方式處理該節(jié)點相鄰的8個方向的每個節(jié)點。①若該鄰節(jié)點為障礙物，或者在閉表中存在，則不進(jìn)行任何操作。②若開表中沒有該鄰節(jié)點，就將其加入到開表中，并計算出該節(jié)點的實際代價 g 和估計代價 h。③若開表中已經(jīng)有了該相鄰節(jié)點，則比較當(dāng)前節(jié)點到達(dá)該相鄰節(jié)點的估計代價 h 與原來的估計代價 h 之間的大小。如果當(dāng)前節(jié)點的估計代價 h 小的話，那么設(shè)置當(dāng)前節(jié)點為該相鄰節(jié)點的父節(jié)點；否則，不進(jìn)行任何操作。

(4)將當(dāng)前節(jié)點從開表中刪除，加入到閉表中。

(5)判斷開表是否為空以及閉表中是否包含有目標(biāo)結(jié)點。如果開表不為空并且閉表中不包含目標(biāo)結(jié)點，則返回到步驟(2)；如果開表不為空且閉表中包含有目標(biāo)結(jié)點，執(zhí)行步驟(6)；如果開表為空，停止搜索。

(6)從目標(biāo)結(jié)點沿著父節(jié)點遍歷到起始節(jié)點，得到初始規(guī)劃路徑F。

(7)遍歷初始路徑F內(nèi)的所有節(jié)點，若某個兩個節(jié)點之間沒有障礙物節(jié)點時，將中間節(jié)點置為空結(jié)點。

(8)將 F 中的所有空節(jié)點刪除，依次連接剩余節(jié)點，得到最終的路徑 Q。

四、實驗結(jié)果及分析

本文提出的改進(jìn)的 A*算法，對A*算法的評價函數(shù)改進(jìn)，考慮了轉(zhuǎn)向時間對整體路徑規(guī)劃的影響，并對規(guī)劃后的路徑進(jìn)行了平滑處理，與傳統(tǒng) A*算法相比，采用改進(jìn)的 A*算法規(guī)劃出的路徑長度和路徑的轉(zhuǎn)折角度有所減小，使得規(guī)劃出的路徑更優(yōu)。