基于改進智能水滴算法的汽車避障局部路徑規劃*

宋曉琳,潘魯彬,曹昊天

(湖南大學，汽車車身先進設計制造國家重點實驗室，長沙 410082)

2016030

基于改進智能水滴算法的汽車避障局部路徑規劃*

宋曉琳,潘魯彬,曹昊天

(湖南大學，汽車車身先進設計制造國家重點實驗室，長沙 410082)

智能水滴算法是群落智能算法的一種新型算法，它模擬水流與泥沙相互作用而形成水道的機制，可應用于計算科學領域中求解復雜問題。針對原智能水滴算法在求解路徑規劃問題時，因啟發性不足而導致所規劃的路徑不理想的缺陷，通過改變原算法的概率選擇和更新機制，提出了改進的智能水滴算法。與其他算法對比仿真的結果表明，該改進算法的求解能力明顯提高。運用于汽車局部路徑規劃的結果表明，汽車在障礙規避過程中橫擺角速度和側向加速度值均符合穩定性要求，進一步驗證了該算法的可行性。

智能水滴算法；智能群落算法；路徑規劃；避障

前言

根據各種路徑規劃算法基本原理與時序，目前主要的路徑規劃算法可歸納為傳統算法和智能算法兩類[1]。傳統的路徑規劃算法有人工勢場法，模糊邏輯算法，啟發式搜索算法等。人工勢場法[2]是模擬力場的算法，其優點是所規劃的路徑平滑，但存在容易陷入局部最優解的問題。模糊邏輯算法[3]，其模糊規則的歸納和在線調整比較困難，應變性差。啟發類的A*算法[4]在復雜的環境中能夠快速地規劃出路徑，但所規劃的路徑不很理想。另外，在智能汽車的局部路徑規劃領域中，彈繩算法[5-6]能夠規劃出面向公路環境的理想路徑，但模型描述比較復雜。智能算法主要有神經網絡算法、遺傳算法和群智能算法等。神經網絡算法[7]是一種學習能力強的優秀算法，但較難描述復雜多變的環境。遺傳算法[8]是模擬達爾文生物進化論的自然選擇和遺傳學機理的計算模型，其優點是易于與其他算法結合，發揮其迭代的優勢，但實時性差。群智能算法[9]是一種結合概率選擇和啟發搜索的新型仿生算法，具有良好的自組織性和魯棒性，且對復雜問題的適應性較強，已受到越來越多學者們的重視。

智能水滴算法(IWD)[10]是由Hamed Shah Hosseini學者提出的一種新型群智能算法，它模擬水流與泥沙相互作用而形成水道的原理，可應用在計算科學領域中復雜問題的求解。該算法已被成功應用在旅行商問題(TSP)[10]、多重背包問題(MKP)[11]和車輛路徑問題(VRP)[12]等問題中。但對路徑規劃問題，由于原算法的啟發性不足，導致所規劃的路徑不理想。于是，本文中旨在對原算法進行改進，并驗證其在路徑規劃領域中的有效性與可行性。

1 智能水滴算法基本原理

在自然界中，水流對地面的沖刷作用會在地面形成一條能夠繞開障礙物并成功到達某低勢地點的溝壑。水流可看作由單位水滴組成的群體，而且每個水滴都帶有速度變量屬性和泥沙雜質成分。研究發現，當水滴流經某區域時，水滴更可能選擇含泥沙量少的河床經過，如此在重力的作用下，水滴將獲得更大的速度增量，沖刷掉更多的泥沙。如圖1所示，當兩個屬性相同的水滴分別流經區域(a)與區域(b)時，圖1(b)中的水滴將獲得更大的速度增量，帶走更多的泥沙。

在抽象的模型中，水滴按照離散步驟運動，并含有兩個屬性：運動速度veliwd與泥沙含量soiliwd。假設水滴的當前位置為i，在運動到下一位置j的過程中，將發生以下變化。

(1) 智能水滴在選擇路徑時會傾向于選擇泥沙量更少的路徑，為此以p(i,j)表示智能水滴在位置i選擇j作為下一位置的概率，它與路徑(i,j)的泥沙量soil(i,j)成反比關系，選擇概率為

(1)

(2)

式中：ε為極小正實數，且

(3)

(2) 水滴的速度增量Δveliwd非線性反比于路徑(i,j)的泥沙量soil(i,j)，即

(4)

式中：av，bv和cv是用戶自定義的系數。

(3) 水滴沖刷帶離的泥沙量Δsoiliwd非線性反比于水滴經過路徑(i,j)所需的時間變量time(i,j;veliwd)，并且與路徑(i,j)的泥沙減少量Δsoil(i,j)相等，即

Δsoil(i,j)=Δsoiliwd

(5)

(6)

式中：as，bs和cs為用戶自定義的系數。另外，time(i,j;veliwd)水滴從位置i到位置j所需時間為

(7)

式中HUD(i,j)為關于路段(i,j)的啟發函數。

(4) 當水滴從位置i到達位置j后，路段(i,j)所含泥沙量將被更新，以對其他水滴的路徑規劃形成反饋機制。泥沙量局部更新為

soil(i,j)=(1-ρ)·soil(i,j)-ρ·Δsoil(i,j)

(8)

式中ρ為0～1之間的系數。

(5) 當所有水滴按照步驟(1)～(4)從初始點到達目標點后，每個水滴都有著不同的路徑解TIWD，然后根據評價函數q(·)可以選擇出迭代最優的路徑解TIB為

(9)

式中arg(·)函數用于獲得最優解的元素。

當前最優路徑解TTB依據式(10)進行最優路徑解的更新。

(10)

(6) 為提高下一群水滴搜索最優路徑的能力，需要形成如式(11)所示的反饋機制對迭代最優解TIB的路徑進行全局泥沙量的更新。

(11)

式中：ρ為0～1之間的更新系數；NIB為路徑的節點數。

2 智能水滴算法的改進

針對原算法規劃路徑時存在啟發性不足的問題，本文中提出了以下幾方面的改進。

2.1 變量更換

為避免原算法在迭代求解過程中泥沙量正負亂秩的不良現象，改進算法以相對地平面缺失的泥沙量(負值)為變量，從而提高算法的收斂特性。

2.2 概率選擇策略

改進后概率選擇策略為

(12)

(13)

式中:Eta(i,j)為位置j距目的地的距離；Q為與距離有關的啟發強度指數。原算法的選擇策略只與泥沙量soil(i,j)成負相關；而改進算法的選擇策略與相對地平面缺少的泥沙量成正相關，與Eta(i,j)成負相關，這樣可以提高算法的收斂性與啟發性。

2.3更新機制

將式(7)中關于路段(i,j)的啟發函數HUD(i,j)用Eta(i,j)替代，這樣可對更優路段的泥沙量進行有效的更新，即

(14)

泥沙量的局部更新與全局更新分別為

soil(i,j)=soil(i,j)-ρ·Δsoil(i,j)

(15)

(16)

改進算法實現路徑規劃的流程如圖2所示。

3 算法的仿真對比實驗

為驗證智能水滴算法在路徑規劃應用中的有效性，本文中建立一個模擬環境，運用該算法完成路徑規劃，并與原智能水滴算法、蟻群算法、人工魚群算法和粒子群算法進行對比分析。

3.1 環境建模

環境建模的方法可概括為柵格法、幾何特征法和拓撲法3種表示法[13]。其中，柵格地圖直接與環境信息對應，容易創建與維護，既可用于全局路徑規劃也可用于局部路徑規劃[14]，是目前最常用的一種環境地圖。所以本算法也采用柵格地圖的方法表達環境信息。在自定義的25×25的二維柵格環境模型中，單位柵格的邊長為4m×4m，如圖3所示，黑色區域表示的是實際大小的靜止障礙物，其余白色空間是可以安全行駛的區域。另外，根據汽車外形尺寸將障礙物做相應的膨脹處理，并將汽車視為質心處的一點，以便于安全地規劃路徑。

3.2 初始參數設置

原水滴算法(IWD)[15]、蟻群優化算法(ACO)[16]、粒子群優化算法(PSO)[17]和魚群優化算法(AFSA)[18]的內容皆由編程實現。應用經驗試算法得到的改進水滴算法(IWD-P)和原水滴算法(IWD)的初始參數如表1所示。蟻群優化算法和魚群優化算法的初始參數則分別如表2和表3所示。

3.3 路徑光順

基于柵格環境模型規劃出的路徑難免出現曲折變向的現象，即路徑曲線的1階導數不連續，這顯然不滿足汽車高速運動下在動力學與運動學方面對安全穩定性的要求。所以，算法還需要對以上所規劃的路徑進行光順。由于B樣條曲線[19]的初點和末點保持不變，因此，采用此方法對原生路徑進行處理，以獲得光滑路徑。

3.4 有效性分析

仿真實驗的軟件平臺是MATLAB R2014a，硬件平臺是Win7@64bit+core2@2.53GHz+RAM@4G。各算法仿真結果路徑如圖3所示，將各算法分別運行32次，統計各算法的路徑長度(其中，剔除最長路徑和最短路徑)和平均耗時，結果如表4所示。

表1 兩種水滴算法的參數

表2 蟻群優化算法的參數

表3 魚群優化算法的參數

由圖3和表4可知，IWD算法無論在規劃的路徑還是實時性方面都很不理想；PSO和AFSA算法雖然實時性表現出明顯的優勢，但規劃出的路徑不光順且長度較長；IWD-P和ACO的路徑都較平順且距離最短，但從表4中方差對比可知，IWD-P算法的實時性與ACO的相差不大，但IWD-P的方差值明顯要小于ACO算法，說明IWD-P算法穩定性好。

名稱路徑長度/m平均值最小值方差平均用時/s原水滴算法315 11238 40667 8712 09改進水滴算法153 62152 170 655 63蟻群算法158 14152 174 175 74粒子群算法164 55159 203 680 35魚群算法171 05162 511 920 56

4 在汽車避障局部路徑規劃中的仿真

為說明改進水滴算法應用的可行性，將算法用于無人駕駛汽車的局部路徑規劃中。長度為260m、寬度為7m的平直同向雙車道可表達為65×6的二維柵格模型，單位柵格的邊長為4m×1.17m。為驗證算法對速度的魯棒性，仿真時，無人駕駛汽車分別以中速20m/s和高速30m/s行駛。當汽車探測到前方40m內有障礙時，系統將觸發局部路徑規劃程序以0.5s的時間間隔實時探測周邊環境，并據此進行路徑規劃。其中，算法的參數按表5設置。實驗場景主要分為以下3種。

4.1 對靜態障礙車的超車仿真

假設無人駕駛汽車分別以20和30m/s恒速在車道行駛，障礙汽車在無人駕駛汽車初始位置的前方40m處固定不動，場景如圖4(a)所示。用改進水滴算法規劃的路徑動態顯示如圖4(b)與圖4(c)所示，其中t0～t7各處的白色矩形分別表示無人駕駛汽車每隔0.5s時間的位置，黑色矩形表示障礙汽車。

表5 改進水滴算法的參數

為進一步研究汽車在跟隨路徑過程中的運動學特性，基于PRESCAN平臺搭建了環境模型，并將所規劃的路徑數據用PRESCAN的動力學模型進行仿真，結果如圖5所示。圖5(a)中的虛線是汽車跟隨目標路徑過程中所產生的運動軌跡，可見在兩種速度模式下，汽車的跟隨效果良好。圖5(b)與圖5(c)分別描述汽車運動過程中的側向加速度與橫擺角速度的變化情況，由圖可知，在靜態避障過程中汽車側向加速度的峰值均低于0.65m/s2，橫擺角速度峰值低于17(°)/s。因此，在此路況下，改進的水滴算法所規劃出的局部路徑能夠保證汽車穩定行駛。

4.2 對動態障礙車的超車仿真

假設無人駕駛汽車的車速分別以20和30m/s恒速在車道行駛，障礙汽車以16m/s恒速在同一車道上同向行駛，障礙汽車的初始位置在無人駕駛汽車初始位置的正前方40m處，場景如圖6(a)所示。改進水滴算法規劃出的路徑動態顯示如圖6(b)與圖6(c)所示，圖6(b)中t0～t17各處的白色與黑色矩形分別表示無人駕駛汽車與障礙汽車每隔0.5s時間的位置；圖6(c)中t0～t9各處的白色矩形與黑色矩陣分別表示無人駕駛汽車與障礙汽車每隔0.5s時間的位置。

圖7為汽車動態超車的動力學特性。圖7(a)中的虛線是汽車跟隨目標路徑過程中所產生的運動軌跡，在兩種速度模式下，汽車的跟隨效果良好。圖7(b)與圖7(c)分別描述汽車運動過程中的側向加速度與橫擺角速度的變化情況，由圖可知，在動態避障過程中汽車側向加速度的峰值均低于0.65m/s2，橫擺角速度峰值低于18(°)/s。因此，在此路況下，本算法所規劃出的局部路徑能夠保證汽車穩定行駛。

4.3 對動態障礙車的避障仿真

假設無人駕駛汽車以20m/s恒速向前行駛，障礙汽車在無人駕駛汽車初始位置的后方16m處以24m/s恒速向前方行駛，場景如圖8(a)所示。當障礙車對無人駕駛汽車超車時突然出現車道偏離現象，避障路徑動態顯示如圖8(b)所示，其中t0～t7各處的白色矩形分別表示無人駕駛汽車每隔0.5s時間的位置，t0～t7各處的黑色矩形分別表示障礙汽車每隔0.5s時間的位置。

圖9為汽車動態避障的動力學特性。圖9(a)中的虛線是汽車跟隨目標路徑過程中所產生的運動軌跡，可見汽車的跟隨效果良好。圖9(b)與圖9(c)分別描述汽車運動過程中的側向加速度與橫擺角速度的變化情況，由圖可知，在動態避障過程中汽車側向加速度的峰值低于0.6m/s2，橫擺角速度峰值低于16(°)/s。因此，在此路況下，本算法所規劃出的局部路徑能夠保證汽車穩定行駛。

5 結論

針對原智能水滴算法規劃路徑時啟發性不足的問題，分別對原算法的概率選擇策略和更新機制做了改進。通過與原算法和其他群落算法對比分析，結果表明：改進的水滴算法的求解能力顯著提高，且所規劃的路徑接近最優。

將改進的智能水滴算法用于汽車超車和避障局部路徑規劃中，并在兩種車速、3種交通場景下分別進行了仿真。結果表明：汽車按照規劃出的路徑行駛能夠實現安全避障，并且在運動過程中其側向加速度和橫擺角速度值均符合穩定性要求，說明采用改進的智能水滴算法求解汽車局部路徑規劃問題是可行的。

今后將對比研究不同環境模型下，本算法規劃路徑效果的差異，并將該算法應用于更復雜的路徑規劃問題，以求得到更好的效果。

致謝：感謝上海天歐TNO公司為本研究提供Prescan仿真軟件的支持。

[1] 張穎,吳成東,原寶龍.機器人路徑規劃方法綜述[J].控制工程,2008(z1):152-155.

[2] KHATIB O. Real-time Obstacle Avoidance for Manipulators and Mobile Robots[J]. The International Journal of Robotics Research,1986,5(1):90-98.

[3] WANG M, LIU J N K. Fuzzy Logic Based Robot Path Planning in Unknown Environment[C]. Machine Learning and Cybernetics. Proceedings of 2005 International Conference on. IEEE,2005,2:813-818.

[4] YAO J, LIN C, XIE X, et al. Path Planning for Virtual Human Motion Using Improved A*Star Algorithm[C]. Information Technology: New Generations (ITNG), 2010 Seventh International Conference on. IEEE,2010:1154-1158.

[5] SONG X, CAO H, HUANG J. Influencing Factors Research on Vehicle Path Planning Based on Elastic Bands for Collision Avoidance[J]. SAE International Journal of Passenger Cars-electronic and Electrical Systems,2012,5(2):625-637.

[6] SONG X, CAO H, HUANG J. Vehicle Path Planning in Various Driving Situations Based on the Elastic Band Theory for Highway Collision Avoidance[J]. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering,2013,227(12):1706-1722.

[7] JUNG I K, HONG K B, HONG S K, et al. Path Planning of Mobile Robot Using Neural Network[C]. Industrial Electronics. ISIE’99. Proceedings of the IEEE International Symposium on. IEEE,1999,3:979-983.

[8] HU Y, YANG S X. A Knowledge Based Genetic Algorithm for Path Planning of a Mobile Robot[C]. Robotics and Automation. Proceedings. ICRA’04. 2004 IEEE International Conference on. IEEE,2004,5:4350-4355.

[9] 馮翔,馬美怡,施尹,等.基于社會群體搜索算法的機器人路徑規劃[J].計算機研究與發展,2013,50(12).

[10] SHAH-HOSSEINI H. Problem Solving by Intelligent Water Drops[C]. Evolutionary Computation,2007. CEC 2007.IEEE.

[11] SHAH-HOSSEINI H. Intelligent Water Drops Algorithm: A New Optimization Method for Solving the Multiple Knapsack Problem[J]. International Journal of Intelligent Computing and Cybernetics,2008,1(2):193-212.

[12] KAMKAR I, AKBARZADEH-T M R, YAGHOOBI M. Intelligent Water Drops a New Optimization Algorithm for Solving the Vehicle Routing Problem[C]. Systems Man and Cybernetics (SMC),2010 IEEE International Conference on. IEEE,2010:4142-4146.

[13] 時丕芳,趙永瑞.移動機器人行走路徑環境建模方法綜述與解析[J].現代制造技術與裝備,2010(1):1-2.

[14] 馬兆青,袁曾任.基于柵格方法的移動機器人實時導航和避障[J].機器人,1996,18(6):344-348.

[15] DUAN H, LIU S, WU J. Novel Intelligent Water Drops Optimization Approach to Single UCAV Smooth Trajectory Planning[J]. Aerospace Science and Technology,2009,13(8):442-449.

[16] HSIAO Y T, CHUANG C L, CHIEN C C. Ant Colony Optimization for Best Path Planning[C]. Communications and Information Technology. ISCIT 2004.IEEE International Symposium on. IEEE,2004,1:109-113.

[17] 宮金超,李曉明.基于粒子群優化算法的小型足球機器人路徑規劃[J].機電工程,2010(12):116-120.

[18] 徐曉晴,朱慶保.動態環境下基于多人工魚群算法和避碰規則庫的機器人路徑規劃[J].電子學報,2012,40(8).

[19] 宋金澤,戴斌,單恩忠,等.一種改進的 RRT 路徑規劃算法[J].電子學報,2010,38(2A):225-228.

Local Path Planning for Vehicle Obstacle Avoidance Based onImproved Intelligent Water Drops Algorithm

Song Xiaolin, Pan Lubin & Cao Haotian

HunanUniversity,StateKeyLaboratoryofAdvancedDesignandManufacturingforVehicleBody,Changsha410082

Intelligent water drops (IWD) algorithm is a new swarm intelligent algorithm. It simulates the mechanism of water path forming by the interaction between water and soil, suitable for solving the complicated problems in computation science field. In view of the inadequate heuristic nature of original IWD algorithm, resulting in its incapacity to get an ideal path in solving routing problem, an improved IWD algorithm is proposed through the modifications of probability selection and updating mechanism in original IWD algorithm. The results of simulation on the improved IWD algorithm with comparison to other algorithms indicate that the improved IWD algorithm has its problem solving capability enhanced, and the results of its application to local path planning show that both the yaw rate and lateral acceleration of vehicle meet the requirements of stability in its obstacle avoidance maneuver, further verifying the feasibility of improved algorithm.

intelligent water drops algorithm; intelligent swarm algorithm; path planning; obstacle avoidance

*國家自然科學基金(51175159)、湖南省科技計劃項目(2013WK3024)和湖南省研究生科研創新項目(CX2013B146)資助。

原稿收到日期為2014年4月9日，修改稿收到日期為2014年12月10日。