李詩玄

摘 要：為了進(jìn)一步提高自主駕駛汽車真實(shí)動態(tài)環(huán)境下快速、準(zhǔn)確的自主避障能力，提出了一種基于粒子群參數(shù)優(yōu)化（PSO）的改進(jìn)蟻群算法（AC）模型實(shí)現(xiàn)了對自動駕駛汽車在自動避障時規(guī)劃路徑的全局快速優(yōu)化分析。首先，建立了自駕車輛的自主避障路徑規(guī)劃模型;其次，利用PSO中粒子間的協(xié)作和信息共享模式搜索全局信息;再次，利用全局信息更新策略優(yōu)化AC的路徑搜索能力;最后，采用PSO和AC融合算法求解出最佳的避障路徑。仿真結(jié)果表明，粒子群算法對蟻群算法模型進(jìn)行了改進(jìn)，從而實(shí)現(xiàn)了對自駕車輛自主避障路徑的快速、準(zhǔn)確的實(shí)時動態(tài)規(guī)劃。

關(guān)鍵詞：自主駕駛汽車;路徑規(guī)劃;蟻群算法;粒子群優(yōu)化;自主避障

Abstract：In order to further improve the accurate response and fast response ability of autonomous obstacle avoidance in real dynamic environment， an improved AC （ant colony algorithm） model based on PSO （Particle Swarm Optimization） is proposed to realize the global and fast optimization analysis of autonomous obstacle avoidance path planning for self-driving vehicles. Firstly， an autonomous obstacle avoidance path planning model for self-driving vehicles is established; secondly， the global pheromone is searched by using the cooperation and information sharing mode between particles in PSO; thirdly， the global pheromone updating strategy is used to optimize the path searching ability of AC; finally， an innovative way of integrating PSO and AC is used to obtain the optimal path of autonomous obstacle avoidance for self-driving vehicles. The simulation results show that the AC model is improved by PSO to realize the fast and accurate planning of autonomous obstacle avoidance path for self-driving vehicles.

Key words： self-driving vehicle; path planning; ant colony algorithm; particle swarm optimization; autonomous obstacle avoidance

自動駕駛車輛的自主避障已經(jīng)成為無人駕駛車輛領(lǐng)域的熱門話題[1]。為了有效保護(hù)自動駕駛車輛行駛狀態(tài)下的人身和財產(chǎn)安全，許多研究者將人工智能技術(shù)和算法應(yīng)用于自駕車輛的自主避碰和動態(tài)路徑規(guī)劃問題之中[2]。其中，蟻群算法在路徑規(guī)劃的應(yīng)用方面效果尤為突出[3]。

然而，在現(xiàn)實(shí)生活中，自動駕駛車輛的自主避障技術(shù)尚未得到相關(guān)立法和工程技術(shù)行業(yè)的廣泛推廣[4]，其主要原因是相關(guān)技術(shù)尚未達(dá)到成熟和可控的水平。蟻群算法是由意大利學(xué)者Dorigo、Maniezzo等人于20世紀(jì)90年代首先提出來的。他們發(fā)現(xiàn)蟻群在覓食過程中，個體螞蟻的行為相對簡單，但是螞蟻群體行為卻具有一定的智能性。在覓食時，多樣性使螞蟻不會走進(jìn)死胡同而無限循環(huán)，是一種創(chuàng)新能力;正反饋使優(yōu)良信息保存下來，是一種學(xué)習(xí)強(qiáng)化能力。兩者的巧妙結(jié)合使智能行為涌現(xiàn)，如果多樣性過剩，系統(tǒng)過于活躍，會導(dǎo)致過多的隨機(jī)運(yùn)動，陷入混沌狀態(tài);如果多樣性不夠，正反饋過強(qiáng)，會導(dǎo)致僵化，當(dāng)環(huán)境變化時蟻群不能相應(yīng)調(diào)整。同時，蟻群算法本身存在諸如收斂響應(yīng)時間長，易于進(jìn)入局部最優(yōu)解的問題[5]。單一算法無法獨(dú)立完美地解決自動駕駛車輛自主避障路徑規(guī)劃的實(shí)際應(yīng)用問題?；诖吮尘?，多種智能算法的結(jié)合已成為解決自動駕駛車輛自主避障問題的路徑規(guī)劃的發(fā)展趨勢。因此，下面本文介紹一種基于粒子群優(yōu)化的改進(jìn)蟻群算法。

2.自動駕駛車輛自主避障路徑技術(shù)路線優(yōu)化的建立

自動駕駛車輛的自主避障對實(shí)時響應(yīng)和的可控性有很高的要求，因此路徑規(guī)劃評估十分重要。結(jié)合PSO算法和AC算法各自的優(yōu)點(diǎn)，圖1給出了自動駕駛車輛自主避障路徑規(guī)劃優(yōu)化設(shè)計的技術(shù)設(shè)計路線：

自駕車輛自主避障路徑的具體技術(shù)路線優(yōu)化：

1.使用PSO算法，構(gòu)造時空的粒子集合：Ω（pi）（xi，yi，zi，tpi）;

2.建立粒子動態(tài)搜索模式，優(yōu)化粒子適應(yīng)度函數(shù);

3.通過適應(yīng)度函數(shù)動態(tài)調(diào)整全局信息素（使用循環(huán)迭代）;

4.建立蟻群算法，找出最短路徑函數(shù)（建立信息素更新方法）;

5.在時空中增加全局信息素干預(yù);

6.通過全局范圍信息素的積累和路徑優(yōu)化的迭代工作，得到了自駕車輛自主避障行為的規(guī)劃路徑。

3.基于PSO的改進(jìn)蟻群自主避障路徑優(yōu)化模型

3.1基于PSO的適應(yīng)度函數(shù)模型

PSO是一種基于種群的隨機(jī)優(yōu)化控制技術(shù)，受種群行為特征的啟發(fā)，用于解決優(yōu)化問題。每個優(yōu)化問題的潛在解決方案可以被認(rèn)為是n維搜索空間中的一個點(diǎn)，稱為“粒子”。所有粒子都具有由目標(biāo)函數(shù)確定的適應(yīng)度值，并且每個粒子具有確定其方向和距離的速度。然后粒子跟隨當(dāng)前最優(yōu)粒子在解空間中搜索。

每個粒子可以被視為n維搜索空間中的搜索個體。粒子的當(dāng)前位置是相應(yīng)優(yōu)化問題的備選解決方案。粒子的飛行過程是個體的搜索過程。粒子的飛行速度可以根據(jù)粒粒子向自身的歷史最佳位置和鄰域或整個群體的歷史最佳位置聚集來進(jìn)行。粒子只有兩個屬性：速度和位置，速度代表粒子的運(yùn)動速度，位置代表粒子的運(yùn)動方向。每個粒子獨(dú)立搜索的最優(yōu)解決方案稱為獨(dú)立極值，粒子群中的最優(yōu)獨(dú)立極值是當(dāng)前的全局的最優(yōu)解。速度和位置不斷迭代和更新。最終，獲得滿足終止條件的最優(yōu)解。

3.1.1 PSO算法的初始化

PSO用于通過粒子間的協(xié)作和信息共享獲得滿足自行駕駛車輛自主避障的路徑規(guī)劃優(yōu)化要求時空中最佳的定位點(diǎn)。結(jié)合算法更能有效提高求解過程中的收斂速度和最優(yōu)解精度，找到最優(yōu)調(diào)度方案[6，7]。

粒子的速度矢量和當(dāng)前時空位置用公式（1）和（2）表示。

（1）

（2）

在公式（1）和（2）中，Vi+1是粒子的速度矢量，Pi+1是時間t時粒子的位置，pbesti代表單粒子的最佳位置，gbesti代表整個群體的實(shí)際最佳位置，c0，c1，c2代表路徑規(guī)劃過程中粒子群的調(diào)整系數(shù)，c0是0到1之間的隨機(jī)數(shù)，c1，c2是0到2之間的隨機(jī)數(shù). Vi是Vi+1，pbesti-Pi和gbesti-Pi之間的向量和，代表粒子速度的更新受當(dāng)前速度，感知模式和群體信息的影響。

3.1.2 適應(yīng)性函數(shù)的意義

在自動駕駛車輛自主避障路徑優(yōu)化的背景下，PSO的動態(tài)響應(yīng)適應(yīng)度函數(shù)定義如下[8]。

（3）

在公式（3）中，在時間t，（xp，yp，zp）是粒子的空間坐標(biāo)，（xS，yS，zS）是起點(diǎn)坐標(biāo)，（xD，yD，zD）是結(jié)束點(diǎn)坐標(biāo)。

表示從當(dāng)前位置到終點(diǎn)的p粒子的估計值。 ? ? ? ? ? ? 表示從起點(diǎn)到當(dāng)前位

置的距離之和， ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 。 Ob代表預(yù)測障礙信息量。當(dāng) ? ? ? ? ? ? ? ? ? ? ?時，Ob很清晰;當(dāng) ? ? ? ? ? ? ? ? ? ? 時，Ob比較清晰;當(dāng) ? ? ? ? ? ? ? ? ? ? ? ? ? ?時，Ob為一般清晰;當(dāng) ? ? ? ? ? ? ? ? ? ? ? ? ? 時，Ob相對模糊。

3.2基于AC的全局信息素更新

蟻群算法的基本原理來源于自然界中螞蟻覓食的最短路徑原理。當(dāng)螞蟻在尋找食物來源時，它們會在它們所經(jīng)過的路徑中釋放信息素，這是螞蟻在覓食過程中進(jìn)行種群交流的一種特性，因此在一定范圍內(nèi)的其他螞蟻可以檢測并因此影響它們未來的行為。當(dāng)越來越多的螞蟻通過某些路徑時，它們會留下越來越多的信息素，導(dǎo)致信息素濃度增加，從而選擇該路徑的螞蟻的概率就會更高，這也會導(dǎo)致在該路徑上的信息素濃度增強(qiáng)。該選擇過程稱為螞蟻的自催化行為。螞蟻行走路徑用于表示待優(yōu)化問題的可行解，整個蟻群的所有路徑構(gòu)成了待優(yōu)化問題的解空間。路徑較短的螞蟻會釋放更多的信息素。隨著時間的推移，在較短路徑上累積的信息素濃度逐漸增加，選擇該路徑的螞蟻數(shù)量也在增加。

3.2.1 AC的初始化

螞蟻之間的信息傳遞是通過稱為信息素的物質(zhì)實(shí)現(xiàn)的。通常，AC的信息素累積過程受路徑規(guī)劃更新過程中信息量的影響[9]。

路徑優(yōu)化過程中AC的信息更新方法如公式（4）所示。

（4）

在公式（4）中， ? ? ? ? ?表示循環(huán)中路徑ij上的信息量的總增量; ρ表示信息的揮發(fā)程度，范圍從0到1; ? ? ? ? ? ?表示在此循環(huán)中螞蟻k在路徑ij上離開的信息增量; Cf表示在該循環(huán)中螞蟻k在路徑ij上留下的信息量的增量相關(guān)系數(shù)。

3.2.2 全局信息素的動態(tài)更新策略

根據(jù)PSO在全局時空中的適應(yīng)性函數(shù)，在AC的迭代過程中調(diào)整了全局情況下的信息素分布和積累[10]。

通過調(diào)整Cf，可以實(shí)現(xiàn)信息素累積的全局調(diào)度。 Cf的具體形式如下所示。

（5）

在公式（5）中，RBest表示最優(yōu)規(guī)劃路徑數(shù)據(jù)，f（pi）min表示粒子群適應(yīng)性函數(shù)的最小值，f（pi）max表示粒子群適應(yīng)性函數(shù)的最大值。

4.仿真分析

為了驗(yàn)證基于PSO優(yōu)化AC的自動駕駛車輛自主避障路徑優(yōu)化問題的可行性，從規(guī)劃路徑自身優(yōu)化程度和路徑規(guī)劃的時效性兩個維度進(jìn)行了仿真驗(yàn)證。

4.1規(guī)劃路徑模擬

根據(jù)自駕車輛自主避障的路徑規(guī)劃要求，從規(guī)劃路徑的相對優(yōu)化程度進(jìn)行比較工作，如圖2所示。

如圖2所示，由于PSO + AC的復(fù)雜度高于AC，在路徑規(guī)劃優(yōu)化的初始階段（迭代次數(shù)<50），PSO + AC路徑規(guī)劃優(yōu)化的相對增長率低于AC的。但隨著迭代次數(shù)的增加，PSO + AC的路徑優(yōu)化度具有明顯的優(yōu)勢。當(dāng)?shù)螖?shù)在90和130之間時，路徑規(guī)劃使用AC算法一度陷入局部最優(yōu)解的情況，間接導(dǎo)致AC的路徑規(guī)劃優(yōu)化的相對程度的降低。

4.2路徑規(guī)劃的及時性模擬

根據(jù)自動駕駛車輛自主避障的路徑規(guī)劃要求，對規(guī)劃路徑的時效性進(jìn)行了比較，如圖3所示。

如圖3所示，AC算法在最短路徑優(yōu)化的整個過程中頻繁波動。相比較而言，PSO + AC算法的波動更加穩(wěn)定。其主要原因是：在路徑規(guī)劃的早期階段，PSO被用來驅(qū)動AC全局信息素的動態(tài)更新策略。同時，在T≈751 ms時，PSO + AC方法接近接近94.5%的最短路徑并保持該狀態(tài)。在T ≈ 792 ms時，AC方法接近最短路徑方法達(dá)到77.0%并保持該狀態(tài)。

5.結(jié)論

在分析自駕車輛自主避障路徑優(yōu)化的過程中，通過對蟻群算法和粒子群算法分別進(jìn)行改進(jìn)，利用兩種算法自身優(yōu)勢相結(jié)合的方式建立一種蟻群粒子群算法，提高了云計算資源調(diào)度效率，解決云計算中資源調(diào)度方案優(yōu)化問題。實(shí)驗(yàn)結(jié)果表明，該算法所消耗的時間更少，效果更好[11]。PSO與AC的結(jié)合解決辦法在計算初期的路徑規(guī)劃與避障能力相較于AC單獨(dú)解決方法偏差較大，得出最優(yōu)路徑所需時間相對較長，但在實(shí)際運(yùn)用中，總體路徑規(guī)劃結(jié)果與效率很大程度的優(yōu)于AC單獨(dú)解決方式的效果。并且，在路徑規(guī)劃的穩(wěn)定性上，PSO與AC的結(jié)合使自動避障車在避障的成功率方面有了顯著的提升。同時，該方法提高了自駕車輛在自主避障過程中對于全局最優(yōu)路徑的搜索能力和避障的準(zhǔn)確性。

參考文獻(xiàn)：

[1]Polvara R， Sharma S， Wan J， et al. Obstacle Avoidance Approaches for Autonomous Navigation of Unmanned Surface Vehicles[J]. Journal of Navigation， 2017， 71（1）：1-16.

[2]Lee U， Yoon S， Shim H C， et al. Local path planning in a complex environment for self-driving car[C]// IEEE International Conference on Cyber Technology in Automation. 2014.

[3]Jie C， Fang Y， Tao J. Path planning under obstacle-avoidance constraints based on ant colony optimization algorithm[C]// IEEE International Conference on Communication Technology. 2018.

[4]Larson J， Bruch M， Ebken J. Autonomous Navigation and Obstacle Avoidance for Unmanned Surface Vehicles[J]. Proceedings of SPIE - The International Society for Optical Engineering， 2006， 6230：623007-623007-12.

[5]朱宏偉， 游曉明， 劉升. 基于粒子群參數(shù)優(yōu)化的同構(gòu)雙種群蟻群算法[J]. 測控技術(shù)， 2007， 33（3）：279-285.

[6]Li G， Chou W. Path planning for mobile robot using self-adaptive learning particle swarm optimization[J]. Science China Information Sciences， 2018， 61（5）：052204.

[7]El-Shorbagy， M.A， Hassanien A E. Particle Swarm Optimization from Theory to Applications[J]. International Journal of Rough Sets and Data Analysis， 2018， 5.

[8]譚冠政， 賀歡， Sloman A. 基于ACS算法的移動機(jī)器人實(shí)時全局最優(yōu)路徑規(guī)劃[J]. 自動化學(xué)報， 2019，001-009

[9]粒子群蟻群結(jié)合算法在車輛調(diào)度問題中的應(yīng)用研究[J]. 陳磊. ?湖北工業(yè)大學(xué)學(xué)報. 2016（05）

[10]Wu J， Chen B， Kai Z， et al. Ant pheromone route guidance strategy in intelligent transportation systems[J]. Physica A Statistical Mechanics & Its Applications， 2018， 503：S0378437118301225.

[11]薩日娜. 基于蟻群粒子群優(yōu)化算法的云計算資源調(diào)度方案[J]. 吉林大學(xué)學(xué)報（理學(xué)版）. 2017（06）