智能車輛局部路徑規(guī)劃算法研究綜述

馬曉錄，李如意，吳立輝

智能車輛局部路徑規(guī)劃算法研究綜述

馬曉錄，李如意*，吳立輝

（河南工業(yè)大學(xué) 機(jī)電工程學(xué)院，河南 鄭州 450001）

為提高智能車輛行駛的平穩(wěn)性和合理性，文章對近年來智能車輛常用的局部路徑規(guī)劃算法進(jìn)行了分類和總結(jié)。首先對各類傳統(tǒng)算法的原理進(jìn)行了闡述，分析其優(yōu)缺點(diǎn)，并指出傳統(tǒng)算法在智能車輛上應(yīng)用時(shí)的不足；其次整理分析了各類傳統(tǒng)算法應(yīng)用至智能車輛上時(shí)各學(xué)者所提出的改進(jìn)算法；最后提出基于離散優(yōu)化的算法是未來智能車輛局部路徑規(guī)劃的應(yīng)用趨勢，多算法融合是復(fù)雜場景下智能車輛局部路徑規(guī)劃的研究方向。文章的研究結(jié)果為智能車領(lǐng)域的研究人員在選擇局部路徑規(guī)劃算法時(shí)提供參考。

智能車輛；路徑規(guī)劃算法；局部路徑規(guī)劃；離散優(yōu)化；多算法融合

隨著自動駕駛技術(shù)的興起，智能車輛的路徑規(guī)劃問題越來越受到重視。路徑規(guī)劃可分為全局路徑規(guī)劃和局部路徑規(guī)劃。全局路徑規(guī)劃器在全局地圖內(nèi)按照一定的評估準(zhǔn)則規(guī)劃一條從初始點(diǎn)到目標(biāo)點(diǎn)的全局路徑，該路徑不隨環(huán)境或車輛運(yùn)動狀態(tài)變化而發(fā)生變化[1]。當(dāng)車輛沿著全局路徑行駛時(shí)，局部路徑規(guī)劃器以全局路徑為參考，根據(jù)實(shí)時(shí)的環(huán)境信息生成一條短期路徑，以達(dá)到避障和調(diào)整位姿的效果，該路徑隨著環(huán)境的變化而變化，稱為局部路徑[2]。局部路徑規(guī)劃起到修飾全局路徑的作用，在滿足車輛運(yùn)動學(xué)、動力學(xué)等約束的條件下為車輛求解出一條最優(yōu)路徑。因此，選擇合適的局部路徑規(guī)劃算法，對提高智能車輛行駛的平穩(wěn)性和合理性至關(guān)重要。

目前智能車輛常用的局部路徑規(guī)劃算法可分為基于勢場的算法、基于圖搜索的算法、基于隨機(jī)采樣的算法和基于離散優(yōu)化的算法。本文從搜索效率、尋優(yōu)能力、約束條件、軌跡平滑性等方面分析了它們的優(yōu)缺點(diǎn)，并整理分析了各學(xué)者將傳統(tǒng)算法應(yīng)用至智能車輛上時(shí)所提出的改進(jìn)算法，為今后該領(lǐng)域的研究人員提供參考。

1 局部路徑規(guī)劃算法

1.1 基于勢場的算法

KHATIB最早提出了基于勢場概念的人工勢場（Artificial Potential Field, APF）算法，當(dāng)時(shí)主要用于解決機(jī)械臂和機(jī)器人的動態(tài)避障問題[3]。APF算法無需對全局路徑進(jìn)行搜索，計(jì)算代價(jià)小，規(guī)劃效率高，便于底層實(shí)時(shí)控制，近年來在智能車輛上得到了廣泛應(yīng)用。APF算法的基本思想是將車輛在空間中的運(yùn)動虛擬成一個(gè)質(zhì)點(diǎn)在虛擬勢場中的受力運(yùn)動，如圖1所示，目標(biāo)點(diǎn)對車輛產(chǎn)生引力場，引導(dǎo)車輛朝向其運(yùn)動，障礙物對車輛產(chǎn)生斥力場，避免物體與之發(fā)生碰撞，車輛在引力場和斥力場的共同作用下朝著目標(biāo)點(diǎn)運(yùn)動[4]。當(dāng)車輛所受引力與斥力大小相等、方向相反時(shí)，所受合力為零，此時(shí)車輛陷入局部極小值點(diǎn)。目標(biāo)點(diǎn)是整個(gè)勢場中的全局極小值點(diǎn)，然而復(fù)雜勢場中除了目標(biāo)點(diǎn)以外的其他局部區(qū)域內(nèi)也存在極小值點(diǎn)，將導(dǎo)致車輛在到達(dá)目標(biāo)點(diǎn)之前就停止在局部極小值點(diǎn)[5]。

圖1 傳統(tǒng)APF算法原理圖

將APF算法應(yīng)用至車輛上時(shí)，不僅要考慮勢場函數(shù)建模的合理性，還要考慮車輛本身運(yùn)動的復(fù)雜性。智能車輛在行駛的過程中，一方面受到道路邊界的約束，另一方面受到車輛自身的約束。然而傳統(tǒng)的APF算法中，車輛的運(yùn)動只受到引力和斥力的約束，并未考慮道路邊界等各類約束條件，不適合結(jié)構(gòu)化道路場景下的路徑規(guī)劃，車輛無法得到合理的路徑，甚至規(guī)劃失敗[6]。為保證車輛滿足各類約束條件，并順利到達(dá)目標(biāo)點(diǎn)，各學(xué)者對其展開了研究。修彩靖等[7]通過在斥力場中引入調(diào)節(jié)因子建立了改進(jìn)的APF模型，消除了局部極小值點(diǎn)的現(xiàn)象；并基于高斯組合隸屬函數(shù)建立了考慮運(yùn)動學(xué)約束、動力學(xué)約束和障礙物約束的引力目標(biāo)點(diǎn)函數(shù)，最后建立了道路邊界約束模型，實(shí)現(xiàn)了智能車輛安全平穩(wěn)的路徑規(guī)劃。安林芳等[8]提出了一種以避障換道思想構(gòu)建障礙點(diǎn)模型的方法，同時(shí)結(jié)合車輛動力學(xué)和運(yùn)動學(xué)約束，解決了目標(biāo)不可達(dá)和局部最小值問題。吳乙萬等[9]提出了一種基于動態(tài)虛擬障礙物的路徑規(guī)劃算法，在算法中加入動力學(xué)和運(yùn)動學(xué)約束，解決了APF算法無法直接應(yīng)用于智能車路徑規(guī)劃的問題。GU等[10]提出了APF-FC融合算法，利用模糊控制思想使車輛從局部極小值點(diǎn)逃離。RASEKHIPOUR等[11]提出了一種APF算法和模型預(yù)測控制（Model Predictive Control, MPC）器相結(jié)合的路徑規(guī)劃控制器，既能對不同的障礙物和道路結(jié)構(gòu)分布不同的勢函數(shù)，保證車輛遵守交通規(guī)則，又能利用車輛動力學(xué)來規(guī)劃最優(yōu)路徑。

1.2 基于圖搜索的算法

基于圖搜索的方法依靠已知的環(huán)境地圖信息構(gòu)造從起點(diǎn)到終點(diǎn)的可行路徑，主要包括Dijkstra、A*、D*、D* lite等算法。

Dijkstra算法是一種廣度優(yōu)先的狀態(tài)空間搜索算法，算法從起始點(diǎn)開始計(jì)算相鄰點(diǎn)與起始點(diǎn)的距離，將計(jì)算距離最近的點(diǎn)作為新的起始點(diǎn)再次計(jì)算相鄰點(diǎn)與起始點(diǎn)的距離，逐層向外擴(kuò)展，直到到達(dá)目標(biāo)點(diǎn)。這種算法得到的路徑最短，但大大增加了搜索數(shù)據(jù)量和計(jì)算時(shí)間[12]。A*算法是在Dijkstra算法基礎(chǔ)上衍生而來的一種典型的啟發(fā)式搜索算法，如圖2所示，其通過建立節(jié)點(diǎn)估價(jià)函數(shù)來決定搜索方向，減少了盲目搜索的范圍，其估價(jià)函數(shù)表達(dá)式為

()=()+() （1）

式中，()為節(jié)點(diǎn)的估價(jià)函數(shù)；()為在狀態(tài)空間從初始節(jié)點(diǎn)到節(jié)點(diǎn)的實(shí)際代價(jià)，它決定了搜索范圍，節(jié)點(diǎn)越多，搜索效率越低；()為從節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最優(yōu)路徑的估計(jì)代價(jià)，()的取值有曼哈頓距離和歐幾里得距離等。當(dāng)估計(jì)代價(jià)等于實(shí)際代價(jià)時(shí)，搜索的節(jié)點(diǎn)恰好就是最優(yōu)路徑上的節(jié)點(diǎn)，搜索效率最高[13]。為提高搜索效率，馬飛等[14]提出一種匹配運(yùn)動軌跡的擴(kuò)展節(jié)點(diǎn)方法。李瓊瓊等[15]在啟發(fā)函數(shù)里引入搜索優(yōu)先級信息。D*算法是在A*算法的基礎(chǔ)上改進(jìn)而來的動態(tài)路徑搜索算法，D* lite算法是在D*算法的基礎(chǔ)上提出的，其采用從目標(biāo)點(diǎn)向當(dāng)前點(diǎn)搜索的反向搜索方式。當(dāng)車輛在行駛過程中遇到動態(tài)障礙物時(shí)，基于上次規(guī)劃的路徑信息的基礎(chǔ)上再次搜索路徑，從而避免對相同數(shù)據(jù)的重復(fù)計(jì)算，提高了重規(guī)劃的效率[16]。

圖2 傳統(tǒng)A*算法曼哈頓距離搜索原理圖

傳統(tǒng)的圖搜索算法應(yīng)用至智能車輛作局部路徑規(guī)劃時(shí)，智能車輛被看作質(zhì)點(diǎn)處理，未考慮車輛的非完整運(yùn)動學(xué)約束和最大轉(zhuǎn)向角，規(guī)劃的路徑是一系列線段的相互拼接，轉(zhuǎn)折點(diǎn)較多，使得規(guī)劃路徑不能被底層控制模塊很好地實(shí)現(xiàn)。針對圖搜索算法存在的問題，DOLGOV等[17]提出一種滿足車輛運(yùn)動學(xué)約束的混合A*路徑搜索算法，并采用數(shù)值優(yōu)化方法對生成路徑進(jìn)行優(yōu)化，車輛的運(yùn)動軌跡接近全局最優(yōu)。齊堯等[18]提出了一種共軛梯度下降法的路徑后處理方法，保證車輛運(yùn)動軌跡的平滑性。楊瑤等[19]在估價(jià)函數(shù)中引入方向代價(jià)和自適應(yīng)障礙物懲罰代價(jià)，使用車輛最大轉(zhuǎn)向角約束優(yōu)化路徑轉(zhuǎn)折點(diǎn)，最后使用自由邊界三次插值算法擬合轉(zhuǎn)折點(diǎn)，使生成的路徑符合智能車運(yùn)動特性。田海波等[20]提出了一種考慮轉(zhuǎn)彎成本并引入預(yù)判斷規(guī)劃策略和冗余拐點(diǎn)剔除策略的改進(jìn)A*算法，生成的整體路徑長度更短，拐點(diǎn)數(shù)量更少。辛煜等[21]提出了一種可沿任意方向搜索的改進(jìn)A*算法，大大減少了路徑中的轉(zhuǎn)折點(diǎn)個(gè)數(shù)。劉曉濤等[22]提出了一種基于支持向量機(jī)（Support Vector Machine, SVM）算法的改進(jìn)D*算法，利用SVM算法對車輛轉(zhuǎn)向位置的局部路徑進(jìn)行平滑優(yōu)化。DAKULOVI?等[23]提出了一種基于二維柵格占據(jù)地圖的雙向搜索D*算法，規(guī)劃的路徑比傳統(tǒng)的D*算法更合理。FERGUSON等[24]提出了一種柵格內(nèi)線性插值的改進(jìn)D*lite算法，生成的路徑點(diǎn)不局限于柵格中心點(diǎn)，線段之間的連接更為平滑。

1.3 基于隨機(jī)采樣的算法

基于隨機(jī)采樣的路徑規(guī)劃算法分為單查詢算法和漸近最優(yōu)算法，前者只要找到可行路徑即可，側(cè)重快速性，后者會對找到的路徑進(jìn)行優(yōu)化，側(cè)重最優(yōu)性。常用的單查詢算法有概率路圖（Proba- bilistic Roadmap, PRM）、快速隨機(jī)擴(kuò)展樹（Rapi- dly-exploring Random Trees, RRT）和RRT-Connect等算法，漸近最優(yōu)算法有RRT*等算法。

傳統(tǒng)的PRM算法分為離線學(xué)習(xí)階段和查詢階段。離線學(xué)習(xí)階段的主要內(nèi)容是，在地圖空間中隨機(jī)采集一定數(shù)量的節(jié)點(diǎn)，之后每個(gè)采樣點(diǎn)與其附近一定距離內(nèi)的采樣點(diǎn)連接，去除采樣點(diǎn)間穿越障礙物區(qū)域的連接，形成路徑網(wǎng)絡(luò)圖。查詢階段的主要內(nèi)容是采用圖搜索等算法尋找起點(diǎn)和目標(biāo)點(diǎn)間的無碰撞路徑[25]。采樣點(diǎn)的數(shù)量決定了搜索到路徑的概率大小，采樣點(diǎn)的數(shù)量過少，可能無法完成路徑搜索。鄒善席等[26]在PRM算法中引入隨機(jī)節(jié)點(diǎn)生成函數(shù)，取代落在障礙物中的采樣節(jié)點(diǎn)，保證采樣節(jié)點(diǎn)數(shù)量不變；并利用節(jié)點(diǎn)增強(qiáng)法對路徑進(jìn)行優(yōu)化，縮短了整體路徑長度，提高了路徑的平滑度。

RRT算法是一種基于樹結(jié)構(gòu)的經(jīng)典算法，如圖3所示。算法流程為（1）初始化起點(diǎn)，終點(diǎn)，擴(kuò)展樹T={起點(diǎn)}；（2）在自由空間中隨機(jī)采樣得到采樣點(diǎn)rand；（3）從擴(kuò)展樹T中找到距離采樣點(diǎn)rand最近的節(jié)點(diǎn)near；（4）計(jì)算near與rand之間的距離，若大于步長，則從near向rand移動后得到新的節(jié)點(diǎn)new，否則，在rand位置生成新的節(jié)點(diǎn)new；（5）若new和near之間存在直線通路，則將new加入擴(kuò)展樹T，其父節(jié)點(diǎn)為near；（6）循環(huán)上述步驟，直到加入擴(kuò)展樹T的節(jié)點(diǎn)new與終點(diǎn)間的距離小于一定閾值[27]。

圖3 傳統(tǒng)RRT算法原理圖

RRT算法以隨機(jī)采樣的方式獲得無碰撞路徑，不需要進(jìn)行預(yù)處理，因此，搜索速度很快。同時(shí)該算法考慮了運(yùn)動學(xué)約束和動力學(xué)約束，可用于智能車輛的路徑規(guī)劃，但還是存在一些不足：（1）由于算法的搜索側(cè)重快速性，導(dǎo)致規(guī)劃的路徑不是最優(yōu)的；（2）采樣點(diǎn)缺乏導(dǎo)向機(jī)制，存在很多冗余搜索，影響算法的收斂速度；（3）采樣的隨機(jī)性導(dǎo)致采樣點(diǎn)間跳動較大，甚至出現(xiàn)相鄰采樣點(diǎn)間的角度達(dá)到直角的現(xiàn)象[28]。

針對傳統(tǒng)RRT算法的缺陷，學(xué)者們提出了不同的改進(jìn)RRT算法。KARAMAN等[29]在RRT算法的基礎(chǔ)上提出了漸進(jìn)最優(yōu)的RRT*算法。RRT*與RRT的算法流程基本相同，但節(jié)點(diǎn)new的父節(jié)點(diǎn)的選擇策略不同。RRT*算法以節(jié)點(diǎn)new為圓心，在半徑的鄰域，選擇路徑代價(jià)最小的節(jié)點(diǎn)作為新的父節(jié)點(diǎn)，代替new，從而生成的路徑較短，但未考慮節(jié)點(diǎn)間長度小于探索步長的問題。趙港[30]在RRT*算法中引入歐氏距離對次級節(jié)點(diǎn)的選擇進(jìn)行限制，避免因節(jié)點(diǎn)間距離過短而導(dǎo)致采樣點(diǎn)間曲率變化大的現(xiàn)象。

為減少冗余搜索，提高搜索速度，KUFFNER等[31]提出RRT-Conect算法，該算法分別以起點(diǎn)和目標(biāo)點(diǎn)為根節(jié)點(diǎn)生成兩棵樹進(jìn)行雙向搜索；宋曉琳等[31]在RRT算法中引入啟發(fā)式搜索機(jī)制；TAHERI等[32]提出了一種基于模糊貪婪策略的改進(jìn)RRT算法；ELBANHAWI等[33]提出了一種兩階段規(guī)劃的RRT算法；ZUO等[34]將A*算法作為RRT算法的第一層幾何路徑規(guī)劃。

為使規(guī)劃路徑能夠滿足車輛的運(yùn)動學(xué)特性，宋曉琳等[28]建立道路約束模型，使隨機(jī)采樣點(diǎn)在期望路徑模型上呈現(xiàn)高斯分布，最后采用三次B樣條曲線擬合路徑；ZUO等[34]采用最小二乘策略迭代算法對生成的路徑進(jìn)行優(yōu)化。杜明博等[35]基于RRT算法框架提出了一種考慮車輛自身約束和環(huán)境約束的連續(xù)曲率RRT算法，同時(shí)基于最大曲率約束的后處理方法生成平滑的車輛軌跡；周維等[36]采用目標(biāo)導(dǎo)向、修剪無用節(jié)點(diǎn)、五次多項(xiàng)式曲線擬合以及引入權(quán)重系數(shù)的聯(lián)合策略得到滿足車輛運(yùn)動學(xué)約束的最優(yōu)路徑。

1.4 基于離散優(yōu)化的算法

基于離散優(yōu)化思想的路徑規(guī)劃算法是基于積分和微分等高等數(shù)學(xué)方法來描述車輛的行駛軌跡，從而生成一定數(shù)量的候選路徑，最后根據(jù)不同的評價(jià)標(biāo)準(zhǔn)從候選路徑中選擇一條最優(yōu)路徑[37]，如圖4所示。這種方法得到的路徑更優(yōu)更合理，實(shí)時(shí)性較好，在智能車輛上得到了廣泛應(yīng)用[38]。

圖4 基于離散優(yōu)化的算法原理圖

為滿足智能車輛的各類約束，該類算法通常將車輛的運(yùn)動解耦成多個(gè)子規(guī)劃，實(shí)現(xiàn)車輛的縱橫向規(guī)劃或速度、轉(zhuǎn)向角規(guī)劃。姜巖等[39]提出一種基于運(yùn)動微分約束的縱橫向協(xié)同路徑規(guī)劃算法，利用高階多項(xiàng)式模型在預(yù)瞄距離內(nèi)對可行駛曲線進(jìn)行建模，生成候選曲線集合。魏民祥等[40]利用Frenet坐標(biāo)系將車輛運(yùn)動解耦，構(gòu)建以加速度變化率為核心的一維縱向、橫向獨(dú)立積分系統(tǒng)，通過5次、4次多項(xiàng)式分別求解得到有限的橫向、縱向候選軌跡集合。陳成等[41]將車輛運(yùn)動解耦成軌跡規(guī)劃和速度規(guī)劃，提出一種基于四階貝塞爾曲線的軌跡規(guī)劃方法。張琳[42]等提出了一種基于滾動窗口優(yōu)化的車輛軌跡生成方法，采用啟發(fā)式搜索獲得滿足約束條件的目標(biāo)候選軌跡。ZHANG等[43]提出一種分層式軌跡規(guī)劃方法，第一層生成不考慮運(yùn)動學(xué)約束的最短路徑，第二層基于多相位狀態(tài)采樣方法，在最短路徑的附近進(jìn)行采樣，生成運(yùn)動學(xué)可行的路徑集合。

為從候選曲線中選擇最優(yōu)曲線，各學(xué)者提出了不同的選擇方法。姜巖等[39]通過碰撞安全性分析選擇一條曲線作為跟隨或超車場景下的待執(zhí)行曲線。魏民祥等[40]基于高斯卷積、加速度變化率分別構(gòu)建損失函數(shù)來評價(jià)候選軌跡的安全性和舒適性，損失函數(shù)中各加權(quán)項(xiàng)和加權(quán)系數(shù)共同決定最優(yōu)軌跡的選擇。陳成等[41]采用序列二次規(guī)劃算法求解得到最優(yōu)運(yùn)動軌跡。張琳等[42]引入度量函數(shù)決策出當(dāng)前窗口下局部最優(yōu)軌跡。ZHANG等[43]基于無導(dǎo)數(shù)平滑算法對路徑進(jìn)行平滑，為多相位狀態(tài)采樣避障提供正確引導(dǎo)信息。R?SMANN等[44]通過調(diào)節(jié)各類軟約束所占權(quán)重來獲得期望的車輛運(yùn)動軌跡。周慧子等[45]提出一種考慮安全性、舒適性、連續(xù)性的代價(jià)函數(shù)，從候選路徑中選擇代價(jià)函數(shù)最小的路徑作為行駛路徑。

2 總結(jié)與展望

本文總結(jié)了目前智能車輛常用的局部路徑規(guī)劃算法，并具體分析了不同算法之間的優(yōu)缺點(diǎn)，可獲得以下結(jié)論：

（1）基于勢場法的算法計(jì)算代價(jià)小、規(guī)劃效率高，但容易陷入局部極小值點(diǎn)；基于圖搜索的算法規(guī)劃的路徑最短，但搜索時(shí)間長；基于隨機(jī)采樣的算法搜索速度快，但路徑不是最優(yōu)的；基于離散優(yōu)化的算法在候選曲線集合中選擇最優(yōu)的路徑，得到的路徑更合理，但存在大量的復(fù)雜數(shù)學(xué)運(yùn)算，實(shí)時(shí)性有待進(jìn)一步提高。這些傳統(tǒng)算法有一個(gè)共性問題，對道路環(huán)境、交通規(guī)則、非完整運(yùn)動學(xué)、運(yùn)動學(xué)以及動力學(xué)等約束沒有考慮或約束不足。

（2）為保證車輛滿足各類約束條件，目前的解決方法可分為兩類，一是在搜索函數(shù)里配置各類約束信息，二是采用數(shù)學(xué)方法或結(jié)合其他算法的優(yōu)勢對生成的路徑進(jìn)行處理和優(yōu)化?；陔x散優(yōu)化的算法將車輛運(yùn)動解耦，分層式規(guī)劃，既考慮約束條件，又基于數(shù)學(xué)方法或其他算法優(yōu)化候選路徑曲線，得到的路徑更為合理。因此，基于離散優(yōu)化的算法將是未來智能車輛局部路徑規(guī)劃的應(yīng)用趨勢。

（3）當(dāng)空間的緯度、障礙物的密度以及車輛的行駛速度增加時(shí)，計(jì)算復(fù)雜度和計(jì)算時(shí)間將呈指數(shù)級增加，僅僅靠單一的算法不能滿足需求，將多種算法的優(yōu)點(diǎn)進(jìn)行融合，將是未來該研究領(lǐng)域的熱點(diǎn)與難點(diǎn)。同時(shí)，車輛的底層控制算法決定了車輛的規(guī)劃軌跡和實(shí)際行駛軌跡之間的誤差大小，因此，如何協(xié)調(diào)好路徑規(guī)劃算法和底層控制算法之間的關(guān)系也是研究的難點(diǎn)。

[1] 鄭凱林,韓寶玲,王新達(dá).基于改進(jìn)TEB算法的阿克曼機(jī)器人運(yùn)動規(guī)劃系統(tǒng)[J].科學(xué)技術(shù)與工程,2020,20 (10):3997-4003.

[2] 彭曉燕,謝浩,黃晶.無人駕駛汽車局部路徑規(guī)劃算法研究[J].汽車工程,2020,42(1):1-10.

[3] KHATIB O.Real-time Obstacle Avoidance System for Manipulators and Mobile Robots[J].The Interna- tional Journal of Robotics Research,1986,5(1):90-98.

[4] 余政.基于改進(jìn)人工勢場法的智能汽車超車軌跡規(guī)劃策略[J].農(nóng)業(yè)裝備與車輛工程,2021,59(9):64-68.

[5] 朱毅,張濤,宋靖雁.未知環(huán)境下勢場法路徑規(guī)劃的局部極小問題研究[J].自動化學(xué)報(bào),2010,36(8):1122-1130.

[6] 陳宇珂,林棻,王少博.基于障礙物勢場和模型預(yù)測的車輛避障路徑規(guī)劃[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)), 2020,34(10):34-41.

[7] 修彩靖,陳慧.基于改進(jìn)人工勢場法的無人駕駛車輛局部路徑規(guī)劃的研究[J].汽車工程,2013,35(9):808- 811.

[8] 安林芳,陳濤,成艾國,等.基于人工勢場算法的智能車輛路徑規(guī)劃仿真[J].汽車工程,2017,39(12):1451-1456.

[9] 吳乙萬,黃智.基于動態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[J].湖南大學(xué)學(xué)報(bào)(自然科學(xué)版),2013, 40(1):33-37.

[10] GU X, HAN M, ZHANG W, et al.Intelligent Vehicle Path Planning Based on Improved Artificial Potential Field Algorithm[C]//2019 International Conference on High Performance Big Data and Intelligent Systems. New York:IEEE,2019:104-109.

[11] RASEKHIPOUR Y,KHAJEPOUR A,CHEN S K,et al. A Potential Field-based Model Predictive Path-plan- ning Controller for Autonomous Road Vehicles[J]. IEEE Transactions on Intelligent Transportation Systems, 2017,18(5): 1255-1267.

[12] GUO Q,ZHENG Z,YUE X.Path-planning of Automa- ted Guided Vehicle Based on Improved Dijkstra Algorithm[C]//2017 29h Chinese Control & Decision Conference.New York:IEEE,2017:7138-7143.

[13] 徐瑞,李軍.無人駕駛汽車局部路徑規(guī)劃研究綜述[J].汽車科技,2020(5): 84-89.

[14] 馬飛,楊皞屾,顧青,等.基于改進(jìn)A*算法的地下無人鏟運(yùn)機(jī)導(dǎo)航路徑規(guī)劃[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2015,46(7): 303-309.

[15] 李瓊瓊,施楊洋,布升強(qiáng),等.基于改進(jìn)A*算法的無人車路徑規(guī)劃研究[J].林業(yè)機(jī)械與木工設(shè)備,2020,48 (6):45-49.

[16] 張毅,施明瑞.基于單元分解的改進(jìn)D* lite路徑規(guī)劃算法[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2021,33(6): 1007-1013.

[17] DOLGOV D, THRUN S, MONTEMERLO M, et al. Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments[J].The International Journal of Robotics Research,2010,29(5):485-501.

[18] 齊堯,徐友春,李華,等.一種基于改進(jìn)混合A*的智能車路徑規(guī)劃算法[J].軍事交通學(xué)院學(xué)報(bào),2018,20(8): 85-90.

[19] 楊瑤,付克昌,蔣濤,等.一種改進(jìn)A*算法在智能車中的應(yīng)用研究[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)),2021, 35(3):71-79.

[20] 田海波,李陸軍,暢科劍,等.用于無人車路徑規(guī)劃的改進(jìn) A*算法[J].現(xiàn)代制造工程,2021(11):63-68,92.

[21] 辛煜,梁華為,杜明博,等.一種可搜索無限個(gè)鄰域的改進(jìn)A*算法[J].機(jī)器人,2014,36(5):627-633.

[22] 劉曉濤,蔡云飛,王田橙.基于SVM的受約束D*算法在無人車尋路中的應(yīng)用[J].計(jì)算機(jī)與數(shù)字工程,2017, 45(9): 1748-1754.

[23] DAKULOVI? M, PETROVI? I.Two-way D*Algori- thm for Path Planning and Replanning[J].Robotics and Autonomous Systems,2011,59(5):329-342.

[24] FERGUSON D,STENTZ A.Field D*:An Interpolation- Based Path Planner and Replanner[M].Berlin Springer, 2007.

[25] KAVRAKI L E,SVESTKA P, LATOMBE J C, et al. Probabilistic Roadmaps for Path Planning in High- dimensional Configuration Spaces[J].IEEE Transac- tions on Robotics and Automation,1996,12(4):566-580.

[26] 鄒善席,王品,韓旭.基于PRM改進(jìn)的路徑規(guī)劃算法[J].組合機(jī)床與自動化加工技術(shù),2019(1):1-3.

[27] LAVALLE S M. Rapidly-exploring Random Trees:A New Tool for Path Planning[J].Research Report,1999.

[28] 宋曉琳,周南,黃正瑜,等.改進(jìn)RRT在汽車避障局部路徑規(guī)劃中的應(yīng)用[J].湖南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2017,44(4):30-37.

[29] KARAMAN S,FRAZZOLI E.Sampling-based Algori- thms for Optimal Motion Planning[J].The International Journal of Robotics Research,2011,30(7):846-894.

[30] 趙港.改進(jìn)RRT*算法的智能車輛路徑規(guī)劃[J].汽車實(shí)用技術(shù),2021,46(22):41-43.

[31] KUFFNER J J,LAVALLE S M.RRT-Connect:An Effic- ient Approach to Single-query Path Planning[C]//Pro- ceedings of the 2000 IEEE International Conference on Robotics and Automation. New York: IEEE,2000: 995-1001.

[32] TAHERI E, FERDOWSI M H, DANESH M. Fuzzy Greedy RRT Path Planning Algorithm in a Complex Configuration Space[J].International Journal of Con- trol, Automation and Systems,2018,16(6): 3026-3035.

[33] ELBANHAWI M, SIMIC M. Randomised Kinodyna- mic Motion Planning for an Autonomous Vehicle in Semi-structured Agricultural Areas[J]. Biosystems Engineering,2014,126:30-44.

[34] ZUO L,GUO Q,XU X, et al. A Hierarchical Path Planning Approach Based on A and Least-squares Policy Iteration for Mobile Robots[J].Neurocomput- ing,2015,170(25): 257-266.

[35] 杜明博,梅濤,陳佳佳,等.復(fù)雜環(huán)境下基于RRT的智能車輛運(yùn)動規(guī)劃算法[J].機(jī)器人,2015,37(4):443-450.

[36] 周維,過學(xué)迅,裴曉飛,等.基于RRT與MPC的智能車輛路徑規(guī)劃與跟蹤控制研究[J].汽車工程,2020,42 (9):1151-1158.

[37] WERLING M,ZIEGLER J,KAMMEL S,et al.Optimal Trajectory Generation for Dynamic Street Scenarios in a Frenet Frame[C]//2010 IEEE International Confe- rence on Robotics and Automation.New York:IEEE, 2010: 987-993.

[38] CHU K, LEE M, SUNWOO M. Local Path Planning for Off-road Autonomous Driving with Avoidance of Static Obstacles[J].IEEE Transactions on Intelligent Transportation Systems,2012,13(4):1599-1616.

[39] 姜巖,龔建偉,熊光明,等.基于運(yùn)動微分約束的無人車輛縱橫向協(xié)同規(guī)劃算法的研究[J].自動化學(xué)報(bào),2013, 39(12):2012-2020.

[40] 魏民祥,滕德成,吳樹凡.基于Frenet坐標(biāo)系的自動駕駛軌跡規(guī)劃與優(yōu)化算法[J].控制決策,2021,36(4): 815-824.

[41] 陳成,何玉慶,卜春光,等.基于四階貝塞爾曲線的無人車可行軌跡規(guī)劃[J].自動化學(xué)報(bào),2015,41(3): 486-496.

[42] 張琳,章新杰,郭孔輝,等.未知環(huán)境下智能汽車軌跡規(guī)劃滾動窗口優(yōu)化[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),2018,48 (3):652-660.

[43] ZHANG Y,CHEN H Y,WASLANDER S L,et al.Hy- brid Trajectory Planning for Autonomous Driving in Highly Constrained Environments[J].IEEE Access, 2018(6):32800-32819.

[44] R?SMANN C,HOFFMANN F,BERTRAM T. Kinod- ynamic Trajectory Optimization and Control for Car-like Robots[C]//2017 IEEE/RSJ International Conference on Intelligent Robots and Systems.New York:IEEE,2017:5681-5686.

[45] 周慧子,胡學(xué)敏,陳龍,等.面向自動駕駛的動態(tài)路徑規(guī)劃避障算法[J].計(jì)算機(jī)應(yīng)用,2017,37(3):883-888.

Review on Local Path Planning Algorithm for Intelligent Vehicle

MA Xiaolu, LI Ruyi*, WU Lihui

( School of Mechanical and Electrical Engineering, Henan University of Technology, Zhengzhou 450001, China )

In order to improve the driving stability and rationality of intelligent vehicles, this paper classifies and summarizes the local path planning algorithms commonly used by intelligent vehicles in recent years. Firstly, this paper expounds the principles of various traditional algorithms, analyzes their advantages and disadvantages, and points out the shortcomings of traditional algorithms in the application of intelligent vehicles. Secondly, this paper sorts out and analyzes the improved algorithms proposed by scholars when various traditional algorithms are applied to intelligent vehicles. Finally, it is proposed that the algorithm based on discrete optimization is the application trend of intelligent vehicle local path planning in the future, and the fusion of multiple algorithms is the research direction of intelligent vehicle local path planning in complex scenarios. The research results of this paper can provide reference for researchers in the field of intelligent vehicles when choosing local path planning algorithms.

Intelligent vehicle; Path planning algorithm; Local path planning;Discrete optimization;Fusion of multiple algorithms

U471.1

A

1671-7988(2022)23-232-06

U471.1

A

1671-7988(2022)23-232-06

10.16638/j.cnki.1671-7988.2022.023.043

馬曉錄（1964—），男，博士，教授，研究方向?yàn)橹悄芪锪餮b備，E-mail:maxiaolu@haut.edu.cn。

李如意（1995—），男，碩士研究生，研究方向?yàn)橹悄苘囕v的定位與路徑規(guī)劃，E-mail:ruyi_li1995@163.com。

國家自然科學(xué)基金（U1704156）。