自動(dòng)駕駛汽車(chē)避障運(yùn)動(dòng)中路徑規(guī)劃研究綜述

明瑞陽(yáng)

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

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

0 引言

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

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

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

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

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

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

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

1.1 概率路線(xiàn)圖算法

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

圖1 概率路線(xiàn)圖設(shè)置點(diǎn)

圖2 去除障礙物點(diǎn)位后的概率路線(xiàn)

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

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

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

1.3 算法改進(jìn)

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

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

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

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

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

1.4 小結(jié)

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

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

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

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

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

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

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

2 人工勢(shì)場(chǎng)法

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

圖4 物體在人工勢(shì)場(chǎng)中的受力情況

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 小結(jié)

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

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

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

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

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

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