藍 丹，樊東紅，陳 強，危 維

(1.廣西生態(tài)工程職業(yè)技術學院汽車與信息工程學院，廣西 柳州 545004；2.廣西民族師范學院數(shù)理與電子信息工程學院，廣西 崇左 532200；3.柳州電信分公司，廣西 柳州 545004)

0 引言

隨著互聯(lián)網、大數(shù)據以及人工智能等高新技術在車輛領域的廣泛運用，車輛正由人工操控加速向智能化系統(tǒng)控制轉變，智能車輛已成為產業(yè)技術的戰(zhàn)略制高點，受到廣泛研究人員的關注[1-3]。路徑規(guī)劃作為智能車輛的核心技術之一，其主要功能是根據給定的環(huán)境模型，在一定約束條件下，規(guī)劃出一條連接車輛當前位置和目標位置的無碰撞路徑，是確保車輛正常行駛的關鍵，也是智能車輛技術研究中的重點[4-6]。

當前，大量學者對智能車輛路徑規(guī)劃問題開展了廣泛的研究：文獻[7]運用人工勢場算法對車輛進行局部路徑規(guī)劃，實現(xiàn)了車輛在滿足動力學約束以及平穩(wěn)性、安全性要求前提下的避障換道，但僅限于規(guī)避靜態(tài)障礙物；文獻[8]在傳統(tǒng)人工勢場算法中引入速度斥力勢場，以此規(guī)劃出車輛運動的動態(tài)路徑，實現(xiàn)了車輛的動態(tài)避障，且能滿足車輛轉向要求；文獻[9-11]進一步對傳統(tǒng)人工勢場算法進行改進，引入調節(jié)因子，進行車輛運動的路徑規(guī)劃，較好的克服了陷入局部最優(yōu)且不適用于動態(tài)環(huán)境等問題。以上是傳統(tǒng)的人工勢場法在車輛路徑規(guī)劃中的應用。隨著人工智能技術的快速發(fā)展，模糊邏輯算法、遺傳算法、快速擴展隨機樹等智能算法在車輛路徑規(guī)劃問題中也得到了較好的應用。文獻[12]提出了一種分層分級的模糊控制方法，通過設計避障控制器和目標趨向控制器實現(xiàn)了車輛的運動避障，減少了算法的計算量；文獻[13]對傳統(tǒng)遺傳算法進行改進，提出了一種車輛路徑規(guī)劃方法，大大提高了系統(tǒng)收斂速度；文獻[14]設計期望避障路徑模型，提出一種改進RRT路徑規(guī)劃算法，較好的解決了傳統(tǒng)RRT算法隨機性太大導致的路徑不平滑問題，使得規(guī)劃路徑能夠滿足車輛動力學約束。

本文針對智能車輛路徑規(guī)劃問題，提出一種改進蟻群智能路徑規(guī)劃方法，較好地解決了傳統(tǒng)蟻群算法搜索時間長和容易陷入局部最優(yōu)等缺陷，在提高算法效率的同時保證了路徑的平滑性并能實現(xiàn)實時動態(tài)避障，有效提高了車輛行駛的安全性。

1 傳統(tǒng)蟻群算法原理及缺陷

在t時刻，螞蟻k從柵格i轉移到柵格j的概率為：

(1)

式中，Jk(i)表示螞蟻k下一步可選柵格的集合。τij表示當前路徑的信息素濃度，ηij表示一個啟發(fā)因子，α和β分別表示信息素和期望啟發(fā)因子的相對重要程度。

式(1)中，ηij具體表達式為：

(2)

式中，d(j,G)表示柵格j到目標柵格G的距離。

信息素更新公式為：

(3)

式中，λ為局部信息素揮發(fā)速率，表示全局信息素揮發(fā)速率，Δτij表示全局信息素濃度，Q為正常數(shù)，Lk為第k只螞蟻在本次周游中的最短路徑長度。

根據以上原理，算法的主要流程為：

步驟1：創(chuàng)建柵格化地圖環(huán)境，輸入由0和1組成的矩陣表示需要尋找最優(yōu)路徑的地圖，其中0表示可行道路，1表示障礙物；

步驟2：信息素矩陣、初始點、終止點、啟發(fā)因子等各類參數(shù)初始化設置；

步驟3：選擇從初始柵格下一步的可行柵格，并根據路徑的信息素濃度，通過公式(1)求得前往每個節(jié)點的概率，通過輪盤算法獲得下一步的初始柵格；

步驟4：更新柵格路徑以及路程；

步驟5：重復步驟3、4，直到螞蟻到達目標柵格或者無路可走；

步驟6：重復步驟3、4、5，直到m只螞蟻迭代結束；

步驟7：按公式(3)更新信息素矩陣，沒有到達目標柵格的螞蟻除外；

步驟8：重復步驟3～7，直到n代螞蟻全部迭代結束。

從算法的基本原理和主要流程來看，傳統(tǒng)蟻群算法主要存在以下缺陷[16]：

(1)由于螞蟻尋找路徑的隨機性比較大，且初始時刻各路徑的信息素大致相同，導致了搜索時間較長；

(2)根據路徑選擇概率公式，螞蟻會朝著信息素濃度較大的路徑前進，但當搜索規(guī)模較大時，容易陷入局部最優(yōu)。

2 改進蟻群算法

2.1 優(yōu)化路徑選擇概率

在傳統(tǒng)蟻群算法中，從螞蟻選擇概率公式(1)可以看出，螞蟻在選擇下一步移動柵格時，取決于信息素濃度τij以及僅包含柵格j到目標柵格G的距離信息的啟發(fā)信息ηij，完全沒有考慮障礙柵格信息，算法通過提供的先驗位置信息，判斷可行區(qū)域，能夠實現(xiàn)有效靜態(tài)避障，但對于動態(tài)障礙物，此法失效。為保證螞蟻能夠有效實現(xiàn)動態(tài)避障，現(xiàn)將障礙柵格信息引入選擇概率中。改進后的路徑選擇概率公式為：

(4)

(5)

式中，d(i,b)表示障礙柵格與自由柵格的距離，γ為障礙距離的啟發(fā)因子，用以表示δib(t)的重要程度。

同時為了增加路徑選擇的多樣性，避免算法陷入局部最優(yōu)，對啟發(fā)式因子ηij進行改進：

(6)

式中，C為正常數(shù)。

2.2 改進信息素更新方式

在傳統(tǒng)蟻群算法中的初期時，螞蟻每進行一次移動時，走過路徑的信息素都會按照一定的揮發(fā)速率而減弱，當搜索問題規(guī)模較大時，可能會導致該條路徑信息素揮發(fā)至0，從而較低算法搜索能力，為此，對局部信息素揮發(fā)系數(shù)改進如下：

(7)

式中，0.95λ(t)表示取95%的信息素揮發(fā)因子的上限，λmin表示信息素揮發(fā)因子的下限。

同時，為避免某條路徑信息素濃度過大或過小，而導致出現(xiàn)搜索停滯，對其做出范圍限制如下：

(8)

通過改進局部信息素揮發(fā)系數(shù)以及限定信息素濃度的閾值，能有效防止某條路徑上的信息素濃度過高或過低，從而實現(xiàn)在保證路徑選擇多樣性的同時，提高算法的局部搜索能力和收斂性。

2.3 路徑平滑處理

圖1為智能車輛簡化模型，考慮車輛處于較低速度行駛狀態(tài)，此時車輛運行相對穩(wěn)定，車輛轉向靈敏性可通過轉向半徑來表示，具體表達式為[8]：

(9)

式中，R為車輛轉向半徑，δ為車輛前輪轉向角，L為車輛軸距。

當車輛進入彎道轉向時，應滿足：

(10)

式中，車輛轉向角通常在30°～40°，乘用車輛軸距一般在2.3～2.45 m之間，取δmax=40°，取Lmax=2.45 m。

圖1 智能車輛模型

傳統(tǒng)蟻群算法的路徑規(guī)劃并沒有考慮路徑拐點的轉彎半徑，而車輛在行駛過程中為避免側翻，需滿足一定的轉向特性，為此，本文在改進傳統(tǒng)蟻群算法路徑選擇概率和信息素更新方式的基礎上，再通過樣條插值方法對規(guī)劃路徑進行平滑處理，使得其轉向半徑滿足公式(10)，從而確保車輛行駛的穩(wěn)定性。

綜上所述，改進后的蟻群算法基本流程如圖2所示。

圖2 改進蟻群算法流程圖

3 仿真實驗

為驗證本文所提改進蟻群路徑規(guī)劃算法的有效性，以智能車為對象，采用柵格地圖環(huán)境進行對比仿真實驗。

3.1 柵格地圖環(huán)境創(chuàng)建

在柵格地圖中，分別通過用0和1表示可行區(qū)域和障礙物區(qū)域，為充分驗證本文所提算法的有效性，分別創(chuàng)建如圖3a所示的20×20的靜態(tài)方格地圖，以下稱為1號地圖，該地圖中僅存在靜態(tài)障礙物，以及如圖3b所示的11×15的動態(tài)車道地圖，以下稱為2號地圖，該地圖存在靜態(tài)和動態(tài)兩種障礙物。

(a) 1號靜態(tài)方格地圖

(b) 2號動態(tài)車道地圖圖3 柵格地圖環(huán)境

圖中，黑色方格表示靜態(tài)障礙物以及車道邊界等不可行區(qū)域，紅色方格代表起點，藍色方格代表終點，黃色方格代表動態(tài)障礙物，其沿x軸方向移動。

3.2 仿真運行結果

分別使用傳統(tǒng)蟻群算法和本文改進蟻群算法在1號地圖和2號地圖進行仿真實驗，仿真參數(shù)設置為：螞蟻個數(shù)M為50，迭代次數(shù)K為100，信息素全局蒸發(fā)系數(shù)為0.8，信息素局部蒸發(fā)系數(shù)λ為0.6，重要程度參數(shù)α為2，β為4，信息素強度Q為2。得到仿真結果如圖4～圖6所示。

1號地圖仿真結果如圖4所示。

(a) 傳統(tǒng)蟻群算法路徑規(guī)劃結果

(b) 本文改進蟻群算法路徑規(guī)劃結果圖4 1號地圖中仿真結果

表1 1號地圖仿真結果數(shù)據

分析1號地圖兩種算法仿真結果，從圖4a中可以看出，傳統(tǒng)蟻群算法可有效避開已知靜態(tài)障礙物，而規(guī)劃出一條全局路徑；從圖4b中可以看出，本文改進的蟻群算法能夠有效避開圖中靜態(tài)障礙物，且規(guī)劃出的路徑相對較為平滑；從表1所示的仿真結果對比中可以看出，改進蟻群算法較傳統(tǒng)蟻群算法最優(yōu)路徑長度減少了17.5%，運行時間減少了75.8%。

1號地圖兩組仿真實驗重點證明了改進算法在收斂速度和全局優(yōu)化上較傳統(tǒng)算法具有明顯的優(yōu)越性。

2號地圖仿真結果如圖5所示。

(a) 初始狀態(tài)路徑規(guī)劃結果

(b) 動態(tài)障礙位置變化后路徑規(guī)劃結果圖5 2號地圖中傳統(tǒng)蟻群算法仿真結果

分析2號地圖傳統(tǒng)蟻群算法仿真結果，從圖5可以看出，初始狀態(tài)時該算法能夠較好的同時避開動態(tài)和靜態(tài)障礙物，而當動態(tài)障礙物位置發(fā)生變化時，由于算法中的路徑選擇概論并沒有對動態(tài)障礙物位置信息進行更新，所以路徑規(guī)劃結果不會發(fā)生變化，無法有效避開位置更新后的動態(tài)障礙物。

分析2號地圖改進蟻群算法仿真結果，從圖6可以看出，初始狀態(tài)時該算法能夠較好的同時避開動態(tài)和靜態(tài)障礙物，當動態(tài)障礙物位置發(fā)生變化時，由于改進算法中的路徑選擇概率引入了動態(tài)障礙物位置信息，因而能根據動態(tài)障礙的實時位置進行路徑規(guī)劃，從而有效避開動態(tài)障礙物，且規(guī)劃出的路徑平滑性較好。

(a) 初始狀態(tài)路徑規(guī)劃結果

(b) 動態(tài)障礙位置變化后路徑規(guī)劃結果圖6 2號地圖中改進蟻群算法仿真結果

2號地圖兩組仿真實驗結果重點證明了改進算法在動態(tài)避障以及路徑平滑上較傳統(tǒng)算法具有明顯優(yōu)越性。

4 結論

本文針對智能車輛路徑規(guī)劃問題，提出一種改進蟻群智能路徑規(guī)劃方法，較好的解決了傳統(tǒng)蟻群算法搜索時間長和容易陷入局部最優(yōu)等缺陷，在提高算法效率的同時保證了路徑的平滑性并能實現(xiàn)實時動態(tài)避障，進一步提高了車輛行駛的安全性。兩種不同工況下的對比仿真實驗充分驗證了所提改進蟻群算法具有以下優(yōu)越性：一是通過在概率轉移公式中引入障礙物位置信息，實現(xiàn)了動態(tài)避障；二是通過改進信息素更新方式，提高了算法的收斂性；三是通過樣條插值方法提高了路徑的平滑性。