文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.166484
中文引用格式: 唐焱,,肖蓬勃,李發(fā)琴,,等. 避障最優(yōu)路徑系統(tǒng)研究[J].電子技術(shù)應(yīng)用,,2017,43(11):128-131,,135.
英文引用格式: Tang Yan,,Xiao Pengbo,Li Faqin,,et al. Research of urban traffic obstacle avoidance and early warning system[J].Application of Electronic Technique,,2017,43(11):128-131,,135.
0 引言
隨著城市繁華區(qū)域車(chē)輛行駛密度的增加,,行車(chē)過(guò)程車(chē)道上阻礙行車(chē)的各類(lèi)移動(dòng)、固定障礙物出現(xiàn)頻數(shù)不斷增多,,嚴(yán)重影響行車(chē)速度,,這是導(dǎo)致區(qū)域交通擁堵的主要因素之一。有關(guān)研究表明:駕駛者從觀測(cè),、判斷到駕駛動(dòng)作的執(zhí)行,,以及車(chē)輛控制系統(tǒng)的反應(yīng),所需總時(shí)間在1.87 s以上,,其中人員生理反應(yīng)時(shí)間約占60%~70%[1],。因此在一定車(chē)速條件下,人工操作避障極易發(fā)生車(chē)輛與障礙物之間的碰撞,,導(dǎo)致在車(chē)道障礙物較多的交通環(huán)境中難以實(shí)現(xiàn)自動(dòng)駕駛,。利用安裝于車(chē)輛前方的超聲波等探測(cè)系統(tǒng)進(jìn)行路障信息采集,由車(chē)載電腦作數(shù)字化處理并及時(shí)反饋和視頻預(yù)警[2],,將有效保證繁華市區(qū)行車(chē)安全和提高行車(chē)速度,。
1 避障系統(tǒng)核心算法
1.1 人工勢(shì)場(chǎng)法
車(chē)輛行駛速度受行駛目的地,、車(chē)道障礙物兩方面的因素影響。在繁華城區(qū)的行駛要求所有車(chē)輛能安全,、迅速通過(guò),,從而對(duì)交通環(huán)境影響程度達(dá)到最小。人工勢(shì)場(chǎng)法原理表明,,動(dòng)態(tài)物體在設(shè)定的空間按預(yù)期目的地運(yùn)動(dòng)時(shí),,存在兩種物理勢(shì)場(chǎng)的影響,即預(yù)期目的地吸引力和運(yùn)動(dòng)過(guò)程沿途障礙物的排斥力,。運(yùn)用多目標(biāo)優(yōu)化處理的方法,,合理解決上述吸引和排斥的矛盾,能獲得安全高效的運(yùn)動(dòng)方案[3],。
1.2 A*搜尋算法
A*搜尋算法是一種探測(cè)性的算法,,其是一種在平面圖形中求出最低成本的算法。規(guī)劃合理的行車(chē)路徑,,減少擁堵,,降低運(yùn)營(yíng)成本是A*搜尋算法應(yīng)用的重要領(lǐng)域之一。A*算法基本思想是通過(guò)劃分網(wǎng)格,,計(jì)算起點(diǎn)到當(dāng)前點(diǎn)的距離G和目標(biāo)點(diǎn)到當(dāng)前點(diǎn)的距離H的和,,通過(guò)比較大小,把可能通過(guò)的點(diǎn)儲(chǔ)存進(jìn)open列表,,而不會(huì)考慮的點(diǎn)則儲(chǔ)存進(jìn)closed列表,。
1.3 粒子群算法(ACO)
粒子群算法(PSO)是一種群智能算法,其基本思想是模擬鳥(niǎo)群覓食的行為,,通過(guò)鳥(niǎo)類(lèi)之間的集體協(xié)作使群體飛行路線(xiàn)最優(yōu)的算法[4],。在粒子群算法中,用無(wú)質(zhì)量無(wú)體積的粒子作個(gè)體,,并且為每個(gè)粒子規(guī)定一定的運(yùn)動(dòng)規(guī)則,,從而使整個(gè)群體表現(xiàn)出一定的復(fù)雜特性。PSO概念簡(jiǎn)明,,無(wú)需復(fù)雜的調(diào)整、收斂速度快,,收斂準(zhǔn)確,、設(shè)置參數(shù)少、實(shí)現(xiàn)簡(jiǎn)單,,且其數(shù)學(xué)基礎(chǔ)相對(duì)薄弱,,沒(méi)有系統(tǒng)的數(shù)學(xué)基礎(chǔ)。
1.4 矩陣實(shí)驗(yàn)室(MATLAB)
MATLAB是適用于數(shù)值計(jì)算,、數(shù)據(jù)分析及可視化,、算法開(kāi)發(fā)等場(chǎng)合的高級(jí)技術(shù)計(jì)算語(yǔ)言,,具有矩陣運(yùn)算、繪制函數(shù),、數(shù)據(jù)圖像等功能,,本研究即在交互式環(huán)境中對(duì)算法進(jìn)行編程,進(jìn)行特定算法計(jì)算,,實(shí)現(xiàn)動(dòng)態(tài)仿真和數(shù)據(jù)輸出,。
2 路徑規(guī)劃算法原理
2.1 人工勢(shì)場(chǎng)法原理
2.1.1 人工勢(shì)場(chǎng)法函數(shù)
經(jīng)典勢(shì)能函數(shù)將運(yùn)動(dòng)物體(汽車(chē))作為一個(gè)運(yùn)動(dòng)質(zhì)點(diǎn)置于虛擬人工勢(shì)場(chǎng)之中:運(yùn)動(dòng)終點(diǎn)與汽車(chē)相互作用產(chǎn)生的引力場(chǎng)用式(1)表示,障礙物與汽車(chē)相互作用產(chǎn)生的斥力場(chǎng)用式(2)表示[5-10],,即:
輸入初始條件,、汽車(chē)信息等參數(shù),實(shí)時(shí)采集并更新車(chē)道環(huán)境參數(shù),,建立動(dòng)態(tài)勢(shì)場(chǎng)分布,,在虛擬力的作用下完成路徑規(guī)劃。
2.1.2 人工勢(shì)場(chǎng)法程序設(shè)計(jì)及仿真結(jié)果
基于人工市場(chǎng)法在MATLAB環(huán)境進(jìn)行設(shè)計(jì),。
初始條件為:起始點(diǎn)為(10.5,,10.5),終點(diǎn)(1.5,,1.5),。系統(tǒng)參數(shù)為:引力的增益系數(shù)k=20;斥力增益系數(shù)m=20,;障礙影響距離P=1,;障礙個(gè)數(shù)n=8;步長(zhǎng)a=0.5,;l=0.4,;循環(huán)迭代次數(shù)j=200。
基于人工勢(shì)場(chǎng)法設(shè)計(jì)的路徑規(guī)劃如圖1,,障礙物為實(shí)心圓圈,,空心圓圈代表障礙物的大小是障礙物半徑和障礙物的斥力之和,因此路徑會(huì)進(jìn)入障礙物范圍,;將信息數(shù)據(jù)輸入式(1),、式(2)運(yùn)算行車(chē)終點(diǎn)引力和障礙斥力總和,獲得安全避障行駛的相關(guān)數(shù)據(jù),。
2.2 A*搜尋算法(a星算法)
路徑優(yōu)化的第一步是把地圖簡(jiǎn)化成容易控制的搜索形式,,即通過(guò)劃分網(wǎng)格,把本文的地圖劃分為10×10的小網(wǎng)格,。
2.2.1 A*算法的相關(guān)參數(shù)
(1)Open列表和Closed列表
①一個(gè)記錄下所有被考慮來(lái)尋找最短路徑方塊的列表,,被稱(chēng)為OPEN列表。
②一個(gè)記錄下所有不會(huì)再考慮來(lái)尋找最短路徑方塊的列表,其中包括起點(diǎn)和邊界,,被稱(chēng)為Closed列表,。
(2)路徑增量
G值是從開(kāi)始點(diǎn)到當(dāng)前點(diǎn)所在的方塊的移動(dòng)量,即規(guī)定從開(kāi)始點(diǎn)到相鄰方塊的移動(dòng)量為1,,其值會(huì)隨著距離開(kāi)始點(diǎn)越來(lái)越遠(yuǎn)而增大,。
H值是從當(dāng)前點(diǎn)靠目標(biāo)點(diǎn)的移動(dòng)量的估計(jì)值,在算法中常被稱(chēng)為探視,,而估計(jì)值越接近真實(shí)值,,最終的路線(xiàn)會(huì)更加精確。如果估計(jì)值停止作用,,則規(guī)劃的路徑很大概率不是最短,,通常使用的是“曼哈頓距離方法”,其僅僅是計(jì)算出當(dāng)前點(diǎn)距離目標(biāo)點(diǎn)剩下的方塊總數(shù),,除去障礙物的總數(shù),。
2.2.2 A*搜尋算法的規(guī)劃流程
(1)將地圖劃分為n×n的網(wǎng)格;
(2)計(jì)算G+H的和F,;
(3)將方塊提價(jià)到open列表中,,本列表中有最小的F值,將此值稱(chēng)為S,。
(4)將S從open列表中移除,,添加到closed列表中;
(5)對(duì)于與S相鄰的四周方塊T可進(jìn)行如下運(yùn)算:
①如果T在closed列表中,,刪除,,不考慮;
②如果T不在open列表中,,計(jì)算其和值并添加進(jìn)open列表中,;
③如果T在open列表中,當(dāng)使用當(dāng)前生成的路徑到達(dá)T時(shí),,檢查F值是否更小,,如果是,更新和值F并前進(jìn)[11-12],。
2.2.3 A*星算法程序設(shè)計(jì)及仿真結(jié)果
基于A*星搜索算法在MATLAB中進(jìn)行路徑仿真,,結(jié)果如圖2,其中障礙物的布置同人工勢(shì)場(chǎng)法,,邊界的限定為[1,,11]。
如圖2,,其中黑色粗線(xiàn)條代表從起點(diǎn)到終點(diǎn)的直線(xiàn)距離,之后用于比較規(guī)劃路徑距離的長(zhǎng)短,細(xì)線(xiàn)條為A*算法的實(shí)際路徑,。
2.3 粒子群算法(PSO算法)
2.3.1 粒子群算法參數(shù)的選取
粒子群算法主要確定如下各項(xiàng)參數(shù)[13-14]:
(1)粒子數(shù)目:粒子數(shù)越大,,則粒子的搜索的空間范圍越大,但相應(yīng)的搜索所需時(shí)間也越大,。一般的粒子數(shù)取20~40,,由于本文的問(wèn)題比較特殊,本文的粒子數(shù)目取200,。
(2)粒子長(zhǎng)度:大小決定于具體問(wèn)題,。
(3)粒子范圍:大小取決于具體優(yōu)化問(wèn)題,且粒子的每一維度可設(shè)置不同的取值范圍,。
(4)粒子最大速率:大小決定了粒子在一次運(yùn)行中可以移動(dòng)的最大距離,,如果不限定粒子的極限速率,粒子可能會(huì)在一次運(yùn)行中超出搜索空間,,而粒子最大速率的設(shè)定取決于粒子范圍的最大寬度,。
(5)學(xué)習(xí)因子(加速常數(shù)):固定常數(shù),一般取2,。當(dāng)沒(méi)有慣性權(quán)重時(shí),,引入收斂因子,其取值也不一定取2,,C1+C2=4.1時(shí),,收斂因子取0.729。部分實(shí)驗(yàn)研究表明兩個(gè)因子相等且都等于0.2時(shí)效果更好,,部分實(shí)驗(yàn)也表明C1大于C2且其和小于4時(shí)效果更好,。
(6)算法終止條件:最大的迭代次數(shù)和在一定的誤差范圍內(nèi)都可作為終止條件。
(7)適應(yīng)度函數(shù):目標(biāo)函數(shù)或目標(biāo)函數(shù)的變換,。
2.3.2 粒子群算法的具體步驟
算法的流程可以描述如下:
(1)初始化一群粒子(種群規(guī)模為M),,其中包括隨機(jī)位置X和隨機(jī)速度V;通常是在范圍內(nèi)隨機(jī)產(chǎn)生,。設(shè)定學(xué)習(xí)因子C1,、C2,最大迭代次數(shù)Gmax,。
(2)評(píng)價(jià)每個(gè)粒子的適應(yīng)度,;
(3)對(duì)每個(gè)粒子的適應(yīng)值和其經(jīng)過(guò)的歷史最好位置Pbest作對(duì)比,如果較好,,則選擇其作為當(dāng)前最優(yōu)位置,,即更新個(gè)體極值。
(4)對(duì)每個(gè)粒子的適應(yīng)值和種群經(jīng)過(guò)的歷史最好位置Gbest作對(duì)比,,如果較好,,則選擇其作為當(dāng)前最優(yōu)位置,,即更新全局極值。
(5)根據(jù)式(1),、式(2)對(duì)粒子位置和速度進(jìn)行更新,,產(chǎn)生新的種群。
(6)如果迭代次數(shù)達(dá)到終止條件,,則停止迭代,,算法終止;未達(dá)到約束條件時(shí)轉(zhuǎn)到步驟(2),,且粒子數(shù)加1,。
根據(jù)上述步驟得出如圖3所示流程圖[15-16]。
2.3.3 仿真結(jié)果
基于PSO算法在MATLAB中進(jìn)行路徑仿真,,結(jié)果如圖4,,其中障礙物的布置同人工勢(shì)場(chǎng)法,邊界的限定為[1,,11],。
3 3種算法的特性對(duì)比
通過(guò)tic和t=toc得出算法運(yùn)行時(shí)間,通過(guò)對(duì)坐標(biāo)進(jìn)行統(tǒng)計(jì)運(yùn)算計(jì)算出距離的大小,,結(jié)果如表1,。
從表中可得出如下結(jié)論:
(1)地圖相同的前提下,粒子群算法由于需要進(jìn)行多次迭代,,因此所用的時(shí)間相對(duì)于其他兩種算法很大,,而由其得到的路徑非最短路徑。
(2)地圖相同的前提下,,A*搜索算法僅進(jìn)行其局部范圍的最優(yōu)規(guī)劃,,因此得出的路徑不是最短,而其時(shí)間相對(duì)于粒子群算法也小很多,。
(3)人工勢(shì)場(chǎng)法在路徑長(zhǎng)短和時(shí)間上最優(yōu),。
4 粒子群算法的改進(jìn)
由于粒子群算法是群智能算法的一種,相對(duì)于其他兩種算法雖然存在一定缺陷,,但也是未來(lái)智能行業(yè)的一大支點(diǎn),,因此作為一種智能算法,提升空間很大,。本文通過(guò)一種改進(jìn)方法來(lái)提升粒子群算法的仿真時(shí)間,,同時(shí)優(yōu)化其路徑。
通過(guò)對(duì)其各個(gè)程序的調(diào)用發(fā)現(xiàn),,仿真時(shí)間與粒子群算法自身處理程序有關(guān),,仿真時(shí)間占所有時(shí)間的15%,仿真時(shí)間主要是在調(diào)用算法的過(guò)程中,,因此需要對(duì)算法參數(shù)進(jìn)行改進(jìn),。
采用中期隨機(jī)的慣性權(quán)重,,把w分為分段函數(shù)的判斷形式進(jìn)行粒子全局尋優(yōu),彌補(bǔ)了傳統(tǒng)的后期隨機(jī)的慣性權(quán)重的缺陷,。提出在搜索中期采用(0.2,,0.8)均勻分布的隨機(jī)慣性權(quán)重,使用中期隨機(jī)的慣性權(quán)重,。
當(dāng)it<0.2·MaxIt時(shí),慣性權(quán)重取值:
式中,,MaxIt為最大迭代次數(shù),,It為當(dāng)前迭代次數(shù),wmax=0.9為最大慣性權(quán)重,,wmin=0.4為最小慣性權(quán)重,。
中期隨機(jī)的慣性權(quán)重具有一定優(yōu)勢(shì),當(dāng)前期搜索不到最優(yōu)解時(shí),,在搜索中期時(shí)不至于陷入局部最優(yōu),,因此減弱粒子群算法對(duì)迭代次數(shù)的依賴(lài),弱化了最大迭代次數(shù)對(duì)算法的過(guò)度依賴(lài),。當(dāng)最大迭代次數(shù)過(guò)大或過(guò)小時(shí),,對(duì)算法的早熟收斂和最優(yōu)解的準(zhǔn)確度的影響減弱。改善粒子群慣性權(quán)重的選擇方式,,減少搜索中期出現(xiàn)的過(guò)早收斂或者陷入早熟的陷阱中,。因此中期隨機(jī)即保證了隨機(jī)搜索的能力,又保證了收斂速度,。
決定粒子群算法的參數(shù)還有學(xué)習(xí)因子C1,、C2,粒子群在搜索過(guò)程中,,需要前段速度大,,防止其過(guò)早成熟而陷入局部收斂,因此C1取大值,,C2取小值,。在搜索后期,由于其逐漸向全局最優(yōu)靠近,,因此需要弱化其全局搜索的能力,,增強(qiáng)局部搜索的能力,從而減少仿真時(shí)間,,因此C1取小值,,C2取大值。
其分段公式如下:
其中,,x=Itπ/MaxIt,。當(dāng)1≤It≤0.47MaxIt時(shí),,C1>C2;當(dāng)0.47MaxIt≤It≤MaxIt時(shí),,C1<C2,。
通過(guò)對(duì)慣性權(quán)重和學(xué)習(xí)因子參數(shù)進(jìn)行改進(jìn),仿真時(shí)間為119.62 s,,規(guī)劃路徑長(zhǎng)度為12.55 m,,在提升仿真時(shí)間和路徑上有一定的效果。通過(guò)雙重參數(shù)的調(diào)節(jié),,保證局部搜索和全局搜索能力的均衡,,也保證自身認(rèn)知和社會(huì)認(rèn)知的均衡化。相比于傳統(tǒng)固定參數(shù)和僅僅改變一種參數(shù)的結(jié)果,,本仿真效果有很大的改善,。
本文通過(guò)求Shubert函數(shù)的最小值對(duì)以上理論進(jìn)行驗(yàn)證對(duì)比,選擇Shubert函數(shù)的原因是由于其具有很多局部最優(yōu)解,,這里把多元多峰函數(shù)變成單元多峰函數(shù)進(jìn)行其最小值的求解,,通過(guò)此函數(shù)得出最小值的驗(yàn)證更能證明改進(jìn)后的粒子群算法的效果,其具體數(shù)據(jù)如表2所示,。從表中可看出,,經(jīng)過(guò)兩種參數(shù)改進(jìn)后的粒子群算法在收斂到極小值時(shí)的收斂速度更快、更準(zhǔn)確,。
5 結(jié)論
自動(dòng)規(guī)劃路徑的核心是選取最優(yōu)算法,,在復(fù)雜地圖中,智能算法不一定比普通搜索算法強(qiáng),,而是要通過(guò)具體的地圖進(jìn)行判斷,。當(dāng)然智能算法是人類(lèi)科技發(fā)展的方向,通過(guò)對(duì)其各項(xiàng)參數(shù)進(jìn)行改進(jìn)后得出的路徑長(zhǎng)度有了很大的提高,,其路徑通過(guò)不斷迭代得出的結(jié)果非常理想,。其他智能算法,如遺傳算法[17],、蟻群算法[18]等也各具特性,。
參考文獻(xiàn)
[1] 吳初娜.駕駛?cè)藨?yīng)激反應(yīng)能力評(píng)估研究[D].西安:長(zhǎng)安大學(xué),2011:30-40.
[2] 胡愛(ài)軍,,王朝暉.汽車(chē)主動(dòng)安全技術(shù)[J].機(jī)械設(shè)計(jì)與制造,,2010,48(7):97-99.
[3] 季榮濤,,周獻(xiàn)中,,王慧平,等.基于Lyapunov法和勢(shì)場(chǎng)法的對(duì)峙跟蹤研究[J].火力與指揮控制,,2016,,54(4):66-69.
[4] 許源.結(jié)合粒子群算法和改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人混合路徑規(guī)劃[D].杭州:浙江大學(xué),,2013.
[5] 錢(qián)森,訾斌.多起重協(xié)作吊裝避障路徑規(guī)劃研究[J].機(jī)械設(shè)計(jì)與制造,,2015(10):260-263.
[6] 祝雪芬,,涂剛毅.基于軌跡安全性評(píng)價(jià)的免疫遺傳路徑規(guī)劃算法[J].計(jì)算機(jī)應(yīng)用研究,2013,,30(2):354-356.
[7] 何海洋.工業(yè)機(jī)器人無(wú)碰軌跡規(guī)劃算法研究[D].廣州:華南理工大學(xué),,2014.
[8] 楊龍祥.基于反應(yīng)式的人工勢(shì)場(chǎng)發(fā)機(jī)器人路徑規(guī)劃[D].成都:西華大學(xué),2014.
[9] 張煌輝.基于動(dòng)態(tài)人工勢(shì)場(chǎng)的路徑規(guī)劃研究與應(yīng)用[D].長(zhǎng)沙:長(zhǎng)沙理工大學(xué),,2010.
[10] 劉秀松.車(chē)輛避障駕駛控制方法研究[J].計(jì)算機(jī)工程與應(yīng)用,,2012,48(2):230-234.
[11] 鄧順平,,張艷軍,劉會(huì)平.一種基于威脅勢(shì)場(chǎng)的A星路徑規(guī)劃算法[J].科技視界,,2014,,4(3):6,22.
[12] 郭強(qiáng).基于改進(jìn)的A星算法和B樣條函數(shù)的仿生機(jī)器魚(yú)路徑規(guī)劃研究[D].天津:天津大學(xué),,2012.
[13] 張萬(wàn)緒,,張向蘭,李瑩.基于改進(jìn)粒子群算法的智能機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用,,2014,,34(2):510-513.
[14] 吳斌.車(chē)輛路徑問(wèn)題的粒子群算法研究與應(yīng)用[D].杭州:浙江工業(yè)大學(xué),2008.
[15] 劉關(guān)俊.基于粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[D].長(zhǎng)沙:中南大學(xué),,2007.
[16] 王亞春.移動(dòng)機(jī)器人路徑規(guī)劃算法研究[D].天津:天津理工大學(xué),,2015.
[17] 禹建麗,成元洋之,Valeri.Kroumov.無(wú)人駕駛農(nóng)用運(yùn)輸車(chē)路徑規(guī)劃研究[J].拖拉機(jī)與農(nóng)用運(yùn)輸車(chē),,2002,,29(4):22-24.
[18] 卜新蘋(píng),蘇虎,,鄒偉,,等.基于復(fù)雜環(huán)境非均勻建模的蟻群路徑規(guī)劃[J].機(jī)器人,2016,,38(3):276-284.