改進(jìn)的蟻群算法在智能車輛路徑規(guī)劃中的運(yùn)用*

藍(lán) 丹，樊東紅，陳 強(qiáng)，危 維

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

0 引言

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

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

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

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

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

(1)

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

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

(2)

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

信息素更新公式為：

(3)

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

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

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

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

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

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

步驟5：重復(fù)步驟3、4，直到螞蟻到達(dá)目標(biāo)柵格或者無路可走；

步驟6：重復(fù)步驟3、4、5，直到m只螞蟻迭代結(jié)束；

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

步驟8：重復(fù)步驟3～7，直到n代螞蟻全部迭代結(jié)束。

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

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

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

2 改進(jìn)蟻群算法

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

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

(4)

(5)

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

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

(6)

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

2.2 改進(jìn)信息素更新方式

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

(7)

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

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

(8)

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

2.3 路徑平滑處理

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

(9)

式中，R為車輛轉(zhuǎn)向半徑，δ為車輛前輪轉(zhuǎn)向角，L為車輛軸距。

當(dāng)車輛進(jìn)入彎道轉(zhuǎn)向時，應(yīng)滿足：

(10)

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

圖1 智能車輛模型

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

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

圖2 改進(jìn)蟻群算法流程圖

3 仿真實(shí)驗(yàn)

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

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

在柵格地圖中，分別通過用0和1表示可行區(qū)域和障礙物區(qū)域，為充分驗(yàn)證本文所提算法的有效性，分別創(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ū)域，紅色方格代表起點(diǎn)，藍(lán)色方格代表終點(diǎn)，黃色方格代表動態(tài)障礙物，其沿x軸方向移動。

3.2 仿真運(yùn)行結(jié)果

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

1號地圖仿真結(jié)果如圖4所示。

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

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

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

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

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

2號地圖仿真結(jié)果如圖5所示。

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

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

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

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

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

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

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

4 結(jié)論

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