董曉東，李 剛，宗長富，李永明，李云龍，李 祥

（1.遼寧工業(yè)大學(xué)汽車與交通工程學(xué)院，遼寧 錦州 121001；2.吉林大學(xué)汽車仿真與控制國家重點(diǎn)實(shí)驗(yàn)室，長春 130022）

0 引言

無人駕駛技術(shù)是指利用機(jī)器人替代人類在工業(yè)、交通、物流、醫(yī)療、軍事等領(lǐng)域中完成各種工作任務(wù)。實(shí)現(xiàn)無人駕駛最重要的環(huán)節(jié)之一就是路徑規(guī)劃，目標(biāo)是通過搜索尋找最佳路徑，連接起點(diǎn)和終點(diǎn)［1］。目前，無人駕駛路徑規(guī)劃研究主要分為2類：一類是基于車輛動(dòng)力學(xué)模型，采用運(yùn)動(dòng)學(xué)優(yōu)化的方法進(jìn)行路徑規(guī)劃；另一類是基于全局環(huán)境建模和動(dòng)態(tài)障礙物避障的方法進(jìn)行路徑規(guī)劃［2］。在整個(gè)控制系統(tǒng)中，路徑規(guī)劃環(huán)節(jié)承上啟下，是無人駕駛技術(shù)的核心［3］。

路徑規(guī)劃算法根據(jù)適用的場(chǎng)景分類為全局路徑規(guī)劃和局部路徑規(guī)劃［4］。全局路徑規(guī)劃一般用來生成全局參考軌跡，如傳統(tǒng)Dijkstra算法［5］、A*算法［6］、D*算法［7］、快速擴(kuò)展隨機(jī)樹RRT算法、蟻群算法、粒子群算法、遺傳算法等［8］；局部路徑規(guī)劃一般是在參考路徑的引導(dǎo)下，規(guī)劃出未來短暫時(shí)間段內(nèi)可通行的局部路徑，常見的有動(dòng)態(tài)窗口算法、人工勢(shì)場(chǎng)法、TEB算法等。

雖然A*算法具有較好的求解效率而被用于全局尋優(yōu)，但該尋優(yōu)路線仍面臨著拐點(diǎn)過多、節(jié)點(diǎn)冗余、與障礙間距離過于接近等問題。同時(shí)，如果應(yīng)用動(dòng)態(tài)窗口法（DWA）進(jìn)行路徑規(guī)劃可以使無人駕駛汽車具備良好的避障能力，并生成平滑的路徑，無需額外優(yōu)化。但是，該方法可能會(huì)陷入局部最優(yōu)解，無法按全局最優(yōu)路徑到達(dá)目標(biāo)點(diǎn)。隨著上述問題造成的無人駕駛汽車路徑規(guī)劃局限性越來越大，有的專家學(xué)者對(duì)傳統(tǒng)A*算法進(jìn)行了相應(yīng)改進(jìn)優(yōu)化，克服了上述問題衍生出了各種新的路徑規(guī)劃方法，但需要聯(lián)合全局與局部2種方法［9］；Guruji等［10］提出了一種名為時(shí)效A*的改進(jìn)算法，該算法通過使用斜率檢測(cè)的方式來減少相鄰節(jié)點(diǎn)的搜索次數(shù)，從而提高了算法的效率；姚進(jìn)鑫等［11］提出了一種將跳躍點(diǎn)搜索與動(dòng)態(tài)窗口法相融合的路徑規(guī)劃算法，該方法能較好地克服最優(yōu)A*方法在曲線轉(zhuǎn)彎處存在的曲率不連續(xù)性問題，改善了軌跡的光滑度和整體優(yōu)化；合肥工業(yè)大學(xué)的賈嶼等［12］將A*算法與跳點(diǎn)策略相結(jié)合，給出了一種新的優(yōu)化策略，該策略在提高尋優(yōu)速度和路徑安全性方面取得了顯著的進(jìn)展；重慶理工大學(xué)的尹婉秋等［13］基于A*算法，將人工勢(shì)場(chǎng)法和障礙的位置信息相結(jié)合，利用粒子群算法自適應(yīng)地選取參數(shù)，解決了傳統(tǒng)A*算法“先移后避”的難題，降低了A*算法的計(jì)算復(fù)雜度；重慶理工大學(xué)的李長庚等［14］引入一種雙向交叉搜索策略和基于指數(shù)衰減的啟發(fā)函數(shù)權(quán)重方法，解決了現(xiàn)有A*算法存在搜索時(shí)間長、轉(zhuǎn)彎角度大和曲線不連續(xù)等問題；遼寧工業(yè)大學(xué)的白云龍等［15］提出一種通過擴(kuò)展搜索鄰域的方法來提高A*算法的規(guī)劃效率，并將人工勢(shì)場(chǎng)法融入其中來避障，最后通過3次B樣條曲線平滑路徑中出現(xiàn)的尖銳節(jié)點(diǎn)；海南大學(xué)的田晃等［16］提出了一種基于多目標(biāo)節(jié)點(diǎn)的改進(jìn)動(dòng)態(tài)窗口算法，在提高路徑平滑度的同時(shí)，相對(duì)于傳統(tǒng)算法具有更好的局部避障能力；張振等［17］提出了一種實(shí)時(shí)路徑規(guī)劃方法，該方法將改良的A*算法與動(dòng)態(tài)窗口法相結(jié)合，將經(jīng)過優(yōu)化的關(guān)鍵點(diǎn)作為臨時(shí)目標(biāo)點(diǎn)，能夠生成一條基于全局最優(yōu)的光滑曲線路徑；郭翰卿等［18］在傳統(tǒng)A*算法的評(píng)價(jià)函數(shù)中引入安全估值，通過運(yùn)用改進(jìn)的動(dòng)態(tài)窗口評(píng)價(jià)函數(shù)，成功將安全性A*算法與動(dòng)態(tài)窗口法相融合，實(shí)現(xiàn)了在全局路徑行進(jìn)中的動(dòng)態(tài)避障。

路徑規(guī)劃算法常用于機(jī)器人領(lǐng)域，無人駕駛的路徑規(guī)劃算法受其啟發(fā)［19］。在無人駕駛系統(tǒng)中，路徑規(guī)劃算法作為其關(guān)鍵技術(shù)之一，引起了國內(nèi)外學(xué)者的廣泛關(guān)注，并呈現(xiàn)出百家爭(zhēng)鳴的局面［20］。雖然大部分研究人員對(duì)現(xiàn)有的A*算法、DWA算法作了一定的修改，但是仍然不能徹底解決實(shí)際規(guī)劃中的某些問題?；诖?，本文中對(duì)A*算法進(jìn)行了改進(jìn)，使其可以尋找到最優(yōu)的全局路線節(jié)點(diǎn)，同時(shí)利用動(dòng)態(tài)窗口方法對(duì)鄰近節(jié)點(diǎn)進(jìn)行了局部規(guī)劃。該方法可使無人車在全局路徑中遭遇任意的障礙時(shí)合理繞開障礙，返回到全局路徑，這樣不僅可以保證路徑的整體最優(yōu)性，而且可以有效地克服各種隨機(jī)障礙對(duì)規(guī)劃路徑的影響。

1 算法基礎(chǔ)

1.1 傳統(tǒng)A*算法

A*算法被廣泛應(yīng)用于優(yōu)化路徑的搜索，因?yàn)樗哂懈咝У乃阉餍屎涂焖俚囊?guī)劃速度［21］。A*算法基本思想是從起始柵格點(diǎn)開始，尋找與起點(diǎn)相鄰的子?xùn)鸥顸c(diǎn)。每一次都會(huì)從周圍的子?xùn)鸥顸c(diǎn)中選擇一個(gè)評(píng)估函數(shù)值最小的點(diǎn)作為下一步的搜索節(jié)點(diǎn)，即當(dāng)前節(jié)點(diǎn)。然后，在當(dāng)前節(jié)點(diǎn)的基礎(chǔ)上，生成與其鄰接的子?xùn)鸥顸c(diǎn)，并以目標(biāo)節(jié)點(diǎn)為終點(diǎn)進(jìn)行下一步的搜索。

A*算法的評(píng)價(jià)函數(shù)對(duì)檢索空間的大小有影響，而檢索空間的大小、訪問量反過來又對(duì)A*算法的運(yùn)算速度有影響。所以，A*算法評(píng)價(jià)函數(shù)的優(yōu)劣對(duì)其尋優(yōu)效果及尋優(yōu)效率有著很大的影響。

設(shè)f（n）為A*算法評(píng)價(jià)函數(shù)，公式如下：

式中：f（n）為起始位置到當(dāng)前位置n之間總和的代價(jià)函數(shù)；h（n）為當(dāng)前節(jié)點(diǎn)位置n到目的地位置之間估計(jì)路徑代價(jià)的啟發(fā)函數(shù)［22］。

啟發(fā)函數(shù)的選擇會(huì)影響A*算法的效率和準(zhǔn)確性。如果沒有障礙物阻擋，那么用歐幾里得距離作為啟發(fā)函數(shù)，就能使得估計(jì)路徑和實(shí)際最短路徑一致，這樣算法就能快速而精確地找到目標(biāo)，不會(huì)浪費(fèi)時(shí)間在多余的節(jié)點(diǎn)上。但是在實(shí)際情況中，往往有很多障礙物使得實(shí)際路徑比估計(jì)路徑要長，這時(shí)候算法就會(huì)產(chǎn)生很多冗余節(jié)點(diǎn)，增大了搜索空間，降低了搜索速度［23］。如果能夠調(diào)整啟發(fā)函數(shù)的值，使其接近于實(shí)際路徑的值，就能夠有效地提高搜索效率。由于不同的地圖環(huán)境中障礙物的分布不同，如果能夠?qū)φ系K物進(jìn)行量化，并根據(jù)量化數(shù)據(jù)調(diào)節(jié)啟發(fā)函數(shù)，就能夠提高算法的效率和適應(yīng)性。

針對(duì)傳統(tǒng)A*算法在路徑規(guī)劃中存在的缺陷，本文對(duì)其進(jìn)行了改進(jìn)和優(yōu)化。具體方法如下：

1）通過柵格法對(duì)環(huán)境進(jìn)行建模，并根據(jù)式（9）計(jì)算障礙率P。同時(shí)，設(shè)定無人駕駛汽車的起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，并建立Open列表和Close列表。將起始節(jié)點(diǎn)添加到Open列表中，而Close列表為空。

2）算法開始遍歷起始節(jié)點(diǎn)周圍的節(jié)點(diǎn)，并根據(jù)優(yōu)化后的子節(jié)點(diǎn)選擇方式生成可選子節(jié)點(diǎn)。隨后，將起始節(jié)點(diǎn)從Open列表中移到Close列表中，若Open列表為空，表示不存在待搜索節(jié)點(diǎn)，算法將終止，表明無可行的路徑。

3）若Open列表不為空且存在待搜索節(jié)點(diǎn)，則分別計(jì)算各子節(jié)點(diǎn)的f（n）值，并選取具有最小f（n）值的節(jié)點(diǎn)作為下一個(gè)路徑節(jié)點(diǎn)，同時(shí)將該節(jié)點(diǎn)從Open列表中移到Close列表中。

4）判斷該擴(kuò)展節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)。若為目標(biāo)節(jié)點(diǎn)，則從目標(biāo)節(jié)點(diǎn)開始逆向搜索其父節(jié)點(diǎn)，并對(duì)路徑進(jìn)行雙向平滑度優(yōu)化。最后，輸出規(guī)劃路徑。若非目標(biāo)節(jié)點(diǎn)，則繼續(xù)擴(kuò)展其周圍節(jié)點(diǎn)并計(jì)算子節(jié)點(diǎn)的f（n）值，將不在Close列表中的周圍子節(jié)點(diǎn)添加到Open列表中。

5）重復(fù)步驟4），直至擴(kuò)展到目標(biāo)節(jié)點(diǎn)并輸出最終規(guī)劃路徑。

改進(jìn)A*算法的流程如圖1所示。

圖1 改進(jìn)A*算法流程

1.2 動(dòng)態(tài)窗口（DWA）算法

動(dòng)態(tài)窗口（DWA）法是一種局部動(dòng)態(tài)路徑規(guī)劃算法，它通過對(duì)無人駕駛汽車的位置變化進(jìn)行簡(jiǎn)化，僅考慮線速度和角速度控制。它將避障問題簡(jiǎn)化為空間中的運(yùn)動(dòng)約束問題，從而可以根據(jù)運(yùn)動(dòng)約束條件選擇最佳的局部路徑［24］。假設(shè)一輛無人駕駛汽車在時(shí)間段（t1－t2）內(nèi)運(yùn)動(dòng)，那么它對(duì)應(yīng)的位姿變化信息如下：

式中：xt2和yt2分別為t2處無人駕駛汽車的x、y坐標(biāo)位置；θt2為t2時(shí)刻無人駕駛汽車的航向角；v為無人駕駛汽車的線速度；ω為無人駕駛汽車的角速度；Δt為（t1－t2）的時(shí)間間隔。

一旦在預(yù)測(cè)時(shí)間內(nèi)對(duì)速度空間進(jìn)行了采樣，就可以使用評(píng)價(jià)函數(shù)來評(píng)估預(yù)測(cè)軌跡的優(yōu)劣。DWA算法的評(píng)價(jià)函數(shù)通常需要根據(jù)實(shí)際情況進(jìn)行設(shè)置，主要包括目標(biāo)距離、速度、障礙物和方位角的代價(jià)。本文中根據(jù)式（5）設(shè)置DWA算法的評(píng)價(jià)函數(shù)，即總成本越小，路徑規(guī)劃過程越好。

式中：C（v，ω）為對(duì)速度采樣的總成本；D（v，ω）為目標(biāo)點(diǎn)位置與速度取樣空間之間的距離成本；S（v，ω）為速度采樣中的速度成本；O（v，ω）為速度采樣空間和障礙物之間的距離成本；α，β，λ分別表示目標(biāo)距離、速度、障礙物距離的單位成本增益。

各代價(jià)函數(shù)D（v，ω）、S（v，ω）、O（v，ω）的具體函數(shù)表示為：

式中：（xt，yt）為預(yù)測(cè)節(jié)點(diǎn)的（x，y）坐標(biāo)位置；（xd，yd）為目標(biāo)點(diǎn)的（x，y）坐標(biāo)位置；vmax為無人駕駛汽車最大速度；vt為預(yù)測(cè)速度空間的速度；（xoi，yoi）為第i個(gè)障礙物的（x，y）坐標(biāo)位置。

2 改進(jìn)傳統(tǒng)A*算法

2.1 量化柵格地圖障礙物信息

柵格地圖是一種用網(wǎng)格單元表示實(shí)際地圖的方法，每個(gè)網(wǎng)格單元可以表示一個(gè)區(qū)域是否有障礙物。有障礙物的網(wǎng)格單元叫做障礙格，障礙格的多少會(huì)影響地圖上可供選擇的路徑的數(shù)量，也會(huì)使得最短路徑的長度大于起點(diǎn)和終點(diǎn)之間的直線距離。為了估計(jì)最短路徑的長度，需要定義障礙率P，它可以反映地圖環(huán)境的復(fù)雜程度。障礙率P是指當(dāng)前點(diǎn)和終點(diǎn)構(gòu)成的矩形局部環(huán)境中，障礙格的數(shù)量占該局部地圖總格數(shù)的比例。假設(shè)當(dāng)前位置與目的地位置組成的柵格地圖內(nèi)的障礙柵格個(gè)數(shù)為N，初始位置坐標(biāo)（xs，ys）、目的地位置坐標(biāo)（xg，yg），其表達(dá)式如式（9）所示。

2.2 改進(jìn)A*算法的評(píng)價(jià)函數(shù)

評(píng)價(jià)函數(shù)是A*算法的核心，為了提高A*算法的搜索效率和精度，本文中針對(duì)A*算法的評(píng)價(jià)函數(shù)進(jìn)行了優(yōu)化，提升搜索速度和準(zhǔn)確度。評(píng)價(jià)函數(shù)包括代價(jià)函數(shù)和啟發(fā)函數(shù)2部分，其中啟發(fā)函數(shù)是決定搜索效果的重要因素。啟發(fā)函數(shù)的值要根據(jù)地圖情況中的障礙物密度進(jìn)行變化，障礙物密度越高，啟發(fā)函數(shù)越低，搜索范圍越廣，搜索精確度越好。障礙物密度由障礙物個(gè)數(shù)和起點(diǎn)、終點(diǎn)的位置共同確定，它使得A*算法的搜索范圍具有變化性。通過將障礙物密度納入評(píng)價(jià)函數(shù)中，根據(jù)障礙物密度自適應(yīng)調(diào)節(jié)代價(jià)函數(shù)和啟發(fā)函數(shù)的比重，實(shí)現(xiàn)評(píng)價(jià)函數(shù)的自動(dòng)調(diào)節(jié)，從而保證路徑規(guī)劃的靈活性、快速性和最優(yōu)性。

式中：g（n）為初始位置（xg，yg）到當(dāng)前位置（xn，yn）之間累計(jì)距離的代價(jià)函數(shù)；h（n）為當(dāng)前位置（xn，yn）到目的地位置（xg，yg）之間的啟發(fā)函數(shù)。

2.3 優(yōu)化搜索點(diǎn)選取策略

A*算法在搜索過程中，需要維護(hù)一個(gè)開放列表，其中包含了所有當(dāng)前點(diǎn)周圍可達(dá)的子節(jié)點(diǎn)。每次選擇評(píng)價(jià)函數(shù)值最小的節(jié)點(diǎn)作為下一個(gè)路徑節(jié)點(diǎn)。在生成子節(jié)點(diǎn)時(shí)，需要判斷子節(jié)點(diǎn)是否位于障礙柵格上。如果是，將不會(huì)將該子節(jié)點(diǎn)加入開放列表。這樣做的結(jié)果會(huì)導(dǎo)致規(guī)劃出的路徑可能沿著障礙物的邊緣走，甚至還可能穿過2個(gè)相鄰障礙物的頂點(diǎn)。這樣就會(huì)增加無人駕駛汽車與障礙物碰撞的風(fēng)險(xiǎn)，如圖2所示。

圖2 碰撞風(fēng)險(xiǎn)示例

如圖3所示，展示了父節(jié)點(diǎn)及其8個(gè)子節(jié)點(diǎn)之間的位置關(guān)系。根據(jù)子節(jié)點(diǎn)相對(duì)于父節(jié)點(diǎn)的位置，將其分為3種類型。第Ⅰ類是位于父節(jié)點(diǎn)正上方和正下方的子節(jié)點(diǎn)2和6，第Ⅱ類是位于父節(jié)點(diǎn)正左方和正右方的子節(jié)點(diǎn)4和8，第Ⅲ類是位于父節(jié)點(diǎn)斜對(duì)角線上的子節(jié)點(diǎn)1、3、5和7。

圖3 節(jié)點(diǎn)移動(dòng)方向示意圖

為了解決傳統(tǒng)A*算法可能導(dǎo)致路徑穿過障礙物頂點(diǎn)的問題，本文中提出了一種新的搜索點(diǎn)選取策略，根據(jù)子節(jié)點(diǎn)和障礙物的位置關(guān)系，排除一些不優(yōu)的子節(jié)點(diǎn)。以圖3為例，為了防止路徑穿過障礙物頂點(diǎn)，假設(shè)某個(gè)子節(jié)點(diǎn)是障礙物，那么子節(jié)點(diǎn)選取規(guī)則如下：

1）如果障礙子節(jié)點(diǎn)在父節(jié)點(diǎn)的正上方或正下方（第Ⅰ類位置），則舍棄該障礙子節(jié)點(diǎn)左右兩側(cè)的子節(jié)點(diǎn)（如子節(jié)點(diǎn)1、3或子節(jié)點(diǎn)5、7）。

2）如果障礙子節(jié)點(diǎn)在父節(jié)點(diǎn)的正左方或正右方（第Ⅱ類位置），則舍棄該障礙子節(jié)點(diǎn)上下兩側(cè)的子節(jié)點(diǎn)（如子節(jié)點(diǎn)1、7或子節(jié)點(diǎn)3、5）。

3）如果障礙子節(jié)點(diǎn)在父節(jié)點(diǎn)的斜對(duì)角線上（第Ⅲ類位置），則不做任何處理。通過這種優(yōu)化方式，改進(jìn)A*算法可以有效地規(guī)避風(fēng)險(xiǎn)路徑，不會(huì)讓路徑斜穿過障礙物頂點(diǎn)，從而減少無人駕駛汽車與障礙物碰撞的可能性。圖2中的風(fēng)險(xiǎn)路徑經(jīng)過優(yōu)化后變成了圖4中的安全路徑。

圖4 優(yōu)化后的安全路徑

2.4 路徑平滑度優(yōu)化

本文中針對(duì)柵格地圖中路徑的轉(zhuǎn)折和長度問題，設(shè)計(jì)了一種雙向節(jié)點(diǎn)判斷的路徑平滑度優(yōu)化方法。該方法的核心思想是，對(duì)于路徑中的任意2個(gè)不相鄰的節(jié)點(diǎn)，如果它們之間的連線長度小于它們之間的規(guī)劃路徑長度，并且連線不與障礙物相交，那么就可以刪除它們之間的所有節(jié)點(diǎn)。這樣可以有效地減少路徑的轉(zhuǎn)折和長度，提高路徑的平滑度。此外，該算法還考慮了防碰撞的要求，通過設(shè)置安全距離和計(jì)算障礙點(diǎn)到連線的垂直距離和縱軸距離，以及利用單元障礙柵格的外接圓半徑，判斷路徑是否安全，避免與障礙物發(fā)生碰撞。

以圖5所示的柵格地圖路徑規(guī)劃軌跡為例，采用A*算法規(guī)劃的路徑由若干柵格節(jié)點(diǎn)組成，圖中優(yōu)化前的路徑為（S→n1→n2→n3→n4→n5→n6→n7→n8→n9→n10→G），該路徑存在冗余節(jié)點(diǎn)、過多轉(zhuǎn)折和節(jié)點(diǎn)僅能在柵格中心等問題，不利于無人駕駛汽車路徑跟隨。

圖5 柵格地圖路徑規(guī)劃軌跡

針對(duì)以上問題本文中對(duì)A*算法得到的路徑節(jié)點(diǎn)進(jìn)行優(yōu)化處理，包括雙向刪除冗余節(jié)點(diǎn)、障礙距離判斷和雙向平滑度優(yōu)化，使得路徑節(jié)點(diǎn)可以在柵格中任意位置選擇，減少了路徑的轉(zhuǎn)折和長度，提高了路徑的平滑度。具體優(yōu)化步驟如下：

步驟1刪掉路徑節(jié)點(diǎn)中同一直線上的中間點(diǎn)，只保留起點(diǎn)、拐點(diǎn)和終點(diǎn)。這樣可以簡(jiǎn)化路徑，減少不必要的節(jié)點(diǎn)，處理后路徑為S→n7→n8→n9→G。

步驟2 從起始點(diǎn)S方向，在保留的2拐點(diǎn)ni、nj之間每隔k步長取一節(jié)點(diǎn)。這樣可以在2拐點(diǎn)之間生成一系列候選節(jié)點(diǎn)，用于優(yōu)化路徑。

步驟3判斷2點(diǎn)之間路徑是否有障礙物。如果有，就不選擇當(dāng)前節(jié)點(diǎn)為路徑節(jié)點(diǎn)，如果沒有，就繼續(xù)下一步。

步驟4計(jì)算路徑旁障礙物與路徑的距離，并使用大小關(guān)系來判斷是否選擇當(dāng)前節(jié)點(diǎn)作為路徑節(jié)點(diǎn)。這樣可以保證路徑不會(huì)太靠近障礙物，避免碰撞危險(xiǎn)，處理后的路徑為S→n11→G。

步驟5反向取點(diǎn)后，按照與步驟2、3、4相同的判斷方式，從目的地點(diǎn)G方向進(jìn)行判斷。這樣可以優(yōu)化路徑，使其變得更短或更平滑。處理后的優(yōu)化路徑為S→n12→G。

步驟6輸出優(yōu)化路徑Path。

3 融合算法

根據(jù)前文所述，改進(jìn)后的A*算法在全局信息已知的情況下，能夠找到最優(yōu)的全局路徑。然而，當(dāng)存在未知障礙物的環(huán)境中，依賴改進(jìn)后的A*算法單獨(dú)進(jìn)行路徑規(guī)劃并不有效。DWA算法可以實(shí)現(xiàn)路徑的平滑和實(shí)時(shí)避障，但很容易陷入局部最優(yōu)，成功規(guī)劃路徑的概率較低。因此，本文中提出了一種融合改進(jìn)A*算法和DWA算法的方法。通過巧妙地結(jié)合這2種算法，可以得到一種既能保留全局最優(yōu)性，又能適應(yīng)局部實(shí)時(shí)變化的路徑規(guī)劃算法。

3.1 優(yōu)化DWA算法評(píng)價(jià)函數(shù)

根據(jù)無人車的速度范圍和運(yùn)動(dòng)模型，在仿真中使用了多個(gè)軌跡，并使用估計(jì)函數(shù)進(jìn)行篩選，以選擇最優(yōu)軌跡［25］。針對(duì)傳統(tǒng)動(dòng)態(tài)窗口法容易出現(xiàn)局部最優(yōu)的問題，對(duì)動(dòng)態(tài)窗口算法的估計(jì)函數(shù)進(jìn)行了改進(jìn)。新的評(píng)估函數(shù)結(jié)合了2.2節(jié)改進(jìn)的A*算法提供的全局軌跡信息，確保最終的局部軌跡以全局最優(yōu)軌跡為基礎(chǔ)。其中DWA算法的基本參數(shù)設(shè)定如下：最大速度限制設(shè)置為1 m／s；最大角速度限制定為20（°）／s；速度分辨率設(shè)置為0.01 m／s；角速度分辨率設(shè)置為1（°）／s；加速度限制為0.2 m／s2；角加速度限制為50（°）／s2；評(píng)價(jià)函數(shù)的各參數(shù)分別為：α＝0.1，β＝0.05，γ＝0.2，預(yù)測(cè)時(shí)間的周期設(shè)定為3.0 s。改進(jìn)后的估計(jì)函數(shù)如式（17）所示：

式中：PHead（v，ω）為軌跡終點(diǎn)方向與當(dāng)前目標(biāo)點(diǎn)之間的角度差；dist（v，ω）為軌跡與最近障礙物之間的距離；vel（v，ω）為當(dāng)前速度評(píng)價(jià)函數(shù)；σ為平滑函數(shù)；α、β、Υ為加權(quán)系數(shù)。

3.2 算法融合策略

為了同時(shí)實(shí)現(xiàn)全局路徑優(yōu)化和隨機(jī)避障目標(biāo)，本文中提出了一種結(jié)合改進(jìn)A*算法和動(dòng)態(tài)窗口法的路徑規(guī)劃方法。改進(jìn)A*算法利用了啟發(fā)式搜索算法來在復(fù)雜環(huán)境中快速找到全局最優(yōu)路徑。動(dòng)態(tài)窗口法是一種局部避障算法，能夠根據(jù)被控對(duì)象的運(yùn)動(dòng)狀態(tài)和環(huán)境信息，實(shí)時(shí)生成適應(yīng)的速度空間。利用改進(jìn)的A*算法進(jìn)行全局路徑規(guī)劃后，獲得全局最優(yōu)節(jié)點(diǎn)序列后，可以使用動(dòng)態(tài)窗口法在相鄰節(jié)點(diǎn)之間進(jìn)行局部路徑規(guī)劃。本文中將這2種算法結(jié)合起來，所采用的最終融合算法流程如圖6所示。

圖6 融合算法流程

4 仿真驗(yàn)證

4.1 改進(jìn)A*算法實(shí)驗(yàn)仿真分析

為了驗(yàn)證本文中改進(jìn)A*算法的有效性，在柵格地圖環(huán)境信息相同的前提下，分別用改進(jìn)后的A*算法、傳統(tǒng)A*算法、蟻群算法、Dijkstra算法進(jìn)行路徑規(guī)劃仿真對(duì)比實(shí)驗(yàn)，并通過改變對(duì)應(yīng)柵格地圖信息進(jìn)一步仿真驗(yàn)證。柵格地圖模型大小分別為20×20、30×30和50×50。在柵格地圖環(huán)境中，黑色區(qū)域表示障礙，白色區(qū)域?yàn)榭梢苿?dòng)區(qū)域。計(jì)算機(jī)配置為：Windows 11操作系統(tǒng)，處理器為AMD Ryzen 7 5800H with Radeon Graphics，主頻為3 201 MHz，運(yùn)行內(nèi)存為16 G。

1）實(shí)驗(yàn)1：柵格地圖20×20，障礙物覆蓋率p＝20%。路徑規(guī)劃軌跡如圖7所示。

圖7 實(shí)驗(yàn)1的4種算法路徑規(guī)劃軌跡

2）實(shí)驗(yàn)2：柵格地圖30×30，障礙物覆蓋率p＝13%。路徑規(guī)劃軌跡如圖8所示。

圖8 實(shí)驗(yàn)2的4種算法路徑規(guī)劃軌跡

3）實(shí)驗(yàn)3：柵格地圖30×30，障礙物覆蓋率p＝25%。路徑規(guī)劃軌跡如圖9所示。

圖9 實(shí)驗(yàn)3的4種算法路徑規(guī)劃軌跡

4）實(shí)驗(yàn)4：柵格地圖50×50，障礙物覆蓋率p＝25%。路徑規(guī)劃軌跡如圖10所示。

圖10 實(shí)驗(yàn)4的4種算法路徑規(guī)劃軌跡

本文中改進(jìn)A*算法在評(píng)價(jià)函數(shù)中增加了環(huán)境信息的引導(dǎo)，搜索空間對(duì)比4組仿真實(shí)驗(yàn)比傳統(tǒng)A*算法分別降低29.2%、45.83%、61.17%、60.36%；相比Dijkstra算法分別降低72.8%、83.18%、84.23%、88.37%。同時(shí)增加子節(jié)點(diǎn)優(yōu)化規(guī)則及路徑平滑度優(yōu)化，使改進(jìn)A*算法搜索的路徑轉(zhuǎn)折次數(shù)更少，轉(zhuǎn)折角度更小，在保證與障礙物保持在安全距離之外的同時(shí)，規(guī)劃出的路徑有效避免了可能會(huì)沿著障礙物的邊緣走，甚至穿過2個(gè)障礙物相鄰的頂點(diǎn)的情況。從圖8—圖10可知，隨著柵格地圖擴(kuò)大和障礙物的增多，蟻群算法所規(guī)劃路徑由于信息素高低的影響，出現(xiàn)折返路徑、規(guī)劃時(shí)間長、路徑折點(diǎn)多等局限性。Dijkstra算法與傳統(tǒng)A*算法規(guī)劃的路徑均一直朝著目標(biāo)點(diǎn)方向，沒有考慮障礙物對(duì)路徑的影響，選擇了局部路徑最短的路線，出現(xiàn)多次轉(zhuǎn)折，且不能避免規(guī)劃出的路徑可能會(huì)沿著障礙物的邊緣走，甚至穿過2個(gè)障礙物相鄰的頂點(diǎn)的情況。4種算法性能數(shù)對(duì)比如表1所示。

表1 4種算法性能數(shù)

4.2 融合算法實(shí)驗(yàn)仿真分析

通過在柵格地圖中添加不同的隨機(jī)障礙物，分別設(shè)置3組改進(jìn)A*和DWA算法融合算法在障礙物覆蓋率p＝20%的20×20柵格地圖中進(jìn)行路徑規(guī)劃，進(jìn)而對(duì)融合算法的隨機(jī)避障能力進(jìn)行分析驗(yàn)證。

1）實(shí)驗(yàn)1：柵格地圖20×20，障礙物覆蓋率p＝20%，無障礙物。路徑規(guī)劃軌跡如圖11所示。

圖11 無障礙物路徑規(guī)劃軌跡

2）實(shí)驗(yàn)2：柵格地圖20×20，障礙物覆蓋率p＝20%，寬闊地帶出現(xiàn)障礙物。路徑規(guī)劃軌跡如圖12所示。

圖12 寬闊地帶出現(xiàn)障礙物路徑規(guī)劃軌跡

3）實(shí)驗(yàn)3：柵格地圖20×20，障礙物覆蓋率p＝20%，狹窄地帶出現(xiàn)障礙物。路徑規(guī)劃軌跡如圖13所示。

圖13 狹窄地帶出現(xiàn)障礙物路徑規(guī)劃軌跡

4）實(shí)驗(yàn)4：柵格地圖20×20，障礙物覆蓋率p＝20%，模擬較為復(fù)雜環(huán)境。路徑規(guī)劃軌跡如圖14所示。

圖14 較為復(fù)雜環(huán)境路徑規(guī)劃軌跡

通過上述4組對(duì)比實(shí)驗(yàn)分析可知，當(dāng)?shù)貓D中無隨機(jī)障礙物出現(xiàn)時(shí)，改進(jìn)A*算法與融合算法均可以規(guī)劃一條從起點(diǎn)到終點(diǎn)的路徑規(guī)劃方法。然而，在廣闊的區(qū)域中添加隨機(jī)障礙物后，單獨(dú)改進(jìn)A*算法無法有效避免突然出現(xiàn)的隨機(jī)障礙物。相比之下，融合算法實(shí)現(xiàn)了隨機(jī)避障，同時(shí)確保規(guī)劃路徑保持全局最優(yōu)性，并且使路徑平滑，以適應(yīng)無人駕駛車輛的跟蹤行駛要求。后續(xù)通過改變障礙物的數(shù)量和位置來驗(yàn)證融合算法的魯棒性。結(jié)果表明，在較為復(fù)雜的情況下本文融合算法仍然能夠合理避開隨機(jī)障礙物并到達(dá)目標(biāo)點(diǎn)。融合算法路徑規(guī)劃性能參數(shù)如表2所示。

表2 融合算法路徑規(guī)劃性能參數(shù)

5 結(jié)論

1）本文中通過改進(jìn)傳統(tǒng)A*算法，在搜索空間上實(shí)現(xiàn)了大幅的降低，相較于Dijkstra算法的降低幅度在較為復(fù)雜的柵格地圖環(huán)境中更是最大達(dá)到了88.37%。同時(shí)通過增加子節(jié)點(diǎn)優(yōu)化規(guī)則和路徑平滑度優(yōu)化，使得改進(jìn)后的A*算法搜索路徑與障礙物保持安全距離，規(guī)劃出的路徑有效避免沿著障礙物邊緣走或穿過相鄰障礙物頂點(diǎn)的情況，路徑轉(zhuǎn)折次數(shù)更少，轉(zhuǎn)折角度更小。這表明本研究中改進(jìn)的A*算法具有一定的優(yōu)勢(shì)和有效性。

2）改進(jìn)后的A*算法與動(dòng)態(tài)窗口法相結(jié)合，能夠成功避開隨機(jī)障礙物到達(dá)目的地點(diǎn)。它不僅能根據(jù)全局路徑修正局部路徑，還能滿足無人駕駛汽車在尋路過程中避免碰撞的要求。由此可見，該算法的可行性和有效性都具有一定的優(yōu)勢(shì)。

本文中的研究成果可用于復(fù)雜環(huán)境中無人駕駛汽車的路徑規(guī)劃。未來的研究可以通過調(diào)整動(dòng)態(tài)窗口法的權(quán)值組合，提升環(huán)境適應(yīng)能力，根據(jù)障礙物的實(shí)際分布情況進(jìn)行對(duì)應(yīng)優(yōu)化。