明瑞陽

（重慶交通大學(xué)機(jī)電與車輛工程學(xué)院，重慶 400074）

主題詞：自動駕駛；避障；軌跡規(guī)劃

0 引言

隨著汽車產(chǎn)業(yè)市場規(guī)模的不斷擴(kuò)大，汽車產(chǎn)業(yè)在加速向智能化、網(wǎng)聯(lián)化、電動化和共享化轉(zhuǎn)型。2021年8 月發(fā)布的GB∕T 40429—2021《汽車駕駛自動化分級》[1]將駕駛自動化從0級至5級分為6級，其中以5級為最高自動駕駛等級。

據(jù)行業(yè)報告顯示[2]，在2020 年中國自動駕駛汽車行業(yè)的市場規(guī)模約為81.32 億元，較上年的84.2 億元同比下降了約3.5%，到2021年增長至94.1億元左右，同比增長了約15.72%。在我國自動駕駛方面政策、技術(shù)發(fā)展和市場需求增長多方面帶動下，預(yù)測未來幾年自動駕駛汽車的市場規(guī)模將會持續(xù)增長，到2023年有望達(dá)到約120.5億元。

在自動駕駛汽車發(fā)展中，由于避障功能與車輛安全具有高度耦合性，因此在向高等級自動駕駛發(fā)展的過程中，避障功能始終是汽車企業(yè)、大學(xué)和研究機(jī)構(gòu)重點研發(fā)的自動駕駛功能之一。

整個避障運(yùn)動分為4個動作，包括信息感知、智能決策、路徑規(guī)劃和運(yùn)動控制[3]，通過這4個動作使車輛完成躲避障礙物或制動動作。在制動過程中，如何規(guī)劃出一條合理且安全的軌跡尤為重要。避障路徑規(guī)劃也被稱為局部路徑規(guī)劃，與全局路徑規(guī)劃相比，只對當(dāng)前場景進(jìn)行路徑規(guī)劃且能夠適應(yīng)不可預(yù)見的障礙物。目前，局部路徑規(guī)劃的主要方法包括基于采樣的規(guī)劃方法、人工勢場算法、螻蟻算法和神經(jīng)網(wǎng)絡(luò)算法[4]。

本文對基于采樣和人工勢場的路徑規(guī)劃算法進(jìn)行綜述，分析對比這2種算法的優(yōu)缺點，并對近年來國內(nèi)外研究人員對這兩種路徑規(guī)劃算法進(jìn)行的優(yōu)化融合進(jìn)行了歸納，為后續(xù)研究人員開展自動駕駛軌跡規(guī)劃研究與開發(fā)提供參考。

1 基于采樣的規(guī)劃方法

目前，基于采樣的規(guī)劃方法可以避免配置空間的離散化和顯式表示，從而可以很好地擴(kuò)展到高維空間。概率路線圖（Probabilistic Road Maps,PRM）[5]和快速探索隨機(jī)樹算法（Rapidly-Exploring Random Tree,RRT）[6]是基于采樣法進(jìn)行路徑規(guī)劃的代表性方法。

1.1 概率路線圖算法

基于概率路線圖算法解決路徑規(guī)劃問題是在給定的環(huán)境中設(shè)置多個點位，除去被設(shè)置在障礙物上的點位外，對剩余點位進(jìn)行算法運(yùn)算，從而得出一條規(guī)避障礙物的路線，如圖1~圖3所示。

圖1 概率路線圖設(shè)置點

圖2 去除障礙物點位后的概率路線

如圖3所示，在所規(guī)劃的路段中，雖然所有點位均不在障礙物上，但2點之間的路線仍會經(jīng)過障礙物，如灰色路線，因此碰撞檢測耗時較長，導(dǎo)致規(guī)劃效率較低。

1.2 快速探索隨機(jī)樹算法

與概率路線圖算法不同，快速探索隨機(jī)樹算法是1 種遞增式的構(gòu)造方法。在整個路徑規(guī)劃過程中，僅隨機(jī)生成1個點位，如果該點位處于無碰撞點位，則尋找探索樹種離該點最近的節(jié)點作為基準(zhǔn)節(jié)點，從該基準(zhǔn)節(jié)點以固定步長向隨機(jī)點位延伸，每段延伸線的終點會被當(dāng)作有效節(jié)點加入搜索樹種。該過程一直持續(xù)到目標(biāo)節(jié)點與搜索樹的距離小于最初設(shè)定的數(shù)值，然后尋找1條連接起點和終點的最短路徑。該算法有一些不足之處，如搜索時間差異大，在狹窄的通道情況下性能差，離最優(yōu)路徑遠(yuǎn)。

1.3 算法改進(jìn)

為了解決概率路線圖算法中采樣點過多導(dǎo)致運(yùn)算速度過慢的問題，Mika 等[7]提出了1 種基于鄰域的方法，通過濾掉不必要的節(jié)點來減小路線圖的大小。Kumar等[8]提出了1種減少節(jié)點的概率路線圖算法來減小路線圖大小，通過附近障礙物和目標(biāo)的距離誤差以及高斯成本函數(shù)來消除部分節(jié)點，以提高規(guī)劃效率。

而對于快速探索隨機(jī)樹算法而言，盡管改善后的RRT*[9]能夠通過引入近鄰搜索和隨機(jī)樹重新布線操作來實現(xiàn)漸近最優(yōu)，但因為隨機(jī)抽樣機(jī)制會影響收斂速度，因此收斂到最優(yōu)解需要大量時間。Noreen 等[10]提出了1種基于RRT*的RRT*—可調(diào)整邊界（RRT*—AB）離線規(guī)劃算法，該算法包括3 步策略：即連接區(qū)域、基于目標(biāo)的有界采樣和路徑優(yōu)化?；谀繕?biāo)的有界抽樣在連接區(qū)域的邊界內(nèi)進(jìn)行，以尋找初始路徑，而連接區(qū)域可在復(fù)雜的環(huán)境中擴(kuò)展，一旦找到路徑，就使用節(jié)點剔除和集中的有界抽樣對其進(jìn)行逐步優(yōu)化，最后的路徑通過全局修剪進(jìn)一步改進(jìn)，以消除多余節(jié)點。為了提高該算法路徑規(guī)劃效率，除了剔除不需要的節(jié)點外，較為主流的方式是將其它原理或算法和快速探索隨機(jī)樹算法進(jìn)行融合，以解決規(guī)劃效率和路線質(zhì)量問題。

Jeong 等[11]將三角不等式與RRT*相結(jié)合提出了Quick-RRT*（Q-RRT*）,其擴(kuò)大了父頂點集合，產(chǎn)生路徑成本比RRT*算法低且能更快收斂到最優(yōu)。Zhuge等[12]在Q-RRT*基礎(chǔ)上，將啟發(fā)式信息與Q-RRT*算法優(yōu)化能力相結(jié)合，提出1 種基于虛擬光的Q-RRT*（LQRRT*）,該算法相比于Q-RRT*算法優(yōu)化了采樣空間，提高了采樣效率且試驗證明了內(nèi)存占用量較少。

Wu 等[13]提出了1 種基于RRT 的路徑搜索算法Fast-RRT，該算法由1個改進(jìn)RRT模塊和快速最優(yōu)選擇模塊融合，前者穩(wěn)定獲取1條初始路徑，后者將多條初始路徑進(jìn)行合并獲得近似最優(yōu)路徑。最終通過試驗得出，在相同環(huán)境下Fast-RRT 算法會比RRT*算法有著更快的速度和更高的穩(wěn)定性。Wang 等[14]為了解決狹窄空間路徑規(guī)劃問題，提出了1種自適應(yīng)擴(kuò)展雙向RRT*（AEB-RRT*）算法，該算法從設(shè)定的起點和終點雙向同時進(jìn)行擴(kuò)展，并根據(jù)碰撞到障礙物次數(shù)自適應(yīng)調(diào)整采樣頻率，將得到的可行路徑通過插值和三角不等式原理進(jìn)行處理，得到更短的可行路徑。

為了減少RRT 本身的局限性，除上述算法之外，還有基于勢場的P-RRT*、結(jié)合基于勢函數(shù)的RRT*（P-RRT*）和Quick-RRT*的PQ-RRT*[15]、將雙向人工勢場與快速探索隨機(jī)樹星（RRT*）相結(jié)合的RRT*-Connect（P-RRT*-Connect）規(guī)劃算法[16]等，都有效地減少了RRT*算法本身的局限性。

1.4 小結(jié)

概率路線圖和快速探索隨機(jī)樹法都是常見的路徑規(guī)劃算法。

通過對上述內(nèi)容的綜述，可將概率路線圖算法和快速探索隨機(jī)數(shù)算法的優(yōu)缺點進(jìn)行歸納對比，如表1所示。

概率路線圖算法優(yōu)點在于：隨著搜索時間的增加，其成功規(guī)劃路徑的概率會快速向1收斂，也證明其具備概率的完備性，且具有較高的精度，可以在較為復(fù)雜的環(huán)境中規(guī)劃路徑。

概率路線圖算法缺點在于：該算法需要在全局地圖中建立隨機(jī)采樣點，因此運(yùn)行時間較長，且不能很好地應(yīng)對障礙物移動的情況。

快速探索隨機(jī)樹法優(yōu)點在于：其路徑生成速度快，能夠在較短的時間內(nèi)找到1條可行路徑，且能夠應(yīng)對環(huán)境變化，自適應(yīng)地規(guī)劃出合適的路徑，靈活性較高。

快速探索隨機(jī)樹法缺點在于：處理復(fù)雜環(huán)境時，隨機(jī)樹分叉多，使得不穩(wěn)定性較大。

隨著人工智能技術(shù)的發(fā)展，概率路線圖和快速探索隨機(jī)樹法將向高效和智能化發(fā)展。這2種算法可以結(jié)合深度學(xué)習(xí)技術(shù)，實現(xiàn)更加精準(zhǔn)和高效的路徑規(guī)劃。

2 人工勢場法

人工勢場算法是目前運(yùn)用較為廣泛的局部路徑規(guī)劃算法，其基本思想是將物體在具體環(huán)境中的運(yùn)動，轉(zhuǎn)化為人為抽象勢場中的運(yùn)動，由目標(biāo)點對物體產(chǎn)生吸引力，由障礙物對物體產(chǎn)生排斥力，使得物體能順利繞過障礙物到達(dá)目標(biāo)點。其中，物體在抽象勢場中的受力情況如圖4所示，其中，F(xiàn)att是目標(biāo)點對物體的吸引力，F(xiàn)rep是障礙物對物體的排斥力，F(xiàn)total是吸引力和排斥力產(chǎn)生的合力。人工勢場法優(yōu)點在于該算法生成的路徑平滑、計算量小、執(zhí)行效率高[17]，但是同樣存在著局部極值點和目標(biāo)不可達(dá)的問題[18]。

圖4 物體在人工勢場中的受力情況

對于障礙物較少的簡單場景下，人工勢場算法可以較為容易地規(guī)劃出1條無碰撞的路徑以快速到達(dá)目標(biāo)點。但在復(fù)雜場景下，存在局部極值點，在吸引力和多個排斥力的反復(fù)作用下，物體在多個障礙物間做振蕩運(yùn)動，無法駛出局部極值點，如圖5所示。

圖5 物體進(jìn)入狹窄環(huán)境

如圖6所示，對于物體進(jìn)入三面封閉的環(huán)境后，由于目標(biāo)點對物體向上的吸引力和障礙物墻壁對物體向下的排斥力兩個方向相反的作用力作用下，使得該場景無法使用人工勢場算法完成路徑規(guī)劃，存在目標(biāo)不可達(dá)的問題。

圖6 物體進(jìn)入陷阱區(qū)域

2.1 局部極值點的人工勢場算法改進(jìn)

在狹窄環(huán)境下，路徑中可能存在極值點使物體發(fā)生振蕩運(yùn)動從而難以到達(dá)目標(biāo)點，針對這種問題，Duan等[19]在基于安全距離模型的人工勢場中，對于可能存在局部極值點的道路工況，通過引入第二虛擬目標(biāo)點，產(chǎn)生第二道目標(biāo)點吸引力，克服了局部極值點問題。同樣，Wang等[20]通過左轉(zhuǎn)彎勢場法使物體在脫離局部極值點附近，若物體已經(jīng)處于局部極值點時，則通過虛擬目標(biāo)點法在合適的位置設(shè)置虛擬點，并忽略障礙物和初始設(shè)置的目標(biāo)點吸引力的影響，使物體在局部最小點轉(zhuǎn)彎和跳出。

Gu等[21]在傳統(tǒng)人工勢場算法中，添加了1種可修正的斥力勢場函數(shù)，并將此改進(jìn)的人工勢場算法與模糊控制算法進(jìn)行融合，利用該融合勢場解決局部極值點問題。Ma等[22]通過引入隨機(jī)擾動勢能的調(diào)節(jié)機(jī)制，解決了在局部極值點難以移動的問題。Shen 等[23]針對局部極值點導(dǎo)致路徑規(guī)劃失敗的問題，將快速探索隨機(jī)樹算法與人工勢場法相融合，將快速探索隨機(jī)樹所規(guī)劃的節(jié)點設(shè)置為新的目標(biāo)點，為物體提供吸引力的同時弱化預(yù)設(shè)目標(biāo)點作用，并改進(jìn)障礙物排斥勢場功能，確保吸引力的力源可及性，保證物體出現(xiàn)在接近局部極值點附近時，能完成路徑規(guī)劃。

2.2 針對目標(biāo)點不可達(dá)的人工勢場算法改進(jìn)

對于目標(biāo)不可達(dá)問題，尹鳳儀等[24]針對目標(biāo)點附近人工勢場建立了規(guī)則，在障礙物周圍排斥力勢場函數(shù)加入距離影響因子，使得物體能夠抵達(dá)目標(biāo)。Zhang等[25]為了解決物體在進(jìn)入陷阱區(qū)域的目標(biāo)點不可達(dá)問題，通過對斥力場函數(shù)進(jìn)行改進(jìn)并選擇1個虛擬目標(biāo)點，從而使物體逃離陷阱到達(dá)目標(biāo)點，如圖7所示。同樣，Yang等[26]通過增加引力解決了目標(biāo)不可達(dá)問題。

圖7 物體進(jìn)入陷阱區(qū)域所設(shè)的虛擬點

Cao 等[27]在人工勢場法中引入了調(diào)節(jié)因子，以解決軌跡規(guī)劃中目標(biāo)不可達(dá)問題。

2.3 融合人工勢場的改進(jìn)算法

針對不同應(yīng)用場景，張強(qiáng)等[28]將全局路徑規(guī)劃算法與局部路徑規(guī)劃算法相結(jié)合，提出1種融合安全A*和人工勢場的融合算法，在A*算法中的代價函數(shù)里添加安全距離，并將A*算法中的部分關(guān)鍵節(jié)點設(shè)置為人工勢場中的目標(biāo)點提供吸引力，經(jīng)仿真驗證，該方法所規(guī)劃的路徑簡短且避障能力較好。

音凌一等[29]為了解決適用于全局路徑規(guī)劃的灰狼優(yōu)化算法求解效率低和易陷入局部最優(yōu)的問題，將灰狼算法全局路徑規(guī)劃的節(jié)點設(shè)置為人工勢場臨時目標(biāo)點，并改進(jìn)臨時目標(biāo)點為臨時邊界，進(jìn)行局部路徑規(guī)劃。最終通過仿真表明，在全局靜態(tài)環(huán)境和局部動態(tài)環(huán)境下，該融合算法在規(guī)劃路徑時有效性很好。

Wu 等[30]提出了1 種將人工勢場法和IRRT*算法相結(jié)合的融合算法，把人工勢場法中的勢場引入IRRT*算法中的搜索樹擴(kuò)展階段，提供搜索樹擴(kuò)展方向指引，提高了IRRT*算法的收斂率和搜索效率。同樣，辛鵬等[31]為了減小快速探索隨機(jī)樹法擴(kuò)展時的隨機(jī)性，把擴(kuò)展方向通過人工勢場法進(jìn)行約束，減少隨機(jī)樹向正確目標(biāo)點擴(kuò)展的探索時間。

2.4 小結(jié)

人工勢場法是基于虛擬勢場的路徑規(guī)劃算法，它通過構(gòu)造人工勢場來引導(dǎo)物體在環(huán)境中移動，從而實現(xiàn)物體自主避障和路徑規(guī)劃。人工勢場法的優(yōu)勢主要包括：算法簡單易懂、實時性好，且可以用于包括室內(nèi)室外、平面地形和復(fù)雜地形多種場景。其缺點在于作為1種局部路徑規(guī)劃方法，存在局部極值點問題，當(dāng)物體陷入極值點后將無法繼續(xù)前進(jìn)。且該方法在使用過程中需要設(shè)定一系列參數(shù)，如障礙物排斥力、目標(biāo)點吸引力等，這些參數(shù)設(shè)置需要經(jīng)驗和調(diào)試，可能會影響路徑規(guī)劃效果。

未來展望方面，人工勢場法作為1 種經(jīng)典的路徑規(guī)劃算法，已經(jīng)被廣泛應(yīng)用于實際場景中。隨著人工智能技術(shù)的發(fā)展，人工勢場法仍然具有重要的應(yīng)用前景。人工勢場法也可以與其它路徑規(guī)劃算法相結(jié)合，或者與神經(jīng)網(wǎng)絡(luò)技術(shù)相結(jié)合，形成更加高效和使用便捷的路徑規(guī)劃算法。

3 結(jié)束語

避障技術(shù)在自動駕駛汽車或者是其他無人設(shè)備上來說都是1 項核心功能，針對動態(tài)或靜態(tài)環(huán)境，合理、高效規(guī)劃出1條平穩(wěn)、無碰撞的路徑是避障運(yùn)動能否安全完成的重要核心，本文對3種局部路徑規(guī)劃方法優(yōu)缺點和目前發(fā)展現(xiàn)狀進(jìn)行了綜述。

概率路線圖法和快速探索隨機(jī)樹法均是基于采樣的路徑規(guī)劃方法。概率路線圖的優(yōu)點在于隨著搜索時間增加，其成功規(guī)劃出路徑的概率會快速向1收斂，具備概率的完備性?？焖偬剿麟S機(jī)樹法的優(yōu)點在于有更強(qiáng)方向性，且相比于概率路線圖流程更加簡單。但是這2種規(guī)劃方法都存在著規(guī)劃時間較長的問題。而人工勢場法優(yōu)點在于生成的路徑平滑、計算量小，同時該方法對傳感器的誤差有一定的魯棒性，其缺點在于存在局部極值和目標(biāo)不可達(dá)問題。

在進(jìn)行路徑規(guī)劃時，研究人員需要根據(jù)不同的待規(guī)劃環(huán)境采用不同的路徑規(guī)劃策略。就目前而言，多種算法融合后進(jìn)行路徑規(guī)劃，往往比單種規(guī)劃方法所得到的路徑規(guī)劃效果好，同時也可避免一些如探索隨機(jī)樹擴(kuò)展時間長、人工勢場法容易陷入陷阱區(qū)域的問題。