宋曉琳,潘魯彬,曹昊天

(湖南大學(xué)，汽車車身先進(jìn)設(shè)計(jì)制造國(guó)家重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)沙 410082)

2016030

基于改進(jìn)智能水滴算法的汽車避障局部路徑規(guī)劃*

宋曉琳,潘魯彬,曹昊天

(湖南大學(xué)，汽車車身先進(jìn)設(shè)計(jì)制造國(guó)家重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)沙 410082)

智能水滴算法是群落智能算法的一種新型算法，它模擬水流與泥沙相互作用而形成水道的機(jī)制，可應(yīng)用于計(jì)算科學(xué)領(lǐng)域中求解復(fù)雜問(wèn)題。針對(duì)原智能水滴算法在求解路徑規(guī)劃問(wèn)題時(shí)，因啟發(fā)性不足而導(dǎo)致所規(guī)劃的路徑不理想的缺陷，通過(guò)改變?cè)惴ǖ母怕蔬x擇和更新機(jī)制，提出了改進(jìn)的智能水滴算法。與其他算法對(duì)比仿真的結(jié)果表明，該改進(jìn)算法的求解能力明顯提高。運(yùn)用于汽車局部路徑規(guī)劃的結(jié)果表明，汽車在障礙規(guī)避過(guò)程中橫擺角速度和側(cè)向加速度值均符合穩(wěn)定性要求，進(jìn)一步驗(yàn)證了該算法的可行性。

智能水滴算法；智能群落算法；路徑規(guī)劃；避障

前言

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

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

1 智能水滴算法基本原理

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

在抽象的模型中，水滴按照離散步驟運(yùn)動(dòng)，并含有兩個(gè)屬性：運(yùn)動(dòng)速度veliwd與泥沙含量soiliwd。假設(shè)水滴的當(dāng)前位置為i，在運(yùn)動(dòng)到下一位置j的過(guò)程中，將發(fā)生以下變化。

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

(1)

(2)

式中：ε為極小正實(shí)數(shù)，且

(3)

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

(4)

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

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

Δsoil(i,j)=Δsoiliwd

(5)

(6)

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

(7)

式中HUD(i,j)為關(guān)于路段(i,j)的啟發(fā)函數(shù)。

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

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

(8)

式中ρ為0～1之間的系數(shù)。

(5) 當(dāng)所有水滴按照步驟(1)～(4)從初始點(diǎn)到達(dá)目標(biāo)點(diǎn)后，每個(gè)水滴都有著不同的路徑解TIWD，然后根據(jù)評(píng)價(jià)函數(shù)q(·)可以選擇出迭代最優(yōu)的路徑解TIB為

(9)

式中arg(·)函數(shù)用于獲得最優(yōu)解的元素。

當(dāng)前最優(yōu)路徑解TTB依據(jù)式(10)進(jìn)行最優(yōu)路徑解的更新。

(10)

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

(11)

式中：ρ為0～1之間的更新系數(shù)；NIB為路徑的節(jié)點(diǎn)數(shù)。

2 智能水滴算法的改進(jìn)

針對(duì)原算法規(guī)劃路徑時(shí)存在啟發(fā)性不足的問(wèn)題，本文中提出了以下幾方面的改進(jìn)。

2.1 變量更換

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

2.2 概率選擇策略

改進(jìn)后概率選擇策略為

(12)

(13)

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

2.3更新機(jī)制

將式(7)中關(guān)于路段(i,j)的啟發(fā)函數(shù)HUD(i,j)用Eta(i,j)替代，這樣可對(duì)更優(yōu)路段的泥沙量進(jìn)行有效的更新，即

(14)

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

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

(15)

(16)

改進(jìn)算法實(shí)現(xiàn)路徑規(guī)劃的流程如圖2所示。

3 算法的仿真對(duì)比實(shí)驗(yàn)

為驗(yàn)證智能水滴算法在路徑規(guī)劃應(yīng)用中的有效性，本文中建立一個(gè)模擬環(huán)境，運(yùn)用該算法完成路徑規(guī)劃，并與原智能水滴算法、蟻群算法、人工魚群算法和粒子群算法進(jìn)行對(duì)比分析。

3.1 環(huán)境建模

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

3.2 初始參數(shù)設(shè)置

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

3.3 路徑光順

基于柵格環(huán)境模型規(guī)劃出的路徑難免出現(xiàn)曲折變向的現(xiàn)象，即路徑曲線的1階導(dǎo)數(shù)不連續(xù)，這顯然不滿足汽車高速運(yùn)動(dòng)下在動(dòng)力學(xué)與運(yùn)動(dòng)學(xué)方面對(duì)安全穩(wěn)定性的要求。所以，算法還需要對(duì)以上所規(guī)劃的路徑進(jìn)行光順。由于B樣條曲線[19]的初點(diǎn)和末點(diǎn)保持不變，因此，采用此方法對(duì)原生路徑進(jìn)行處理，以獲得光滑路徑。

3.4 有效性分析

仿真實(shí)驗(yàn)的軟件平臺(tái)是MATLAB R2014a，硬件平臺(tái)是Win7@64bit+core2@2.53GHz+RAM@4G。各算法仿真結(jié)果路徑如圖3所示，將各算法分別運(yùn)行32次，統(tǒng)計(jì)各算法的路徑長(zhǎng)度(其中，剔除最長(zhǎng)路徑和最短路徑)和平均耗時(shí)，結(jié)果如表4所示。

表1 兩種水滴算法的參數(shù)

表2 蟻群優(yōu)化算法的參數(shù)

表3 魚群優(yōu)化算法的參數(shù)

由圖3和表4可知，IWD算法無(wú)論在規(guī)劃的路徑還是實(shí)時(shí)性方面都很不理想；PSO和AFSA算法雖然實(shí)時(shí)性表現(xiàn)出明顯的優(yōu)勢(shì)，但規(guī)劃出的路徑不光順且長(zhǎng)度較長(zhǎng)；IWD-P和ACO的路徑都較平順且距離最短，但從表4中方差對(duì)比可知，IWD-P算法的實(shí)時(shí)性與ACO的相差不大，但I(xiàn)WD-P的方差值明顯要小于ACO算法，說(shuō)明IWD-P算法穩(wěn)定性好。

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

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

為說(shuō)明改進(jìn)水滴算法應(yīng)用的可行性，將算法用于無(wú)人駕駛汽車的局部路徑規(guī)劃中。長(zhǎng)度為260m、寬度為7m的平直同向雙車道可表達(dá)為65×6的二維柵格模型，單位柵格的邊長(zhǎng)為4m×1.17m。為驗(yàn)證算法對(duì)速度的魯棒性，仿真時(shí)，無(wú)人駕駛汽車分別以中速20m/s和高速30m/s行駛。當(dāng)汽車探測(cè)到前方40m內(nèi)有障礙時(shí)，系統(tǒng)將觸發(fā)局部路徑規(guī)劃程序以0.5s的時(shí)間間隔實(shí)時(shí)探測(cè)周邊環(huán)境，并據(jù)此進(jìn)行路徑規(guī)劃。其中，算法的參數(shù)按表5設(shè)置。實(shí)驗(yàn)場(chǎng)景主要分為以下3種。

4.1 對(duì)靜態(tài)障礙車的超車仿真

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

表5 改進(jìn)水滴算法的參數(shù)

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

4.2 對(duì)動(dòng)態(tài)障礙車的超車仿真

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

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

4.3 對(duì)動(dòng)態(tài)障礙車的避障仿真

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

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

5 結(jié)論

針對(duì)原智能水滴算法規(guī)劃路徑時(shí)啟發(fā)性不足的問(wèn)題，分別對(duì)原算法的概率選擇策略和更新機(jī)制做了改進(jìn)。通過(guò)與原算法和其他群落算法對(duì)比分析，結(jié)果表明：改進(jìn)的水滴算法的求解能力顯著提高，且所規(guī)劃的路徑接近最優(yōu)。

將改進(jìn)的智能水滴算法用于汽車超車和避障局部路徑規(guī)劃中，并在兩種車速、3種交通場(chǎng)景下分別進(jìn)行了仿真。結(jié)果表明：汽車按照規(guī)劃出的路徑行駛能夠?qū)崿F(xiàn)安全避障，并且在運(yùn)動(dòng)過(guò)程中其側(cè)向加速度和橫擺角速度值均符合穩(wěn)定性要求，說(shuō)明采用改進(jìn)的智能水滴算法求解汽車局部路徑規(guī)劃問(wèn)題是可行的。

今后將對(duì)比研究不同環(huán)境模型下，本算法規(guī)劃路徑效果的差異，并將該算法應(yīng)用于更復(fù)雜的路徑規(guī)劃問(wèn)題，以求得到更好的效果。

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

[1] 張穎,吳成東,原寶龍.機(jī)器人路徑規(guī)劃方法綜述[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] 馮翔,馬美怡,施尹,等.基于社會(huì)群體搜索算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)研究與發(fā)展,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] 時(shí)丕芳,趙永瑞.移動(dòng)機(jī)器人行走路徑環(huán)境建模方法綜述與解析[J].現(xiàn)代制造技術(shù)與裝備,2010(1):1-2.

[14] 馬兆青,袁曾任.基于柵格方法的移動(dòng)機(jī)器人實(shí)時(shí)導(dǎo)航和避障[J].機(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] 宮金超,李曉明.基于粒子群優(yōu)化算法的小型足球機(jī)器人路徑規(guī)劃[J].機(jī)電工程,2010(12):116-120.

[18] 徐曉晴,朱慶保.動(dòng)態(tài)環(huán)境下基于多人工魚群算法和避碰規(guī)則庫(kù)的機(jī)器人路徑規(guī)劃[J].電子學(xué)報(bào),2012,40(8).

[19] 宋金澤,戴斌,單恩忠,等.一種改進(jìn)的 RRT 路徑規(guī)劃算法[J].電子學(xué)報(bào),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

*國(guó)家自然科學(xué)基金(51175159)、湖南省科技計(jì)劃項(xiàng)目(2013WK3024)和湖南省研究生科研創(chuàng)新項(xiàng)目(CX2013B146)資助。

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