基于改進蟻群算法的自動駕駛路徑規劃研究

繩紅強，黃海英，石小銳，崔毅剛

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

0 引言

路徑規劃是自動駕駛車輛運動控制的關鍵技術，通常被描述為自動駕駛車輛在空間環境約束下尋找一條從起始點通往目標點的最優無碰撞路徑[1]。自動駕駛車輛又稱為輪式移動機器人，其路徑規劃算法的研究源自機器人技術。迄今為止，國內外學者提出了諸多經典的路徑規劃算法[2-4]，如蟻群算法、Dijastra算法、A*算法、粒子群算法、快速探索隨機樹算法(RRT)、人工勢場法、禁忌搜索算法、神經網絡法、動態窗口算法等。目前大多數算法針對具體問題需要進行優化整合，自動駕駛車輛安全行駛要求延時必須控制在毫秒甚至微秒級別，對算法效率、規劃路徑質量提出了較高的要求。

蟻群算法由意大利學者DORIGO M等于1996年首先提出[5]，它源于對螞蟻群體覓食機制的研究。蟻群算法具有自組織、分布式、正反饋、魯棒性強等優點，易于與其他優化算法相結合，已經廣泛用于求解車輛路徑規劃、機器人路徑規劃、無人機飛行路徑規劃等問題[6-13]。但是，蟻群算法理論模型缺乏堅實的數學基礎，其關鍵參數的選擇多依靠試驗和經驗來確定，易出現路徑拐點多、轉彎角度大、收斂速度慢、局部收斂、搜索停滯等典型問題[14]。

針對蟻群算法的不足，本文提出一種適用于自動駕駛路徑規劃的改進蟻群算法，以提高規劃路徑的質量和算法性能，對實現自動駕駛車輛安全行駛具有重要價值。

1 蟻群算法的基本模型

由于蟻群算法原理在DORIGO M等的著作已有詳盡的描述，在此不做贅述。下面簡要說明蟻群算法的基本數學模型和實現過程的關鍵步驟。蟻群算法的核心是利用狀態轉移概率和遺留的信息素濃度實現路徑選擇。

1.1 狀態轉移概率

定義螞蟻在t時刻由節點i轉移至節點j的狀態轉移概率為

(1)

啟發函數ηij(t)表達式為

ηij(t)=1/dij

(2)

式中dij為節點i和j的距離，即

1.2 信息素更新規則

當M只螞蟻完成一次循環后，需對路徑信息素更新，其更新公式為

τij(t)=(1-ρ)·τij(t-1)+Δτij

(3)

(4)

式中：τij(t)為t時刻節點i到相鄰節點j的路徑之間信息素濃度；τij(t-1)為在t-1時刻節點i到相鄰節點j的路徑之間信息素濃度；ρ為信息素揮發系數,ρ∈(0,1)；Δτij為在t-1時刻到t時刻節點i到相鄰節點j的路徑之間信息素濃度的增量。

1.3 信息素增量更新模型

根據信息素濃度的增量更新方式的不同，DORIGO M等提出3種不同的基本更新模型，分別稱之為Ant-Density System(ADS)、Ant-Quantity System (AQS)和Ant-Cycle System (ACS)模型。

若第m只螞蟻當前循環經過路徑(i,j)節點的集合為X{(i,j)|i=1,2,…,n;j=1,2,…,n}，則：

ADS模型：

(5)

AQS模型：

(6)

ACS模型：

(7)

式中：Q為信息素強度，影響算法求解速度，為>0的常數；Lm為第m只螞蟻在本次循環中所走路徑的總距離。

上述3個模型的差別：ADS模型和AQS模型采用的是局部更新策略，即螞蟻每走一步都要更新殘留信息素的濃度；ACS模型采用的是全局更新策略，即螞蟻完成一個循環后再更新殘留信息素的濃度，在求解路徑規劃問題中最為常用，因此ACS模型通常作為信息素更新的基本模型。

2 蟻群算法設計改進

2.1 全局啟發函數設計

式(2)中啟發函數ηij(t)僅利用了相鄰節點的信息，啟發性不足，缺乏全局性，易出現規劃路徑拐點多、角度大、盲目搜索、收斂速度慢[14-15]等問題。本文利用相鄰節點和目標點的信息引入貝塞耳平滑曲線函數，構造了一種全局啟發函數。

n+1個頂點的n次貝塞耳曲線表達式為

(8)

式中：Pi(i=0,1,2,…,n)為各頂點的位置向量；Bi,n(t)為伯恩斯坦基函數。

(9)

令ηij(t)=P(t),P0=1/dij和P1=1/djE，按貝塞耳曲線函數一階展開，即取n=1，則

全局啟發函數ηij(t)表達式為

(10)

t的大小取決于車速、相鄰節點之間的距離。當車輛均速行駛時，t≈dij/(dij+djE)。當djE?dij時，t→0，則全局啟發函數ηij(t)表達式可近似為

(11)

2.2 信息素更新策略

本文提出利用螞蟻當前路徑、最優路徑、最差路徑和理想路徑，構建一種動態調整的信息素增量模型。該信息素增量模型表達式如下：

(12)

式中：n為第n次迭代；Ln,m為當前路徑距離，即第m只螞蟻產生的路徑的距離；Lmin為最優路徑距離，即第n次迭代產生的最短路徑距離；Lmax為最差路徑距離，即第n次迭代產生的最長路徑距離；Lidv為理想路徑距離，即起始點與目標點的直線距離；δ為最優路徑距離與最差路徑的差值，即δ=Lmax-Ln,m；ε為第n次迭代可接受路徑誤差，ε值為一常數。

在迭代過程中,新的信息素增量機制可以自適應動態調整信息素的強度，使優化過程加速向全局最優路徑收斂。當δ>ε時，Lmax與Ln,m差值越大，信息素強度越大，全局收斂時間縮短，算法求解效率得到提升；當δ≤ε時，Ln,m與Lmin越接近，信息素濃度蒸發越快，使算法避免出現過早收斂陷入局部最優。Lidv在迭代過程中起到參照作用，可作為最佳路徑決策依據。

2.3 算法過程

根據上述理論，按照本文提出的全局啟發函數和信息素更新策略，自動駕駛車輛路徑規劃算法流程如圖1所示，步驟如下所述。

圖1 本文算法流程圖

步驟1：獲取環境地圖數據。定位起始點S和目標點E；獲取空間所有節點信息，計算鄰接矩陣D和計算啟發式信息矩陣。

步驟2：參數初始化。初始化迭代次數N，螞蟻規模M，信息啟發式因子α，期望啟發式因子β，信息素揮發系數ρ，信息素濃度ε、t，當前路徑列表RT，禁忌表TS。將起始點S置于禁忌表RT和當前路徑列表TS。

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

步驟5：信息素更新。計算當前迭代最優路徑并按式(3)和式(12)更新信息素矩陣。

步驟6：迭代或停止。若n≥N，則輸出最優路徑并停止迭代，否則返回步驟3。

3 仿真實驗與分析

3.1 仿真環境搭建

經典的環境地圖建模方法有柵格法、幾何法、可視圖法等[16-17]。

柵格法是將自動駕駛車輛行駛的空間分解成一系列具有二值信息的網格單元。柵格法表達簡單，易于實現，在路徑規劃中最為常用。

下面以10×10二維柵格地圖為例，簡要說明柵格地圖數學模型和表示形式，如圖2所示。

圖2 10×10二維柵格地圖

圖2中黑色柵格表示障礙物，白色柵格是自由柵格。設每個柵格的中心坐標為柵格的直角坐標，每個柵格編號與直角坐標一一對應，則柵格地圖中任意一點的坐標(xi,yi)與柵格編號i的映射關系如下所示。

xi=a·[mod(i,MM)-0.5]

(13)

yi=a·[MM+0.5-ceil(i/MM)]

(14)

式中：a為每個柵格邊長；MM為橫坐標的最大柵格數值；mod(a,b)為(a/b)取余結果；ceil函數為朝正無窮大方向取整。

在柵格地圖中，在當前節點i位置路徑決策可選方向有“十”字型或“米”字型[18]。本文采用“米”字型方向選擇規則，如圖3所示。

圖3 可行路徑方向圖

3.2 結果與分析

通過仿真程序，下面對本文算法的有效性在柵格地圖環境下進行試驗驗證。仿真環境如圖4所示的20×20二維柵格地圖。

仿真試驗參數設置詳見表1，仿真試驗結果如圖4、圖5和表2所示。

表1 仿真實驗參數設置

圖4 算法路徑規劃圖

圖5 算法收斂變化曲線

表2 仿真實驗結果

由圖4可見，本文改進算法可以實現自動駕駛車輛在復雜的障礙環境中尋找到一條從起始節點出發到達目標點的無碰撞最優路徑。

由圖5和表2結果顯示，本文算法迭代8次達到收斂，規劃路徑距離為31.799，明顯優于基本算法。本文算法全路徑拐點有19個，拐角之和為900°，其中45°拐角18次、90°拐角1次；而基本算法的拐點數為27次，拐角之和為2 170°，其中直角拐角有21次，45°拐角6次，顯然本文算法規劃路徑更平滑。

4 結語

本文提出一種用于自動駕駛路徑規劃的改進蟻群算法。仿真實驗結果表明：本文構造的全局啟發函數，在引導螞蟻對目標節點的感知、消除路徑搜索的盲目性和改善規劃路徑的平滑性方面效果顯著；提出的基于動態調整的信息素更新策略，使算法優化過程自適應調整信息素的強度，全局收斂速度得到明顯提升。

未來進一步探索建立基于自動駕駛車輛完整約束條件的精確算法模型，提高算法的效率和穩健性，滿足復雜環境下實時規避碰撞風險將是自動駕駛路徑規劃研究的重點問題。