基于改進AWA*算法的智能車輛全局路徑規劃研究

吳麟麟，楊俊輝

(江蘇大學 汽車工程研究院， 江蘇 鎮江 212013)

智能車輛的路徑規劃是指根據某一性能指標搜索一條從起始點到目標點的最優或近似最優的無碰路徑[1]。路徑規劃的傳統方法主要分為兩類[2]：分析法、圖形法。而圖形法又分為路圖法、柵格法等。在搜索算法方面，蟻群算法(GA)[3]、粒子群算法[4]、遺傳算法[5]及其混合算法等眾多主流算法均被運用在路徑規劃中。蟻群算法收斂速度慢，在障礙物包圍情況下易陷入局部最優問題；粒子群算法計算效率偏低且抗噪能力較差；遺傳算法實現比較復雜，同時參數的選擇不夠精確。上述算法均存在計算效率低、編程復雜等實際問題，而A*算法作為啟發式搜索算法的一種，在保留了Dijkstra算法[6]精度高的同時減少了擴展節點數目，具有結構簡單、搜索精度高等優點。但在規劃路徑中A*算法[7]存在擴展節點數目較多，Weighted A*算法存在路徑精度不佳等問題。隨著智能車輛的不斷發展，環境地圖日益龐大且復雜，現有的啟發式算法[8]無法滿足搜索耗時及路徑精度的綜合需求，致使搜索耗時冗長或者路徑規劃精度不佳。針對上述問題，本文在原有Anytime Weighted A*算法(AWA*算法)的基礎上引入動態優化因子，建立一種基于擴展節點耗時的新型動態AWA*算法估價函數，重點對改進的AWA*算法與AWA*算法在路徑規劃效率及規劃路徑的影響進行分析[9]。

1 AWA*算法路徑規劃

全局路徑規劃主要分為2個步驟：首先是建立障礙物及自由空間區域的環境地圖，其次是在環境地圖中選擇合適的搜索算法。

1.1 環境建模

根據不同的表示形式，環境地圖表示方法主要分為度量地圖表示法、拓撲地圖表示法和混合地圖表示法。

本研究主要運用的是度量地圖表示法中的空間分解法。假設智能車輛的自由空間為矩形，其內部分布著多個靜止障礙物，對任務區域進行柵格化，得到如圖1的環境模型，其中：設定起點為紅色節點，終點為藍色節點，障礙物為黑色節點。

圖1 環境模型

1.2 AWA*算法的基本原理

AWA*算法是在A*算法的基礎上發展起來的。A*算法在它的每個道路節點均設計了一個估價函數：

k(s)=g(s)+h(s)

(1)

而AWA*算法區別于A*算法的是其初次搜索時，在估價函數的基礎上引入了權值系數K：

k(s)=g(s)+K·h(s)

(2)

在討論A*算法及AWA*算法的標準術語中，g(s)表示從初始節點到任意節點s的真實代價消耗，K為啟發函數的權值系數，h(s)表示從節點s到目標點的啟發式評估代價消耗。g(s)是可知的：

A*算法一定能搜索到最優路徑的前提條件：

h(s)≤cost*(s,sgoal)

(4)

考慮到浮點數處理較慢的因素，柵格節點間采用的連接關系是無浮點數計算的四連接。為了保證搜索路徑的最優性，采用以當前節點s到目標點goal的曼哈頓距離作為啟發式函數：

h(s)=|xs-xgoal|+|ys-ygoal|

(5)

在節點s的擴展子節點中，由于各個子節點g值相同，所以子節點越靠近終點G(goal)，該子節點到終點的曼哈頓距離越小，則 f 值就越小。以此引導搜索的方向，使得智能車輛逐步靠近目標。

AWA*算法用OPEN表與CLOSED表2個集合來管理道路節點。OPEN表存放待擴展的道路子節點，CLOSED表存放擴展過的子節點。所有節點創建時僅已知特性值(X,Y)，其Cost特性值均設為0。

AnytimeWeightedA*算法(算法1)是在WeightedA*算法[10]的基礎上，通過改變其終止條件來改善路徑精度。算法1的具體框架參考文獻[10]。

算法1的核心思想是在限定的搜索時間下，基于WeightedA*算法條件進行搜索，當AWA*算法的OPEN表為空時，那么算法結束，沒有搜索到可行路徑；當AWA*算法搜索到了不大于最優路徑K倍的可行路徑 f(inc)時，如果時間仍有剩余，那么算法會將當前的路徑長度 f (inc)保存，同時對已經擴展的節點繼續搜索，但該搜索滿足的條件相對于之前WeightedA*算法做了相應的改變，后續擴展的節點除了要滿足k(s)值最小之外，其f(s)值必須要小于f(inc)值，這樣，之后得到的路徑均對原始可行路徑進行了優化。AWA*算法終止條件為：OPEN表為空，或者時間結束，算法終止。

2 優化AWA*算法路徑規劃

WeightedA*算法[10]基于A*算法的擴展特點，引入了權值系數K，通過擴大啟發函數使其擴展節點數目減少，加快搜索速度。但由于啟發函數的過分增大，最優子節點選取不充分，導致路徑精度折損過多。AnytimeWeightedA*算法在WeightedA*算法的基礎上加入了終止條件，使AWA*算法可在時間充裕的條件下繼續搜索更優路徑。但AWA*算法如若初次搜索到最優路徑，仍會繼續搜索，擴展多余無用節點。綜上所述，本文基于WeightedA*算法的估價函數，在AnytimeWeightedA*算法的啟發下引入了動態優化因子，提出了一種新型動態估價函數。根據搜索過程中當前耗時T與當前擴展節點數目的線性關系，通過獲取當前搜索耗時參數T，時刻更新啟發函數的權值系數，保證AWA*算法在初次搜索路徑時便可找到較優路徑，進而可在限定時間內找到最優路徑。

2.1 優化AWA*算法的流程步驟

優化AWA*算法大體分為3個階段：

開始階段：將起始節點放入OPEN表中，同時初始化所有變量。

擴展階段：判斷是否找到初始路徑，是則繼續搜索，但是新增條件為當前搜索的路徑 f 值要小于初始路徑inc的 f 值；否則選取OPEN表中最小k值節點，放入CLOSED表中。同時擴展該節點，判斷其4個子節點是否在OPEN表中，計算這些子節點的k值及 f 值后，放入或更新OPEN表；

動態優化階段：根據AWA*算法每次擴展子節點后均檢查最優子節點的機制，獲取當前搜索耗時，更新動態優化因子ε*值。

優化AWA*算法框架如算法2所示，其中：OPEN表示A*算法中存放待擴展的節點集合；CLOSED表示存放擴展過的節點集合。sstart為起始柵格節點；sgoal為目標柵格節點；s′是s的擴展子節點；K為啟發函數的權值系數；inc為找到目標點的節點集合；g(s)表示從起始節點sstart到當前節點s的真實代價值；c(s,s′)為節點s到s′節點的距離值；k(s)為本文公式中當前節點s的估價函數值； f(s)是當前節點的估價長度； f(inc)表示第1次找到的從起始節點到目標節點的可行路徑長度；h(s′)為當前子節點s′的啟發函數值；ε*表示動態優化因子；T1表示限定的搜索時間；P1表示開始時記錄的計算機時間截點；P2表示擴展當前子節點后的計算機時間截點；T為當前搜索消耗的時間；α表示觸發搜索極限時間比率；B表示搜索極限速度常數。

算法2 優化Anytime Weighted A*算法

2.2 優化AWA*算法的具體思路

本文在AWA*算法的初次搜索中估價函數中引入動態優化因子ε*，根據A*算法循環擴展子節點的特點來不斷變化啟發函數的權值系數Kε*，以保證初始路徑時可快速地選擇較優的路徑，同時可進一步在限定時間內尋找更優路徑。

優化AWA*算法的估價函數如下：

河南省戰略性新興產業發明專利數量不多、質量不高的現實狀況，反映出河南省自主創新能力不足。這些問題的形成，既與河南省經濟發展、科技創新、人才培養等方面的歷史欠賬有關，又與新時期河南省知識產權戰略實施不徹底、知識產權布局不科學、知識產權潛力挖掘不充分等有關。具體來說，主要有以下幾個方面的問題。

k(s)=g(s)+Kε*×h(s)

(6)

本文定義了動態優化因子ε*，其具體計算公式如下：

式中： K為初始權值系數；T1為限定搜索時間(ms)； T為獲取的當前搜索耗時(ms)； B為搜索極限速度常數； α為觸發搜索極限時間比率。

加入了搜索耗時T1后，ε*值在開始時每次擴展子節點后均會增大，同時優化AWA*算法的估價函數也會相應改變，減少了可選擇節點數目，保證了搜索效率。隨著搜索耗時T的不斷增大，當T大于或等于αT1時，此時距離目標節點較近，通過使ε*變為常數B，來確保搜索路徑精度。

又由式(7)可知：

K

(8)

由式(4)(8)可證得：

(9)

推導結果證明了優化AWA*算法初次規劃出的路徑要小于KB倍的最優路徑，以此保證了優化AWA*算法路徑的次優性。

3 仿真實驗及結果分析

本文針對路徑規劃搜索耗時問題，對AWA*算法及優化AWA*算法進行了路徑規劃耗時誤差仿真實驗，驗證了優化AWA*算法在不同單一環境地圖下，仿真平臺具有一定穩定性，搜索耗時誤差具有一定局限性，實驗數據具有一定可靠性。同時，本文進行了低百分比障礙物環境地圖路徑規劃普適性仿真實驗，對比分析了優化AWA*算法與傳統AWA*算法的耗時情況和路徑精度。為進一步驗證優化AWA*算法的普適性，本文進行了高百分比障礙物的環境地圖路徑規劃普適性仿真實驗，并對仿真實驗總體上進行了系統性地分析。2種算法均在VitualStudio2013上實現，仿真實驗采用的計算機CPU型號為Intel酷睿i5 3230M，主頻均為2.6GHz，RAM為4GB。在2種仿真實驗中，優化AWA*算法均采用相同的參數，且該參數均由實際需要自行設定，如表1所示。

表1 優化AWA*算法主要參數

3.1 路徑規劃耗時誤差仿真實驗

本文為研究每次搜索耗時的誤差特性，對2種算法分別進行了單一地圖在10%～50%障礙物百分比下的100次重復規劃仿真實驗，并以20%障礙物下的單一環境地圖為例，其結果如圖2所示。

仿真實驗結果顯示：在環境地圖障礙物百分比為20%時，AWA*算法每次搜索耗時之間的誤差值為32ms，優化AWA*算法搜索耗時誤差分別為16ms。同理，在10%、30%、40%、50%障礙物的環境地圖中，AWA*算法與優化AWA*算法搜索耗時誤差也均保持在32ms以內，說明2種算法在各個環境地圖中的耗時誤差均具有一定局限性，且重復規劃的路徑結果均一致，驗證了2種算法路徑結果重復規劃的一致性和仿真平臺數據結果的可靠性。

3.2 算法普適性仿真實驗分析

3.2.1低百分比障礙物環境地圖的普適性仿真實驗

為分析優化AWA*算法在特定障礙物百分比但不同環境地圖下的各項性能，本文分別在障礙物百分比為10%、20%、30%、40%、50%下，均隨機生成100種環境地圖。路徑規劃后的搜索耗時仿真實驗結果如圖3～7所示。

仿真實驗結果顯示：優化AWA*算法與AWA*算法相比，在障礙物為10%、20%、30%、40%、50%下的環境地圖中搜索耗時分別下降了69.3%、73.5%、49.8%、21.4%、19.9%，擴展節點數目減少了55%、62%、43%、22%、12%，路徑平均長度分別減少了0.47%、1.3%、1.2%、1.7%、0。綜上可知，在10%～50%障礙物環境地圖下，優化AWA*算法的各項指標均優于AWA*算法。此仿真實驗驗證了優化AWA*算法在保證路徑次優性的同時仍具有搜索耗時少的優勢。

通過對比圖3(c)、圖4(c)、圖5(c)、圖6(c)、圖7(c)，發現隨著環境地圖障礙物百分比逐步增大，優化AWA*算法相比于AWA*算法的搜索耗時優勢逐步減少這一現象。為此，本文通過進一步地仿真實驗來驗證此發現。

3.2.2高百分比障礙物環境地圖的普適性仿真實驗

由于障礙物百分比為90%時，自由空間不足以生成起點到達終點的可行駛路徑，故隨機生成路徑的障礙物百分比最高設定為80%。本文針對優化AWA*算法相比于AWA*算法，在高百分比障礙物環境地圖下的搜索耗時優勢減少的問題，設定60%、80%百分比障礙物，分別隨機生成100種環境地圖，仿真實驗結果見圖8、9。

仿真實驗結果顯示：優化AWA*算法與AWA*算法相比，在60%、80%障礙物下的環境地圖中，搜索耗時分別下降了3.27%、4.56%，路徑精度分別下降了0.1%、0。此仿真實驗結果與上述發現的環境地圖障礙物百分比逐步增大，優化AWA*算法相比于AWA*算法的搜索耗時優勢逐步減少的現象一致。

圖2 20%障礙物地圖下的路徑規劃

圖3 10%障礙物地圖下的路徑規劃

圖4 20%障礙物地圖下的路徑規劃

圖5 30%障礙物地圖下的路徑規劃

圖6 40%障礙物地圖下的路徑規劃

圖7 50%障礙物地圖下的路徑規劃

圖8 60%障礙物地圖下的路徑規劃

圖9 80%障礙物地圖下的路徑規劃

本文對此現象的原因進行了合理推斷：

耗時大小的具體體現是OPEN表中存放的待擴展節點數目。在低百分比障礙物的環境地圖中，障礙物數量少，自由空間相對多。在未搜索到初始路徑時，由于優化AWA*算法相比于A*算法啟發函數值偏大，故在OPEN表中添入可選擇的待擴展子節點數目偏少，導致擴展節點過程中計算k值的次數少，規劃路徑時間更短。

而隨著環境地圖障礙物逐步增多，自由空間相對逐步減小。在擴展子節點時，AWA*算法OPEN表中添入可選擇的待擴展節點被動減少，導致優化AWA*算法相比于AWA*算法擴展數目的差距逐步減小，故優化AWA*算法在搜索耗時方面的優勢逐步減少，直至持平。

4 結束語

本文提出了一種基于AWA*算法的新型估價函數。在原有AWA*算法估價函數基礎上，引入了動態優化因子ε*，建立了新型的估價函數，根據AWA*算法流程中循環擴展節點的特點不斷更新啟發函數的權值系數Kε*，加快路徑規劃最優性收斂，改善智能車輛路徑規劃在限定時間下路徑精度不佳問題。

在全局工況下，優化AWA*算法相比于AWA*算法，在保證路徑次優性的同時降低了搜索路徑耗時，尤其是在低障礙物百分比地圖下，效果更為明顯。

當環境地圖障礙物百分比逐步增大時，優化AWA*算法相比于AWA*算法的搜索耗時優勢逐步減小，最后兩者搜索耗時基本一致。