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

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

0 引言

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

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

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

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

1 算法基礎(chǔ)

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

A*算法被廣泛應(yīng)用于優(yōu)化路徑的搜索，因為它具有高效的搜索效率和快速的規(guī)劃速度［21］。A*算法基本思想是從起始柵格點開始，尋找與起點相鄰的子?xùn)鸥顸c。每一次都會從周圍的子?xùn)鸥顸c中選擇一個評估函數(shù)值最小的點作為下一步的搜索節(jié)點，即當(dāng)前節(jié)點。然后，在當(dāng)前節(jié)點的基礎(chǔ)上，生成與其鄰接的子?xùn)鸥顸c，并以目標(biāo)節(jié)點為終點進(jìn)行下一步的搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 改進(jìn)A*算法的評價函數(shù)

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

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

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

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

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

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

圖3 節(jié)點移動方向示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟5反向取點后，按照與步驟2、3、4相同的判斷方式，從目的地點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算法可以實現(xiàn)路徑的平滑和實時避障，但很容易陷入局部最優(yōu)，成功規(guī)劃路徑的概率較低。因此，本文中提出了一種融合改進(jìn)A*算法和DWA算法的方法。通過巧妙地結(jié)合這2種算法，可以得到一種既能保留全局最優(yōu)性，又能適應(yīng)局部實時變化的路徑規(guī)劃算法。

3.1 優(yōu)化DWA算法評價函數(shù)

根據(jù)無人車的速度范圍和運(yùn)動模型，在仿真中使用了多個軌跡，并使用估計函數(shù)進(jìn)行篩選，以選擇最優(yōu)軌跡［25］。針對傳統(tǒng)動態(tài)窗口法容易出現(xiàn)局部最優(yōu)的問題，對動態(tài)窗口算法的估計函數(shù)進(jìn)行了改進(jìn)。新的評估函數(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；評價函數(shù)的各參數(shù)分別為：α＝0.1，β＝0.05，γ＝0.2，預(yù)測時間的周期設(shè)定為3.0 s。改進(jìn)后的估計函數(shù)如式（17）所示：

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

3.2 算法融合策略

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

圖6 融合算法流程

4 仿真驗證

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

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

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

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

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

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

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

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

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

圖10 實驗4的4種算法路徑規(guī)劃軌跡

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

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

4.2 融合算法實驗仿真分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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