基于改進(jìn)A星算法的無(wú)人車(chē)路徑規(guī)劃研究

繆殷俊　施衛(wèi)

關(guān)鍵詞：無(wú)人車(chē)避障路徑規(guī)劃；改進(jìn)Ａ星算法；關(guān)鍵節(jié)點(diǎn)優(yōu)化

中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2024）03-0004-04

0 引言

路徑規(guī)劃是無(wú)人車(chē)智能駕駛技術(shù)中非常核心的一門(mén)技術(shù)[1]，無(wú)人車(chē)需要按照預(yù)定的地圖到達(dá)指定目的地，在相對(duì)應(yīng)的地圖上進(jìn)行路徑規(guī)劃，需要相應(yīng)的路徑規(guī)劃算法，而常用的全局路徑規(guī)劃算法有很多種，比如：Dijkstra算法[2]、A星算法[3]、蟻群算法[4]等。其中，A星算法是一種較經(jīng)典啟發(fā)式搜索算法，被廣泛應(yīng)用在全局路徑規(guī)劃中[5]。傳統(tǒng)的A星尋路算法是用于解決靜態(tài)環(huán)境中最優(yōu)路徑的直接搜索算法，其廣泛應(yīng)用于室內(nèi)無(wú)人車(chē)路徑搜索，是在Dijkstra算法的基礎(chǔ)上結(jié)合了廣度優(yōu)先搜索算法（BFS）[6]。因此，為了能使無(wú)人車(chē)在柵格化的電子地圖中規(guī)劃出較優(yōu)的路徑，以安全高效的速度抵達(dá)目標(biāo)點(diǎn)，本文提出了一種基于優(yōu)化改進(jìn)A星算法的路徑規(guī)劃算法，具體的，優(yōu)化改進(jìn)的過(guò)程如下：首先，對(duì)傳統(tǒng)的A星算法進(jìn)行改進(jìn)，對(duì)A星算法的評(píng)價(jià)函數(shù)進(jìn)行改進(jìn)，優(yōu)化啟發(fā)函數(shù)h（n）加入權(quán)重系數(shù)，使得搜索效率提高，搜索鄰域優(yōu)化，優(yōu)化搜索方向?qū)⒍嘤嗟乃阉鞣较蛱蕹詼p少遍歷節(jié)點(diǎn)數(shù)目，提高搜索效率，其次，對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行優(yōu)化處理，刪除多余節(jié)點(diǎn)，減少路徑上的冗余節(jié)點(diǎn)和轉(zhuǎn)折點(diǎn)，提高算法的運(yùn)行效率，提高路徑的平滑度，然后，對(duì)柵格地圖進(jìn)行優(yōu)化，將地圖中的障礙物進(jìn)行膨脹處理，提高安全性能，并將優(yōu)化后的算法與原先的算法進(jìn)行實(shí)際分析比較，最終實(shí)現(xiàn)無(wú)人車(chē)的路徑規(guī)劃。

1 優(yōu)化A星算法

1.1 環(huán)境地圖構(gòu)建

在對(duì)無(wú)人車(chē)進(jìn)行全局路徑規(guī)劃時(shí)，首先需要建立一個(gè)可以完整表達(dá)地圖環(huán)境信息的環(huán)境地圖，然后在構(gòu)建好的環(huán)境地圖上規(guī)劃出一條滿足要求的最優(yōu)路徑。而在常用環(huán)境地圖構(gòu)建的方法中，一般采用柵格地圖，因?yàn)闁鸥竦貓D具有簡(jiǎn)單有效、易于實(shí)現(xiàn)的特點(diǎn)，而且可以通過(guò)改變柵格大小來(lái)改變環(huán)境的分辨率，也可以展示出各種不同形狀，大小的障礙物。

本文采用柵格法進(jìn)行環(huán)境地圖的構(gòu)建，構(gòu)建的柵格地圖如圖1所示。

如圖1所示，構(gòu)建一個(gè)大小為10×10的柵格地圖，在圖中標(biāo)注出無(wú)人車(chē)的起始點(diǎn)s，目標(biāo)點(diǎn)g。

1.2 傳統(tǒng)A星算法

傳統(tǒng)的A星算法基于代價(jià)函數(shù)在電子地圖中規(guī)劃全局路徑，是最有效的求解全局路徑的啟發(fā)式搜索方法，是貪心算法和Dijkstra算法的結(jié)合[7]，其基本的表達(dá)式為：

f （n） = g （n） + h （n） （1）

式中：f（n）表示為當(dāng)前節(jié)點(diǎn)的總代價(jià)，g（n）當(dāng)前節(jié)點(diǎn)與起點(diǎn)的實(shí)際代價(jià)，h（n）為當(dāng)前節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)的預(yù)估代價(jià)。

啟發(fā)函數(shù)h（n）的選擇對(duì)于A星算法的搜索效率有著重要的影響。通常啟發(fā)函數(shù)h（n）的選擇有曼哈頓距離、歐幾里得距離、切比雪夫距離3種。

歐幾里得距離是這3種距離當(dāng)中運(yùn)算量最大的，但是求得的路徑質(zhì)量是最好的，所以本文采用歐幾里得距離來(lái)計(jì)算節(jié)點(diǎn)的估計(jì)代價(jià)h（n），歐幾里得距離的公式為：

傳統(tǒng)A星算法的基本步驟如下：

第1步：建立open列表與close列表，將起點(diǎn)放入open列表中，close列表為空。

第2步：遍歷起點(diǎn)周?chē)墓?jié)點(diǎn)，計(jì)算出他們的評(píng)價(jià)函數(shù)f，將它們放入open列表中，將open列表中評(píng)價(jià)函數(shù)f最小的節(jié)點(diǎn)從open列表中移除，并將其加入close 列表中。如果open列表中沒(méi)有節(jié)點(diǎn)，則尋路失?。蝗绻?dāng)前節(jié)點(diǎn)為終點(diǎn)，則尋路結(jié)束，并將終點(diǎn)的前置節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)，然后返回由當(dāng)前節(jié)點(diǎn)到起點(diǎn)的路徑。

第3步：遍歷當(dāng)前節(jié)點(diǎn)的周?chē)?jié)點(diǎn)。如果鄰接點(diǎn)在close列表中，則不作處理；若有鄰接點(diǎn)為障礙物，則不予考慮；如果鄰接點(diǎn)不在open列表中，則更新其評(píng)價(jià)函數(shù)中的g（n），h（n），并計(jì)算出評(píng)價(jià)函數(shù)f（n），再將其放入open列表中；如果鄰接點(diǎn)已經(jīng)在open列表中，則比較從當(dāng)前節(jié)點(diǎn)到這個(gè)鄰接點(diǎn)的實(shí)際損耗g（n）是否比這個(gè)點(diǎn)原來(lái)的實(shí)際損耗g（n）更優(yōu)，如果不更優(yōu)，則不作處理；如果更優(yōu)，則將鄰接點(diǎn)的實(shí)際損耗g（n）更新為更優(yōu)值，并將鄰接點(diǎn)現(xiàn)在的評(píng)價(jià)函數(shù)f（n）取代之前的f（n）。

第4步：回到第3步，繼續(xù)處理當(dāng)前節(jié)點(diǎn)周?chē)南乱粋€(gè)鄰接點(diǎn)。

第5步：重復(fù)以上步驟，直至擴(kuò)展到目標(biāo)節(jié)點(diǎn)或open列表為空，若非空，則回到第2步繼續(xù)循環(huán)，最終將close列表中的節(jié)點(diǎn)依次連接，生成路徑。

傳統(tǒng)A*算法流程圖如圖2所示。

1.3 優(yōu)化啟發(fā)函數(shù)

傳統(tǒng)A星算法存在一些問(wèn)題，比如：冗余節(jié)點(diǎn)過(guò)多，存在重復(fù)訪問(wèn)不必要節(jié)點(diǎn)的情況；路徑不平滑問(wèn)題，會(huì)產(chǎn)生較多的轉(zhuǎn)折點(diǎn)，降低了路徑的順滑度；搜索范圍較大，出現(xiàn)不必要的搜索范圍，降低搜索速度；最終規(guī)劃出的路線不太符合實(shí)際用途，與障礙物距離較近，易發(fā)生事故風(fēng)險(xiǎn)。因此，本文采用動(dòng)態(tài)權(quán)重的方法，通過(guò)動(dòng)態(tài)調(diào)整啟發(fā)函數(shù)的權(quán)重系數(shù)來(lái)提高搜索效率，提高算法的地圖適應(yīng)性。

h（n）的選取是規(guī)劃最優(yōu)路徑的關(guān)鍵[8]，若h（n）小于g（n），雖然此時(shí)的路徑是最小代價(jià)路徑，但是搜索節(jié)點(diǎn)會(huì)變多，范圍會(huì)變大，搜索時(shí)間變長(zhǎng)，效率低下；若h（n） 大于g（n），則搜索的速度會(huì)大幅提升，但此時(shí)的路徑可能不是最優(yōu)解；因此考慮在初期增加h（n）值，提高搜索速度；當(dāng)當(dāng)前節(jié)點(diǎn)的位置接近終點(diǎn)時(shí)，實(shí)際代價(jià)值g（n） 與估計(jì)代價(jià)值h（n）大小接近，此時(shí)的執(zhí)行效率處在最優(yōu)的情況；當(dāng)障礙物數(shù)量占比較多時(shí)，動(dòng)態(tài)減小搜索速度，確保尋得路徑的精度，提高安全性能，通過(guò)減少h（n）的權(quán)重系數(shù)來(lái)處理。當(dāng)障礙物占比較少時(shí)，應(yīng)加快搜索速度，如果按照傳統(tǒng)A星算法的h（n）尋找最優(yōu)路徑，會(huì)導(dǎo)致搜索節(jié)點(diǎn)過(guò)多，搜索效率降低，此時(shí)加大h（n）的權(quán)重系數(shù)。因此，改進(jìn)后的啟發(fā)函數(shù)如式（3） 所示：

式中，P 表示起始點(diǎn)與目標(biāo)點(diǎn)之間的障礙率，d 為此時(shí)所在節(jié)點(diǎn)n 距離目標(biāo)點(diǎn)的長(zhǎng)度；D 為起始點(diǎn)距離目標(biāo)點(diǎn)的距離長(zhǎng)度。

圖3為采用傳統(tǒng)A星算法規(guī)劃的路徑和遍歷的節(jié)點(diǎn)。

1.4 搜索鄰域優(yōu)化

傳統(tǒng)的A星算法在進(jìn)行相應(yīng)的節(jié)點(diǎn)搜索時(shí)會(huì)擴(kuò)展以當(dāng)前節(jié)點(diǎn)為中心的相鄰8個(gè)柵格[9]，如圖4所示，節(jié)點(diǎn)1～8為當(dāng)前可探索的所有節(jié)點(diǎn)方向，因?yàn)樵趯?shí)際的無(wú)人車(chē)運(yùn)動(dòng)時(shí)，目標(biāo)點(diǎn)的方位已經(jīng)確定了，在知曉目標(biāo)點(diǎn)方位的情況下，如果還對(duì)八個(gè)方向都進(jìn)行相應(yīng)的節(jié)點(diǎn)搜索就會(huì)花費(fèi)更多時(shí)間，遍歷更多的節(jié)點(diǎn)，導(dǎo)致搜索效率的下降，在實(shí)際的搜索過(guò)程當(dāng)中，有些方向是根本運(yùn)用不到的，需要將這些多余的方向剔除掉。根據(jù)上述問(wèn)題，本文提出一種根據(jù)目標(biāo)點(diǎn)的方位，在搜索過(guò)程中只使用其中的5個(gè)方向的方法，假設(shè)目標(biāo)點(diǎn)與當(dāng)前節(jié)點(diǎn)的連線與節(jié)點(diǎn)2的指示方向的夾角度數(shù)為θ，則保留與舍棄方向的規(guī)則如表1所示。

1.5 優(yōu)化關(guān)鍵節(jié)點(diǎn)

由圖3可知，本文的傳統(tǒng)的A星算法在路徑規(guī)劃的過(guò)程中會(huì)產(chǎn)生有較多的轉(zhuǎn)折點(diǎn)，轉(zhuǎn)折點(diǎn)越多，則越不利于無(wú)人車(chē)的運(yùn)動(dòng)，無(wú)人車(chē)的工作效率就會(huì)降低，并且容易出現(xiàn)與障礙物發(fā)生碰撞、刮蹭的行為。針對(duì)上述的問(wèn)題，本文將對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行優(yōu)化提取，將路徑規(guī)劃過(guò)程中的拐點(diǎn)數(shù)目減少，優(yōu)化關(guān)鍵節(jié)點(diǎn)的相關(guān)步驟如下：

第1步：在算法遍歷節(jié)點(diǎn)的過(guò)程中會(huì)得到相應(yīng)的節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)目為n₁，n₂，…，n_z個(gè)，設(shè)立一個(gè)集合U用于存放全部遍歷的節(jié)點(diǎn)，集合V用于存放關(guān)鍵節(jié)點(diǎn)。將得到的全部節(jié)點(diǎn)都存入到節(jié)點(diǎn)集U{n_i，1≤i≤z}，其中n₁表示路徑的起點(diǎn)，n_z表示路徑的終點(diǎn)。將關(guān)鍵節(jié)點(diǎn)集V進(jìn)行相應(yīng)的初始化，以滿足后面的應(yīng)用需求，關(guān)鍵節(jié)點(diǎn)集V中存入起點(diǎn)n₁和終點(diǎn)n_z。

第2步：將n1依次與n₂，n₃，n₄，…，nm連接，判斷連接之后所產(chǎn)生的線路是否出現(xiàn)穿過(guò)障礙物的情況，當(dāng)n₁nm是第一條穿過(guò)障礙物的直線，則n_m的前一個(gè)節(jié)點(diǎn)n_m-1作為路徑優(yōu)化過(guò)程中的關(guān)鍵節(jié)點(diǎn)，將節(jié)點(diǎn)n_m-1添加到關(guān)鍵節(jié)點(diǎn)集V中，并且將n₁與n_m-1之間的節(jié)點(diǎn)判定為冗余節(jié)點(diǎn)。隨后以同樣的方式進(jìn)行判斷，即從n_m開(kāi)始依次連接后面的節(jié)點(diǎn)，并判斷是否穿過(guò)障礙物，如果穿過(guò)就按照之前的處理步驟，將穿過(guò)障礙物的點(diǎn)的前一個(gè)節(jié)點(diǎn)設(shè)置為關(guān)鍵節(jié)點(diǎn)，并存入關(guān)鍵節(jié)點(diǎn)集V 中，一直到連接到終點(diǎn)n_z結(jié)束。

第3步：步驟二中得到了路徑中的所有關(guān)鍵節(jié)點(diǎn)，將這些關(guān)鍵節(jié)點(diǎn)依次連接起來(lái)，最終所得到的路徑即為提取關(guān)鍵節(jié)點(diǎn)后的路徑。

圖5為優(yōu)化示例圖：

1.6 障礙物膨脹處理

通過(guò)觀察圖3的傳統(tǒng)A星算法路徑規(guī)劃圖可以發(fā)現(xiàn)，在經(jīng)過(guò)一些障礙物時(shí)，傳統(tǒng)A星算法是貼著障礙物的邊緣走的，這顯然不符合無(wú)人車(chē)實(shí)際運(yùn)動(dòng)要求，因?yàn)闊o(wú)人車(chē)本身存在自身寬度，在路徑規(guī)劃過(guò)程中，按照一般路徑規(guī)劃算法所規(guī)劃出的路徑有時(shí)會(huì)出現(xiàn)無(wú)人車(chē)與障礙物發(fā)生碰撞、刮蹭的情況，所以需要先對(duì)障礙物進(jìn)行膨脹處理，膨脹范圍為無(wú)人車(chē)的車(chē)身寬度d。在路徑規(guī)劃完之后再將障礙物縮小成原來(lái)的大小，從而很好地避免在無(wú)人車(chē)運(yùn)動(dòng)拐彎的時(shí)候與障礙物發(fā)生碰撞、刮蹭的情況，圖6為障礙物膨脹處理示意圖。

2 仿真實(shí)驗(yàn)與分析

2.1 改進(jìn)A 星算法仿真分析

仿真實(shí)驗(yàn)在MATLAB R2022B環(huán)境下進(jìn)行，為驗(yàn)證改進(jìn)后算法的有效性以及適應(yīng)性。分別采用傳統(tǒng)A星算法與優(yōu)化改進(jìn)后的A星算法進(jìn)行路徑規(guī)劃實(shí)驗(yàn)分析，為了保證有較好的對(duì)比效果，改進(jìn)Ａ星算法的仿真結(jié)果如圖7所示，傳統(tǒng)A星算法與改進(jìn)優(yōu)化后的A星算法的對(duì)比圖，如圖8所示，傳統(tǒng)A星算法與改進(jìn)優(yōu)化后的A星算法的數(shù)據(jù)性能比較如表2所示。

由表2中的實(shí)驗(yàn)數(shù)據(jù)可知，經(jīng)過(guò)改進(jìn)優(yōu)化后的A 星算法與傳統(tǒng)A星算法的路徑相比要更優(yōu)，算法的探索規(guī)劃時(shí)間更短，速度更快，相比于傳統(tǒng)的A星算法的規(guī)劃時(shí)間結(jié)果，改進(jìn)優(yōu)化后的A星算法的規(guī)劃時(shí)間減少了28.25%，遍歷節(jié)點(diǎn)總數(shù)減少了27.12%，路徑長(zhǎng)度從14.188 6縮短到了14.071 1，優(yōu)化了0.83%；拐點(diǎn)數(shù)從5次變?yōu)榱?次，優(yōu)化了40%。

因此，本文的改進(jìn)A星算法可以提高傳統(tǒng)A星算法的效率。

3 結(jié)束語(yǔ)

本文主要針對(duì)傳統(tǒng)A星算法的路徑規(guī)劃過(guò)程中出現(xiàn)的一些問(wèn)題進(jìn)行優(yōu)化處理，比如：拐點(diǎn)過(guò)多、冗余節(jié)點(diǎn)多、容易發(fā)生碰撞、效率低，路徑非最優(yōu)解。本文對(duì)傳統(tǒng)的A星算法進(jìn)行改進(jìn)。在全局路徑規(guī)劃方面，首先，通過(guò)對(duì)h（n）進(jìn)行改進(jìn)加入權(quán)重系數(shù)，然后，對(duì)搜索鄰域進(jìn)行優(yōu)化，剔除多余的方向，其次，使用關(guān)鍵點(diǎn)提取策略去除冗余節(jié)點(diǎn)，最后，對(duì)路徑過(guò)程中的障礙物進(jìn)行膨脹處理以避免無(wú)人車(chē)在路徑規(guī)劃中過(guò)度靠近障礙物產(chǎn)生碰撞風(fēng)險(xiǎn)。通過(guò)對(duì)傳統(tǒng)A星算法與優(yōu)化改進(jìn)后的A星算法進(jìn)行仿真實(shí)驗(yàn)分析，并對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行相應(yīng)的比較，驗(yàn)證出本文改進(jìn)優(yōu)化后的A星算法的性能相比于傳統(tǒng)的A星算法要更好，路徑搜索的效率更高。但是只做全局路徑規(guī)劃還是不夠的，即使應(yīng)用在無(wú)人車(chē)上也不能很好地保障實(shí)際運(yùn)行過(guò)程中的安全、高效。今后筆者將考慮局部路徑規(guī)劃的問(wèn)題，對(duì)局部路徑規(guī)劃進(jìn)行相應(yīng)的算法優(yōu)化，將優(yōu)化后的局部路徑規(guī)劃算法與優(yōu)化改進(jìn)后的A星算法進(jìn)行融合，并進(jìn)行相應(yīng)的實(shí)驗(yàn)分析，以進(jìn)一步驗(yàn)證該優(yōu)化融合之后的算法在實(shí)際場(chǎng)景中進(jìn)行路徑規(guī)劃時(shí)的有效性。

【通聯(lián)編輯：唐一東】