基于A*蟻群融合算法的避障路徑規劃研究*

繩紅強，黃海英，崔毅剛

（1.中國重汽集團濟南動力有限公司，濟南 250101；2.武漢大學數學與統計學院，武漢 430072；3.山東圣翰財貿職業學院，濟南 250316）

0 引言

智能車輛是一個集環境感知、規劃決策和軌跡跟蹤控制等功能于一體的綜合系統。隨著新一代人工智能技術的快速發展，智能車輛已成為未來汽車產業的重要發展方向。避障路徑規劃是智能車輛領域的關鍵技術之一，是當前國內外學者研究的熱點[1-5]。

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

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

1 蟻群算法

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

1.1 狀態轉移概率

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

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

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

1.2 信息素更新策略

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

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

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

若第m只螞蟻當前循環經過邊（i，j）的集合為，則 信息 素濃 度 增量模型函數表示如下。

ADS模型：

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

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

2 改進蟻群算法

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

2.1 構造基于A＊算法的啟發函數

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

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

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

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

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

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

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

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

2.3 改進算法步驟

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

（1）創建柵格地圖環境。選擇起始點和目標點。

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

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

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

（5）信息素更新。計算當前迭代最優路徑并按式（3）和（9）更新信息素濃度。

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

3 仿真分析

3.1 仿真環境地圖模型

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

圖1 柵格地圖

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

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

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

圖2 八個可行方向

3.2 仿真結果分析

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

表1 仿真實驗參數設置

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

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

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

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

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

圖5 基于地圖3環境下兩種算法路徑規劃圖和迭代收斂變化曲線

表2 仿真實驗結果

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

4 結束語

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