智能汽車主動避障的改進(jìn)蟻群路徑規(guī)劃方法

呂 佳，邱建崗

（1.重慶建筑工程職業(yè)學(xué)院軌道與機(jī)電工程系，重慶 400072；2.北京汽車動力總成有限公司，北京 101106）

1 引言

隨著家用汽車的普及，汽車在城鎮(zhèn)居民家庭中的保有量持續(xù)升高，而與此同時行車安全問題也逐漸受到關(guān)注。隨著人工智能和傳感技術(shù)的快速發(fā)展，智能汽車逐漸成為各個國家關(guān)注的熱點方向。所謂智能汽車是指在普通汽車上加裝傳感系統(tǒng)、控制系統(tǒng)和執(zhí)行系統(tǒng)，以使車輛能夠智能感知外界環(huán)境并自主進(jìn)行行為決策[1]。智能軌跡規(guī)劃方法是智能汽車的關(guān)鍵技術(shù)，主要涉及兩部分內(nèi)容：（1）以某種性能最優(yōu)為優(yōu)化指標(biāo)，規(guī)劃汽車從出發(fā)點到終點的路徑；（2）在路徑規(guī)劃過程中，主動避開沿途的障礙物。目前，研究智能汽車軌跡規(guī)劃算法對智能汽車行業(yè)的快速發(fā)展至關(guān)重要[2?3]。

國內(nèi)外學(xué)者圍繞智能汽車主動避障路徑規(guī)劃方法做了大量工作，主要方法包括人工勢場法[4]、Dijkstra算法[5]、滾動時域法[6]、遺傳算法[7]、蟻群算法[8?9]等。文獻(xiàn)[5]提出了一種改進(jìn)的Dijkstra算法以規(guī)劃移動機(jī)器人路徑，但該算法容易陷入局部最優(yōu)。文獻(xiàn)[6]基于滾動時域優(yōu)化思路對移動機(jī)器人進(jìn)行軌跡規(guī)劃，但該算法對系統(tǒng)的模型精度要求較高，在較為復(fù)雜的柵格環(huán)境中很難找到最優(yōu)解析解。Dijkstra算法雖然能有效規(guī)劃路徑，但算法的可行性較差，解算出最優(yōu)解耗時過長。此外，遺傳算法計算效率較低，收斂速度較慢且占用內(nèi)存較大。

人工勢函數(shù)法雖在一定程度上能夠滿足規(guī)劃需求，但其解算過程容易受初值的影響[10]。傳統(tǒng)的蟻群算法由于其具有良好的魯棒性和可靠性在智能避障方面受到學(xué)者們的青睞。但該算法也存在進(jìn)化速度緩慢、容易陷入局部最優(yōu)等問題[11]。由此可知，探索較為有效的智能搜索算法仍存在挑戰(zhàn)。

在充分考慮傳統(tǒng)蟻群算法缺陷的基礎(chǔ)上，為解決智能汽車主動避障軌跡規(guī)劃問題，這里提出了一種改進(jìn)蟻群智能軌跡規(guī)劃方法。在傳統(tǒng)蟻群算法的基礎(chǔ)上，通過在迭代過程中自適應(yīng)調(diào)節(jié)信息素因子、啟發(fā)因子、信息素?fù)]發(fā)率和信息素濃度函數(shù)，實現(xiàn)了自適應(yīng)軌跡規(guī)劃的目標(biāo)。所提方法能夠自適應(yīng)更新各項參數(shù)以擴(kuò)大粒子搜索范圍、提升算法全局搜索能力并且顯著加快算法的收斂速度，從而有效解決了算法的局部最優(yōu)和進(jìn)化緩慢問題。智能汽車主動避障實驗驗證了所提方法的有效性和可靠性。

2 蟻群算法基本原理和流程

2.1 蟻群算法基本原理

蟻群算法由意大利學(xué)者提出，該算法模擬蟻群運動規(guī)律，在路徑規(guī)劃過程中用信息素濃度表征螞蟻對當(dāng)前路徑選擇的概率大小，較大的信息素濃度意味著螞蟻選擇該路徑的概率較大且該路徑較優(yōu)。蟻群算法經(jīng)過多次迭代，最終可找到從出發(fā)點到目標(biāo)地的最優(yōu)路徑。目前該算法在智能路徑規(guī)劃和主動避障方面應(yīng)用較為廣泛。在傳統(tǒng)的蟻群算法中，每只螞蟻選擇路徑（i，j）的轉(zhuǎn)移概率可表示為：

式中：dij(t)—兩點i和j之間的距離。

當(dāng)在一次迭代循環(huán)中每只螞蟻完成路徑規(guī)劃后，信息素全局更新方法為：

式中：τij(t+1)—第（k+1）次迭代時信息素總量；Δτij(t)—相應(yīng)的增量；ρ—信息素?fù)]發(fā)率；Q—信息素強(qiáng)度，為常值；Lk—第k個螞蟻選擇路徑（i，j）時的路徑長度。

2.2 蟻群算法具體流程

（1）參數(shù)初始化

初始化蟻群種群數(shù)量n，信息素因子α，啟發(fā)信息因子β，信息素?fù)]發(fā)率ρ，信息素強(qiáng)度Q，以及最大迭代次數(shù)Nmax，同時約定蟻群的出發(fā)點和終點。

（2）更新狀態(tài)轉(zhuǎn)移概率

對于每只螞蟻，計算路徑（i，j）的距離，并根據(jù)式（1）和式（2）計算轉(zhuǎn)移概率。通過比較不同路徑的概率大小，確定該步的路徑節(jié)點。

（3）更新禁忌表

對于每只螞蟻，每經(jīng)過一個節(jié)點后將該節(jié)點納入禁忌表；

（4）搜索全局路徑

對于每只螞蟻，重復(fù)步驟（2）和（3），直到到達(dá)終點，同時將每只螞蟻的全局路徑進(jìn)行保存；

（5）更新信息素

所有螞蟻規(guī)劃完路徑后，對于每條路徑的信息素進(jìn)行更新，也就是計算式（4）～式（6）；

（6）循環(huán)迭代

在第（5）步信息素更新的基礎(chǔ)上，將所有螞蟻重新放回出發(fā)點，重新進(jìn)行路徑規(guī)劃，直到達(dá)到最大迭代次數(shù)。在每次迭代之后，保留每代螞蟻的最短路徑。

（7）最優(yōu)路徑

對比每代蟻群的最短路徑，并找出最短路徑即為最優(yōu)路徑。

蟻群算法由于計算過程清晰、魯棒性強(qiáng)，且易與其他算法結(jié)合，在智能汽車軌跡規(guī)劃和避障領(lǐng)域應(yīng)用較為廣泛。但由2.2節(jié)基本流程（1）～（7）可知，由于信息素因子α，啟發(fā)信息因子β和信息素?fù)]發(fā)率ρ不能隨路徑搜索過程進(jìn)行自適應(yīng)調(diào)節(jié)，這也給智能汽車軌跡規(guī)劃和避障帶來了一定的缺陷，如收斂速度慢、易于陷入局部最優(yōu)以及搜索停滯等問題。針對本文智能汽車軌跡規(guī)劃問題，為了提高算法的實用性和可靠性，本文提出一種改進(jìn)的蟻群算法。

3 改進(jìn)的蟻群算法

由式（1）可知，每只螞蟻的一步轉(zhuǎn)移概率與信息素因子α和起發(fā)因子β直接相關(guān)，在基本蟻群算法中，α和β均設(shè)置為固定值，該做法極易造成算法的局部最優(yōu)。其次，信息素?fù)]發(fā)率ρ對算法的全局搜索能力有很大影響，而傳統(tǒng)蟻群算法不能夠?qū)Ζ堰M(jìn)行自適應(yīng)調(diào)節(jié)，這也不利于算法的快速收斂。

本節(jié)提出一種改進(jìn)蟻群算法以增強(qiáng)算法的可行性和穩(wěn)定性。首先，3.1節(jié)給出一種α和β的自適應(yīng)更新方法以擴(kuò)大算法的全局搜索空間，增強(qiáng)算法的可靠性。其次，通過自適應(yīng)調(diào)節(jié)信息素?fù)]發(fā)率ρ進(jìn)一步提高算法的收斂速度；最后，通過改進(jìn)式（2）的啟發(fā)函數(shù)ηij(t)的計算方式以提高螞蟻就近選擇路徑的概率，進(jìn)而提高算法的運算效率。

3.1 自適應(yīng)調(diào)節(jié)信息素因子和啟發(fā)因子

由式（1）可知，信息素因子α和啟發(fā)因子β對螞蟻一步轉(zhuǎn)移概率有十分重要的影響。α過大或者過小，該算法均會陷入局部最優(yōu)。β過大則螞蟻更傾向于選擇較近的路徑。因此，這里給出了一種自適應(yīng)更新方法，具體如式（6）所示：

式中：αmin和βmin—初始值；αmax和βmax—最大值；P—循環(huán)迭代過程中的某一給定值；Ni—當(dāng)前迭代次數(shù)。

式（6）和式（7）自適應(yīng)更新的思想為：在路徑尋優(yōu)的初期，先將α和β置于最小初值以提高算法的全局搜索能力，避免陷入局部最優(yōu)；當(dāng)?shù)螖?shù)達(dá)到P次時，基于式（6）和式（7）自適應(yīng)調(diào)節(jié)α和β以避免算法出現(xiàn)停滯和僵局。

3.2 自適應(yīng)調(diào)節(jié)信息素?fù)]發(fā)率

由式（3）可知，信息素?fù)]發(fā)率ρ對信息素的更新起到至關(guān)重要的作用。當(dāng)ρ較大時，之前的搜索路徑被螞蟻選擇的概率更高，此時信息素的正反饋作用明顯。當(dāng)ρ較小時，之前的搜索路徑效果并不好，此時螞蟻尋求新的路徑的可能性更大，此時算法的全局搜索能力更強(qiáng)，但是收斂速度較低。因此，為了配合式（6）和式（7）的更新，在前期可以選擇較大的ρ以彌補(bǔ)前期α和β較小的不足。隨著迭代次數(shù)的增大，可以由大到小自適應(yīng)更新ρ以增強(qiáng)算法的全局搜索能力。具體更新為：

式中：ρ0—初始揮發(fā)率，取值為接近1的常數(shù)。

3.3 改進(jìn)啟發(fā)函數(shù)的更新方式

蟻群算法具有易于實現(xiàn)、約束條件寬松且具有較好的適用性，但根據(jù)3.1和3.2節(jié)的分析可知，由于尋優(yōu)思路簡單且基本算法中參數(shù)適應(yīng)性不強(qiáng)，該方法極易陷入局部最優(yōu)。由式（2）可知，啟發(fā)函數(shù)ηij(t)與路徑距離成反比，在智能汽車軌跡規(guī)劃過程中，約定：

根據(jù)式（2）可知，基本蟻群算法中啟發(fā)函數(shù)為：ηij(t)=1/dij(t)，該種更新方式不利于算法的搜索結(jié)果快速收斂。為了有效提高算法的一步?jīng)Q策效率，使蟻群向著路徑最短的方向進(jìn)化，這里改進(jìn)啟發(fā)函數(shù)ηij(t)的更新方式（式（10）），在算法中增加一個權(quán)系數(shù)用于調(diào)節(jié)尋優(yōu)速度。

式中：C—權(quán)系數(shù)。

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

根據(jù)上述內(nèi)容，本文改進(jìn)蟻群算法具體流程可以概括為：

（1）初始化算法參數(shù)。分別設(shè)置蟻群種群數(shù)量n，最大迭代次數(shù)Nmax，信息素強(qiáng)度Q，權(quán)系數(shù)C，以及自適應(yīng)調(diào)節(jié)參數(shù)αmin，αmax，βmin，βmax和ρ0。設(shè)定智能汽車規(guī)劃路徑的出發(fā)點和終點。

（2）更新一步狀態(tài)轉(zhuǎn)移概率。對于每只螞蟻，根據(jù)式（10）計算路徑（i，j）的距離，并根據(jù)式（1）和式（2）計算轉(zhuǎn)移概率。這里的信息素因子α和啟發(fā)因子β按照式（6）和式（7）進(jìn)行自適應(yīng)更新。在解算每條路徑概率之后，選擇出一步轉(zhuǎn)移的最佳路徑，也即概率最大的路徑。

（3）更新禁忌表。對于每只螞蟻，每經(jīng)過一個節(jié)點后將該節(jié)點納入禁忌表；

（4）搜索全局路徑。對于每只螞蟻，重復(fù)（2）和（3），直到到達(dá)終點，同時保存每只螞蟻的全局路徑和路徑長度；

（5）更新信息素。所有螞蟻完成路徑規(guī)劃后，基于式（4）～式（6）對每條路徑的信息素進(jìn)行更新，在計算過程中，這里的信息素?fù)]發(fā)率ρ按照式（8）進(jìn)行自適應(yīng)更新；

（6）循環(huán)迭代。將上一步計算的全局信息素反饋到下一次迭代過程中，將所有螞蟻重新放回出發(fā)點，重新進(jìn)行路徑規(guī)劃，直到達(dá)到最大迭代次數(shù)。在每次迭代之后，保留每代螞蟻的最短路徑。

（7）算法完成。在完成所有迭代之后，從每代種群中找出最優(yōu)路徑。綜上，這里改進(jìn)蟻群算法的具體流程，如圖1所示。

4 智能汽車自主避障仿真實驗

4.1 柵格環(huán)境模型

為了檢驗這里改進(jìn)蟻群算法在智能汽車避障問題中的有效性和可靠性，這里用柵格法將智能汽車避障地圖進(jìn)行分解。采用一定寬度的柵格將汽車行駛的環(huán)境進(jìn)行分割，可以有效檢驗智能算法的有效性。在柵格環(huán)境中，當(dāng)障礙物存在于某個柵格內(nèi)時，此時將柵格屬性賦值為1，代表該柵格內(nèi)存在障礙物。當(dāng)不存在障礙物時，賦值為0。

此外，當(dāng)障礙物不能完全占滿柵格時，采用膨脹法視為完全填充。最后將汽車行駛的地圖用包含0和1元素的柵格矩陣來表示，如：

在下文仿真驗證過程中，采用標(biāo)準(zhǔn)的（15×15）和（20×20）兩張地圖開展仿真實驗（下文分別稱為1號地圖和2號地圖），兩張地圖中障礙物的分布有所區(qū)別。

4.2 路徑規(guī)劃性能驗證

為了說明本文算法的優(yōu)勢，這里的智能車分別采用基本蟻群算法和本文改進(jìn)蟻群算法兩種方法，分別在1號和2號地圖中開展仿真實驗。在仿真過程中，蟻群數(shù)目設(shè)定為100，最大迭代次數(shù)為200 次，設(shè)定αmin為0.3，αmax為0.9，βmin為0.2，βmax為1，ρ0為0.25，C為2.5。中間過渡迭代次數(shù)P為80.信息素強(qiáng)度Q為1。信息素初始增量為0。在1號地圖中，起始點設(shè)置為（0.5，0.5），終點設(shè)置為（14.5，14.5）。在2 號地圖中，起始點和終點設(shè)置為（0.5，0.5）和（19.5，19）。兩組實驗結(jié)果，如圖2和圖3以及表1所示。

圖2 在1號地圖中兩種方法的對比結(jié)果Fig.2 Comparative Results of the Two Methods in Map 1

圖3 在2號地圖中兩種方法的對比結(jié)果Fig.3 Comparative Results of the Two Methods in Map 2

表1 實驗結(jié)果對比Tab.1 Comparison of Experimental Results

圖2和圖3所示分別為智能車采用傳統(tǒng)蟻群算法和改進(jìn)蟻群算法在1號地圖和2號地圖中規(guī)劃的最優(yōu)路徑。由圖2可知，在（15×15）柵格環(huán)境下，兩種方法均能夠保證智能車有效規(guī)避障礙物并規(guī)劃出可行路徑，但采用改進(jìn)蟻群算法所規(guī)劃的路徑更加簡潔、清晰。在仿真時，每個柵格的長度設(shè)定為1，此時傳統(tǒng)蟻群算法規(guī)劃的最優(yōu)路徑長度為30.52，而改進(jìn)蟻群算法規(guī)劃的最優(yōu)路徑為26.53，采用改進(jìn)算法規(guī)劃的路徑節(jié)省了13.07%的路程。在更為復(fù)雜的2號地圖中，兩種方法所得的結(jié)果，如圖3所示。對比圖3（a）和3（b）可知，改進(jìn)蟻群算法所規(guī)劃的路徑更加簡潔高效。實際上，傳統(tǒng)蟻群算法在2 號地圖中所規(guī)劃最優(yōu)路徑長度為40.56，而改進(jìn)蟻群算法所規(guī)劃的最優(yōu)路徑長度為36.58，后者節(jié)省了9.81%的路程。

由表1所示實驗統(tǒng)計結(jié)果可知，改進(jìn)蟻群算法在平均路徑長度、最優(yōu)路徑長度、迭代次數(shù)和平均耗時等方面均優(yōu)于傳統(tǒng)蟻群算法，顯示出了算法的改良特性。由于改進(jìn)蟻群算法采用了自適應(yīng)因子更新方法，能夠在實驗初期擴(kuò)大搜索范圍、并在實驗全程有效加快粒子進(jìn)化速度，從而提高了算法的全局收縮能力和收斂速度，最終保證了避障路徑的最優(yōu)和最快。

綜合以上分析，由于改進(jìn)蟻群算法在路徑搜索初期能夠自適應(yīng)調(diào)節(jié)信息素因子α和啟發(fā)因子β，在前期保證了智能車能夠在較大范圍內(nèi)進(jìn)行全局路徑規(guī)劃。而在路徑搜索全程通過自適應(yīng)調(diào)節(jié)揮發(fā)率和信息素函數(shù)，實現(xiàn)了算法的快速收斂，進(jìn)而保證了智能車快速搜索到最短路徑。這從圖2和圖3中的最優(yōu)軌跡和表1中的收斂特性也能得以體現(xiàn)。仿真結(jié)果驗證了這里所提智能汽車主動避障改進(jìn)蟻群算法的有效性和平滑性。

5 結(jié)論

這里針對智能汽車主動避障路徑規(guī)劃問題，提出了一種自適應(yīng)蟻群智能避障方法。首先，在分析傳統(tǒng)算法缺陷的基礎(chǔ)上，給出了信息素因子、啟發(fā)因子、信息素?fù)]發(fā)率以及啟發(fā)函數(shù)的更新算法以擴(kuò)大算法的全局搜索能力、提升算法的收斂速度并提高路徑規(guī)劃質(zhì)量。智能汽車避障實驗驗證表明：（1）所提方法能夠有效規(guī)劃智能汽車避障路徑，并有效加快算法的收斂速度，降低迭代次數(shù)；（2）與傳統(tǒng)蟻群算法相比，這里算法能夠有效提升路徑規(guī)劃質(zhì)量，顯著降低路徑規(guī)劃長度，增強(qiáng)了算法的可靠性和平滑性。