繩紅強，黃海英，崔毅剛

（1.中國重汽集團濟南動力有限公司，濟南 250101；2.武漢大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，武漢 430072；3.山東圣翰財貿(mào)職業(yè)學(xué)院，濟南 250316）

0 引言

智能車輛是一個集環(huán)境感知、規(guī)劃決策和軌跡跟蹤控制等功能于一體的綜合系統(tǒng)。隨著新一代人工智能技術(shù)的快速發(fā)展，智能車輛已成為未來汽車產(chǎn)業(yè)的重要發(fā)展方向。避障路徑規(guī)劃是智能車輛領(lǐng)域的關(guān)鍵技術(shù)之一，是當(dāng)前國內(nèi)外學(xué)者研究的熱點[1-5]。

智能車輛避障路徑規(guī)劃一般是指在障礙物環(huán)境中，滿足路徑平滑度最高、距離最短、能耗最小等約束條件下，從車輛起始點到目標點規(guī)劃出一條無碰撞路徑。路徑規(guī)劃算法主要有人工場勢法[6]、概率路圖法（PRM）[7]、快速隨機拓展樹法（RRT）[8]、幾何曲線插值法[9]、D*算法[10]、A*算法[11]、蟻群算法[12-16]、粒子群算法[17]等。智能車輛安全行駛對路徑規(guī)劃算法效率、路徑平滑性提出了較高的要求，而每種路徑規(guī)劃算法適用領(lǐng)域不同，導(dǎo)致單算法結(jié)構(gòu)不具有泛化求解能力，往往針對具體問題需要進行優(yōu)化整合。蟻群算法是由意大利學(xué)者M Dorigo等[14]于1996年提出，它源于模擬蟻群覓食行為完成尋路過程，通過殘留信息素計算路徑節(jié)點選擇概率，最終得到優(yōu)化的規(guī)劃路徑。蟻群算法魯棒性強，易于與其他優(yōu)化算法相結(jié)合，實際應(yīng)用中存在規(guī)劃路徑不光滑、路徑曲折和收斂速度慢的問題[18-20]。

針對上述蟻群算法存在的缺陷，本文通過對蟻群算法啟發(fā)函數(shù)和信息素更新策略改進，提出一種適用于智能車輛的基于A*蟻群融合算法的避障路徑規(guī)劃方法。該方法不僅融合A*算法估價值和轉(zhuǎn)彎拐角約束條件，構(gòu)造了一種增強型啟發(fā)函數(shù)，還設(shè)計改進了信息素濃度增量模型。仿真結(jié)果表明，本文算法在改善規(guī)劃路徑平滑度和算法性能方面效果明顯。

1 蟻群算法

由于蟻群算法原理在M Dorigo等人的著作已有詳盡的描述，在此不做贅述。蟻群算法的核心是利用狀態(tài)轉(zhuǎn)移概率和信息素更新策略實現(xiàn)路徑選擇。

1.1 狀態(tài)轉(zhuǎn)移概率

迭代過程中，螞蟻m（m=1，2，3，…，M）在t時刻從當(dāng)前節(jié)點i轉(zhuǎn)移到下一節(jié)點j的狀態(tài)轉(zhuǎn)移概率由路徑上的信息素濃度和兩點間的距離啟發(fā)函數(shù)確定。狀態(tài)轉(zhuǎn)移概率表達式如下：

蟻群算法啟發(fā)函數(shù)ηij(t)表達式為：

式中：di j為節(jié)點i和j之間的距離，即：

1.2 信息素更新策略

當(dāng)所有螞蟻完成一次迭代后，需對路徑信息素進行更新，其更新公式為：

式中：τij(t)為t時刻節(jié)點i到下一節(jié)點j路徑之間的信息素濃度；τij(t-1)為在t-1時刻節(jié)點i到下一節(jié)點j路徑之間的信息素濃度；ρ為信息素揮發(fā)系數(shù)，ρ∈(0,1)；Δτij為M只螞蟻完成一次迭代，邊（i，j）上累積殘留的信息素濃度；為第m只螞蟻完成一次循環(huán)邊（i，j）上殘留的信息素濃度。

M Dorigo等人提出3種不同的信息素濃度增量模型，分別稱之為Ant-Density System（ADS）、Ant-Quantity System（AQS）和Ant-Cycle System（ACS）模型。

若第m只螞蟻當(dāng)前循環(huán)經(jīng)過邊（i，j）的集合為，則 信息 素濃 度 增量模型函數(shù)表示如下。

ADS模型：

式中：Q為信息素強度，影響算法求解速度，為大于零的常數(shù)；Lm為第m只螞蟻在本次循環(huán)中所經(jīng)過路徑的總長度。

上述ACS模型采用的是全局更新策略，螞蟻完成一個循環(huán)后再更新殘留信息素的濃度，在求解路徑規(guī)劃問題中最為常用，因此本文采用該模型作為信息素更新的基本模型。

2 改進蟻群算法

由于蟻群算法啟發(fā)函數(shù)ηis(t)=1/d ij僅利用相鄰節(jié)點的信息，全局啟發(fā)性不足，易出現(xiàn)規(guī)劃路徑拐角多、盲目搜索和收斂速度慢問題。下面從啟發(fā)函數(shù)和信息素更新策略兩方面對算法進行改進。

2.1 構(gòu)造基于A＊算法的啟發(fā)函數(shù)

A*算法是一種啟發(fā)式搜索算法，其核心是利用估價函數(shù)在狀態(tài)空間中從起始點開始對每一個搜索位置進行評估，按照評價準則（如路徑最短或消耗最小等指標）選取最優(yōu)的位置，再從這個位置進行搜索直到目標位置。以最短路徑作為搜索評價指標，A*算法估價函數(shù)的可表達式為：

式中：n為起始節(jié)點相鄰的節(jié)點；F（n）為節(jié)點n的估價函數(shù)；G（n）為在狀態(tài)空間中從初始節(jié)點s到節(jié)點n的最短距離；H（n）為從節(jié)點n到目標節(jié)點g的最短距離；nx為節(jié)點n的橫坐標；ny為節(jié)點n的縱坐標；sx為起始節(jié)點的橫坐標；sy為起始節(jié)點s的縱坐標；gx為目標節(jié)點的橫坐標；gy為目標節(jié)點g的縱坐標。

引入A*算法估計代價F（n）和拐角懲罰函數(shù)f(θij)作為蟻群算法啟發(fā)函數(shù)的啟發(fā)因子，改進后的蟻群算法啟發(fā)函數(shù)表達式如下：

式中：t為目標節(jié)點g影響路徑選擇的權(quán)重；θij為從節(jié)點i經(jīng)過相鄰節(jié)點j轉(zhuǎn)過的角度；f(θij)為節(jié)點i與節(jié)點j之間的拐角懲罰函數(shù)；C為懲罰函數(shù)系數(shù)，為一常量。

2.2 改進信息素濃度增量模型

利用螞蟻當(dāng)前路徑、最優(yōu)路徑和最差路徑，以及將當(dāng)前迭代路徑累積拐角懲罰函數(shù)，優(yōu)化信息素濃度增量模型。優(yōu)化后的信息素濃度增量模型表達式如下：

式中：Q*為信息度濃度的強度值；n為當(dāng)前迭代次數(shù)；Ln,m為當(dāng)前路徑長度，即第m只螞蟻產(chǎn)生的路徑的長度；Lmin為最優(yōu)路徑長度，即第n次迭代產(chǎn)生的最短路徑長度；Lmax為最差路徑長度，即第n次迭代產(chǎn)生的最長路徑長度；為當(dāng)前迭代最短路徑上各點拐角的累積懲罰值；δ為路徑偏離值，δ=Lmax-L n,m，即最差路徑的長度與當(dāng)前路徑長度之間的差值；ε為第n次迭代路徑允許誤差。

在迭代過程中，新的信息素增量機制可以自適應(yīng)動態(tài)調(diào)整信息素的強度，使優(yōu)化過程加速向全局最優(yōu)路徑收斂。當(dāng)δ＞ε時，Lmax與Ln,m差值越大，信息素強度越大，全局收斂時間縮短，算法求解效率得到提升；當(dāng)δ≤ε時，L n,m與Lmin越接近，信息素濃度蒸發(fā)越快，使算法避免出現(xiàn)過早收斂陷入局部最優(yōu)。引入，保證迭代過程中拐角最小路徑上的信息素濃度得到加強，利于改善路徑平滑性。

2.3 改進算法步驟

本文提出的基于A*蟻群融合算法的避障路徑規(guī)劃方法算法步驟如下。

（1）創(chuàng)建柵格地圖環(huán)境。選擇起始點和目標點。

（2）初始化參數(shù)：螞蟻規(guī)模M，最大迭代次數(shù)N，信息啟發(fā)式因子α，期望啟發(fā)式因子β，信息素揮發(fā)系數(shù)ρ等。設(shè)定初始迭代次數(shù)n=1（n=1，2，3，…，N），初始螞蟻編號m=1（m=1，2，3，…，M），并把起始點S置入禁忌表Tabu。

（3）路徑選擇。訪問um查找當(dāng)前節(jié)點前往下一步可行節(jié)點，按式（1）和（8）分別計算下一步可行節(jié)點的概率，然后，按輪盤法選擇下一節(jié)點。將選定的下一節(jié)點作為新的起始點即當(dāng)前節(jié)點，更新禁忌表Tabu。

（4）螞蟻序號更新。若第m只螞蟻的當(dāng)前節(jié)點列表包含了目標點或無路徑且m≥M，則轉(zhuǎn)入步驟5；否則，m=m+1，返回步驟3。

（5）信息素更新。計算當(dāng)前迭代最優(yōu)路徑并按式（3）和（9）更新信息素濃度。

（6）迭代或停止。若n≥N，則輸出最優(yōu)路徑并停止迭代；否則，n=n+1，釋放禁忌表Tab u，返回步驟3。

3 仿真分析

3.1 仿真環(huán)境地圖模型

本文采用柵格法構(gòu)建工作空間地圖模型，柵格法是將智能車輛行駛的空間分解成N×N具有二值信息的網(wǎng)格單元。下面以10×10柵格地圖為例，簡要說明柵格地圖模型表示方法，如圖1所示。

圖1 柵格地圖

圖1中黑色占有的柵格表示障礙物，白色占有的柵格是可行柵格。按從左到右，從上到下的順序，依次為柵格進行編號，柵格中心的坐標為直角坐標，則柵格地圖中的任意一點的坐標（xi，yi）與柵格編號i的映射關(guān)系如式（10）和式（11）所示：

式中：a為柵格邊長；N×N為柵格編號數(shù)值最大的值；mod(a,b)為（a/b）取余結(jié)果；ceil函數(shù)為朝正無窮大方向取整。

被控對象在某一個柵格內(nèi)可到達的柵格有與其相鄰的上、右、下、左、右上、右下、左下、左上8個方向上的柵格，如圖2所示。

圖2 八個可行方向

3.2 仿真結(jié)果分析

為了驗證改進蟻群算法的有效性，本文通過仿真程序，在3種復(fù)雜障礙物環(huán)境柵格地圖（20×20）下，對基本蟻群算法和本文改進蟻群算法進行了仿真對比分析。仿真試驗參數(shù)設(shè)置如表1所示。仿真結(jié)果如圖3～5和表2所示。

表1 仿真實驗參數(shù)設(shè)置

圖3是在地圖1環(huán)境下仿真結(jié)果，是基本蟻群算法和本文提出的改進蟻群融算法的避障路徑規(guī)劃圖和迭代收斂曲線。如表2所示，本文改進蟻群算法較基本蟻群算法迭代收斂速率提高了54.55%，最優(yōu)路徑減少了38.04%，拐點數(shù)減少了57.69%，路徑平滑度即拐角之和提高了78.85%。

圖3 基于地圖1環(huán)境下兩種算法最短路徑規(guī)劃圖和迭代收斂變化曲線

圖4是在地圖2環(huán)境下仿真結(jié)果，如表2所示，本文改進蟻群算法較基本蟻群算法迭代收斂速率提高了40%，最優(yōu)路徑減少了42.75%，拐點數(shù)減少了50%，路徑平滑度即拐角之和提高了75%。

圖4 基于地圖2環(huán)境下兩種算法最短路徑規(guī)劃圖和迭代收斂變化曲線

圖5是在地圖3環(huán)境下仿真結(jié)果，如表2所示，本文改進蟻群算法較基本蟻群算法迭代收斂速率提高了45.41%，最優(yōu)路徑減少了38.49%，拐點數(shù)減少了44%，路徑平滑度即拐角之和提高了72%。

圖5 基于地圖3環(huán)境下兩種算法路徑規(guī)劃圖和迭代收斂變化曲線

表2 仿真實驗結(jié)果

綜合上述3種地圖環(huán)境下兩種算法的仿真結(jié)果，本文改進的蟻群算法即A*蟻群融合算法較基本蟻群算法環(huán)境適應(yīng)能力強，迭代收斂速率平均提高了41.67%，最優(yōu)路徑減少了39.76%，拐點數(shù)減少了50.56%，路徑平滑度即拐角之和提高了75.28%。

4 結(jié)束語

基本蟻群算法在智能車輛避障路徑規(guī)劃中存在拐角多、收斂速度慢、泛化求解能力差等問題，本文通過對基本蟻群算法改進，提出一種基于A*蟻群融合算法的智能車輛避障路徑規(guī)劃方法，仿真結(jié)果顯示改進效果良好。特別是在算法收斂速度、最優(yōu)路徑和路徑平滑度等方面改進效果明顯。引入A*算法估價因子和路徑拐角懲罰因子，構(gòu)造的增強型啟發(fā)函數(shù)在引導(dǎo)螞蟻對引導(dǎo)目標節(jié)點的感知、消除路徑搜索的盲目性和提高路徑平滑度方面作用明顯；提出的基于拐角懲罰因子的自適應(yīng)信息素濃度增量模型，可以動態(tài)調(diào)整信息素濃度的強度使算法快速向轉(zhuǎn)角最小的最優(yōu)路徑收斂。