針對目前智能汽車路徑規(guī)劃存在A^*算法規(guī)劃的路徑精度高卻搜索耗時(shí)長、搜索耗時(shí)短但精度差的矛盾問題,提出了一種既保證搜索效率又可提高路徑精度的混合連接SA算法.在原有連接方式的基礎(chǔ)上,提出了一種新型的連接方式和S算法,設(shè)計(jì)了混合SA算法的切換機(jī)制,確保了SA算法可獲取保證搜索效率的次優(yōu)路徑.進(jìn)行了路徑規(guī)劃單一地圖仿真試驗(yàn),驗(yàn)證了SA算法在不同的單一環(huán)境地圖中,重復(fù)規(guī)劃的路徑具有一致性、耗時(shí)具有一定局限性;同時(shí)進(jìn)行了路徑規(guī)劃普適性仿真試驗(yàn),對比分析了混合連接SA算法與四連接A^*算法的各項(xiàng)性能指標(biāo).結(jié)果表明:在全局工況下,SA算法相比于四連接A^*算法,在保證搜索耗時(shí)優(yōu)勢的同時(shí),提高了規(guī)劃路徑精度,尤其是在低百分比障礙物地圖下,效果更為明顯. 

【文章來源】：江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版). 2019,40(03)北大核心

【文章頁數(shù)】：6 頁

【部分圖文】：

環(huán)境地圖模型1．2A*算法的基本原理

?肪豆婊?四連接A*算法基于擴(kuò)展子節(jié)點(diǎn)數(shù)目少的擴(kuò)展特點(diǎn)，搜索速度快，但由于OPEN表中的可選擇子節(jié)點(diǎn)數(shù)目少，不考慮對角子節(jié)點(diǎn)間的連接關(guān)系，導(dǎo)致路徑精度不足的問題．綜上所述，在四連接A*算法的基礎(chǔ)上，采用混合連接的節(jié)點(diǎn)方式和基于啟發(fā)式函數(shù)的S算法．通過切換算法的方式，在保證了搜索效率的同時(shí)，盡可能提高路徑精度．2．1混合連接的節(jié)點(diǎn)方式路徑搜索時(shí)，四連接的狀態(tài)節(jié)點(diǎn)間由四連接關(guān)系組成，如圖2a所示．八連接的狀態(tài)節(jié)點(diǎn)間由八連接關(guān)系組成，如圖2b所示．圖2連接示意圖八連接從當(dāng)前節(jié)點(diǎn)可以與它相鄰的周圍8個(gè)節(jié)點(diǎn)連接，但是到達(dá)相鄰節(jié)點(diǎn)的真實(shí)代價(jià)不等．如圖2a所示，到達(dá)的4個(gè)直節(jié)點(diǎn)的方式簡稱為直連接方式．中間父節(jié)點(diǎn)s到直連接子節(jié)點(diǎn)s'的真實(shí)代價(jià)為c(s，s')=1．(6)如圖2b所示，到達(dá)的4個(gè)斜節(jié)點(diǎn)的方式簡稱為斜連接方式．s節(jié)點(diǎn)到斜連接子節(jié)點(diǎn)s″的真實(shí)代價(jià)為c(s，s″)=槡2．(7)目前主流算法，例如Dijkstra算法、BFS算法、A*算法及衍生出的WeightedA*算法等均采用單一的連接方式來進(jìn)行路徑搜索，如采用四連接的方式進(jìn)行搜索，當(dāng)處理低百分比障礙物的環(huán)境地圖時(shí)，雖然搜索耗時(shí)較短，但路徑精度較低;如采用八連接的方式進(jìn)行搜索，由于擴(kuò)展子節(jié)點(diǎn)較多，OPEN表中排序耗時(shí)冗長，雖然路徑精度較高，但搜索耗時(shí)較長．故提出一種新型的混合連接方式，其主要實(shí)現(xiàn)方法為根據(jù)當(dāng)前節(jié)點(diǎn)的障礙物環(huán)境，S算法采用八連接、A*算法采用四連接的方式進(jìn)行切換搜索．2．2SA算法的實(shí)現(xiàn)SA算法主要流程大體分為2個(gè)階段:①開始階段，將起始節(jié)點(diǎn)放?

252第40卷OPEN表及CLOSED表中，并采取相應(yīng)的操作，SA算法核心擴(kuò)展部分流程如圖4所示．其中，Direction數(shù)組為保存有Left，Ｒight，Up，Down，LeftUp，Ｒight-Up，LeftDown，ＲightDown這8個(gè)方位的二維數(shù)組;q為切換算法時(shí)檢測的值;jcw為是否需要進(jìn)行8方位檢測的檢測位值;fmin為設(shè)置的初始f值，用于比較各個(gè)節(jié)點(diǎn)的f值大小;as為確定的數(shù)組方向位值;Dtime為需要進(jìn)行S算法的次數(shù)．圖4SA算法核心擴(kuò)展部分流程圖5)運(yùn)用經(jīng)典A*算法進(jìn)行相應(yīng)擴(kuò)展，同時(shí)判斷擴(kuò)展到的節(jié)點(diǎn)是否在OPEN表中，并進(jìn)一步進(jìn)行處理，具體操作如圖5所示．其中，OLD表示原始最佳節(jié)點(diǎn)．圖5四連接A*算法擴(kuò)展流程圖2．3SA算法的可行性分析SA算法相比于四連接A*算法，在相對寬裕的自由空間采用S算法，故擴(kuò)展子節(jié)點(diǎn)存在斜連接及直連接2種方式．假定在某個(gè)已知的環(huán)境地圖中，如圖2所示的斜連接共進(jìn)行了m次(m為非負(fù)整數(shù))，則SA算法從初始節(jié)點(diǎn)到任意節(jié)點(diǎn)n的真實(shí)代價(jià)消耗為g(n)*=∑k－1i=startcost*(ni，ni+1)，k≤goal，可得g(n)*=(k－m－1)c(s，s')+mc(s，s″)．(8)而四連接A*算法從初始節(jié)點(diǎn)到任意節(jié)點(diǎn)n的真實(shí)代價(jià)消耗為g(n)=(k－m－1+2m)c(s，s')．(9)由式(6)－(9)易證:g(n)*≤g(n)．(10)由式(10)可知:SA算法規(guī)劃出的路徑長度不

【參考文獻(xiàn)】：
期刊論文
[1]基于改進(jìn)A*算法的電動(dòng)車能耗最優(yōu)路徑規(guī)劃[J]. 顧青,豆風(fēng)鉛,馬飛.  農(nóng)業(yè)機(jī)械學(xué)報(bào). 2015(12)
[2]基于平滑A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 王紅衛(wèi),馬勇,謝勇,郭敏.  同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版). 2010(11)
[3]基于改進(jìn)蟻群算法的飛機(jī)低空突防航路規(guī)劃(英文)[J]. 葉文,馬登武,范洪達(dá).  Chinese Journal of Aeronautics. 2005(04)



本文編號(hào)：3096565