周偉 李軍

（重慶交通大學）

隨著人工智能技術(shù)的興起，以自動駕駛車輛為研究對象的運動路徑規(guī)劃問題越來越受到重視。而避障路徑規(guī)劃是自動駕駛車輛的關(guān)鍵部分，對自動駕駛車輛的研究具有重大意義。在自動駕駛汽車行駛過程中，準確地避開障礙物是智能車輛的基本要求。一個好的避障路徑規(guī)劃算法可以安全實時地避開障礙物，且具有較高的乘坐舒適性，從而提高出行效率。文章總結(jié)了目前文獻中經(jīng)常出現(xiàn)的各種適用于自動駕駛車輛路徑規(guī)劃的算法，分別從算法路徑尋優(yōu)能力、算法實時性及算法復雜度等方面分析比較了它們在理論上的優(yōu)勢和缺點，為今后的深入研究提供參考。

1　避障技術(shù)分析

自動汽車避障技術(shù)主要是利用先進的傳感器技術(shù)來增強汽車對行駛環(huán)境的感知能力，將感知系統(tǒng)獲取的車速、位置等實時信息反饋給系統(tǒng)，同時根據(jù)路況與車流的綜合信息判斷和分析潛在的安全隱患，并在緊急情況下自動采取報警提示、制動或轉(zhuǎn)向等措施協(xié)助和控制汽車主動避開障礙，保證車輛安全、高效和穩(wěn)定地行駛[1]。采用人工勢場法的智能車輛避障原理，如圖1所示。

圖1　智能車輛避障原理圖

文獻[2]將避障問題看成有約束的多目標優(yōu)化問題，而避障問題的處理前提就在于如何根據(jù)當前障礙物信息以及自身狀態(tài)信息決策出該采取何種基本駕駛子操作（分為左換道、右換道、跟隨巡航及制動）。

2　局部危險避障算法研究

2.1　智能車局部危險避障概述

自動駕駛車輛作為一種具有自主決策能力的智能機器人，需要從外部環(huán)境獲取信息并根據(jù)信息做出決策，從而進行全局路徑規(guī)劃和局部危險狀況下的避障。

自動駕駛車輛的全局路徑規(guī)劃為車輛規(guī)劃出了一條在已知環(huán)境地圖信息下的最優(yōu)路徑。車輛在前進過程中，處在不可預(yù)測和高度動態(tài)的城市道路環(huán)境中，障礙物很可能出現(xiàn)在已經(jīng)規(guī)劃好的全局路徑上，也有可能在前進的過程中一些障礙（行人或車輛等）動態(tài)地出現(xiàn)在路徑上。自動駕駛車輛必須對這些不可預(yù)測的事件以某種方式做出反應(yīng)，進行局部避障，使之仍然能夠順利到達目的地、完成任務(wù)。因此，局部避障必須速度快、實時性好和效率高，而可靠的避障算法正是保證自動駕駛車輛成功避障的主要方法。因此，在全局路徑規(guī)劃的基礎(chǔ)上，還需要進行實時的局部危險避障。目前，對于自動駕駛車輛動態(tài)目標及城市道路區(qū)域的相關(guān)避障方法的研究，正是智能駕駛車輛研究的熱點和重要方向，也是一項實現(xiàn)車輛智能化的關(guān)鍵技術(shù)。

2.2　傳統(tǒng)避障算法

目前局部避障算法也有很多成熟的算法，每個算法的優(yōu)缺點也不一樣。目前所采用的方法主要有人工勢場法（Artificial Potential Field，APF）和虛擬力場法（Virtual Force Field，VFF）等。

人工勢場法是一種虛擬力法，它的基本思想是把車輛在周圍環(huán)境中的運動視為車輛在人工建立的虛擬力場中的運動。目標點產(chǎn)生引力，引導車輛向目標點運動。障礙物產(chǎn)生斥力，避免車輛與障礙物發(fā)生碰撞，車輛在二者的合力下運動。根據(jù)引力和斥力的合力來控制車輛的運動，即車輛搜索沿著勢場下降的方向運動，產(chǎn)生一條無碰撞的最優(yōu)路徑。

應(yīng)用人工勢場法規(guī)劃出來的路徑一般比較平滑且安全，算法簡明，實時性良好，適合無人駕駛智能車領(lǐng)域。但是該算法也存在一些缺點，如當目標點附近有障礙物時，斥力遠遠大于引力，車輛將很難到達目的地；當智能車輛在某一點的引力和斥力剛好大小相等時，智能車將會陷入局部最優(yōu)點；傳統(tǒng)的人工勢場只考慮了障礙物與目標點靜止不動的靜態(tài)環(huán)境，而車輛實際是在運動的環(huán)境中，因此在動態(tài)環(huán)境無法取得良好的效果。

針對傳統(tǒng)人工勢場的改進，大量學者展開研究，文獻[3]利用高斯組合隸屬函數(shù)建立引力的目標點函數(shù)，在引力點函數(shù)中考慮障礙物約束和車輛約束，并引入調(diào)節(jié)因子，建立了改進的無人駕駛汽車人工勢場模型，消除了傳統(tǒng)人工勢場法容易陷入局部極小的問題。文獻[4]通過調(diào)整勢力場范圍、改進斥力勢函數(shù)和動態(tài)調(diào)整斥力場系數(shù)，解決了陷入局部極小值的情況。文獻[5]在人工勢場中加入速度元素，能夠規(guī)劃出同時避開靜態(tài)和動態(tài)障礙物且能到達目標點的理想路徑。文獻[6]解決了傳統(tǒng)APF算法在無人車避障應(yīng)用中虛擬勢場作用域固定、避障角度過大的問題。

虛擬力場法是柵格法和人工勢場法結(jié)合的一種移動機器人實時避障算法。VFF算法是使用柵格來表示環(huán)境,同時使用力場法對無人車進行控制的局部避障算法。

2.3　智能優(yōu)化算法

智能優(yōu)化算法一般都是建立在生物智能或物理現(xiàn)象基礎(chǔ)上的隨機搜索算法，包括模糊邏輯算法（Fuzzy Logic Algorithm，F(xiàn)LA）、遺傳算法（Genetic Algorithms，GA）、快速擴展隨機樹 (Rapidly Random-exploring Trees，RRT)、蟻群算法[7]、水滴算法[8]、觸須算法[9]及粒子群算法[10]（Particle SwarmOptimization，PSO）等。

模糊邏輯算法主要是根據(jù)人類駕駛經(jīng)驗，設(shè)計出一個模糊控制規(guī)則庫。將傳感器獲得的信息作為輸入，經(jīng)過模糊推理后得出車輛所需要的輸出，一般輸出為速度和導航角。因為智能車輛的運動學模型具有非線性和強耦合性的特點，而模糊控制避障算法不依賴受控對象的精確運動模型，因此采用模糊控制避障算法也是研究中經(jīng)常采用的方法之一。但模糊規(guī)則往往是人們通過經(jīng)驗預(yù)先制定的，所以存在無法學習和靈活性差的缺點，且模糊規(guī)則數(shù)量隨著輸入的增多呈指數(shù)倍增長。

文獻[11]針對移動機器人設(shè)計了一個模糊控制器，將通過安裝在機器人前方180°范圍內(nèi)的超聲波和紅外傳感器采集的障礙物距離信息以及電子羅盤獲取的目標方位角作為模糊控制器的輸入，機器人左右輪的速度作為輸出。在隸屬度函數(shù)的選擇上，采用高斯型隸屬度函數(shù)，因為高斯型隸屬度函數(shù)曲線較為平滑，具有較好的準確性和簡潔性。

文獻[12]采用分層分級的思想，將避障過程分為車輛繞開障礙物過程和車輛趨向目標過程的新方法，分別設(shè)計了一個避障行為控制器和目標趨向控制器，減少了算法的計算量和提高了運算速度。模糊控制系統(tǒng)分層結(jié)構(gòu)圖，如圖2所示。

圖2　模糊控制系統(tǒng)分層結(jié)構(gòu)圖

遺傳算法[13]是模擬了生物界的進化論原理（適者生存，優(yōu)勝劣汰）演化和遺傳變異達到物種進化的一種智能算法。遺傳算法把路徑點作為一個種群，并按照一定的規(guī)則對每一個路徑點進行編碼，然后根據(jù)適應(yīng)度函數(shù)選擇路徑點，借助遺傳算子進行組合交叉和變異，逐漸演化產(chǎn)生出越來越優(yōu)化的近似解。遺傳算法具有并行計算能力、群體搜索特性與可擴展性，一般不需要輔助信息，但是效率比其他智能優(yōu)化算法低，而且在利用選擇交叉算子時，會丟失一些優(yōu)秀的基因片段，從而導致過早收斂。此外，在編碼環(huán)境中會有較長的計算時間與很大的數(shù)據(jù)存儲空間需求。

文獻[14]對傳統(tǒng)遺傳算法提出了一系列的改進措施，包括可見空間的概念、新的矩陣編碼形式和新的變異算子。通過使用新的變異算子可使快速收斂到全局最優(yōu)，且在靜態(tài)環(huán)境和動態(tài)環(huán)境中都可以快速收斂。

快速擴展隨機樹（RRT）算法[15]是以狀態(tài)空間中的一個初始點作為根節(jié)點，通過隨機采樣擴展，逐漸增加葉節(jié)點，生成一個隨機擴展樹，當隨機樹的葉節(jié)點中包含了目標點或者目標區(qū)域中的點時，從初始點到目標點之間的一條以隨機樹的葉節(jié)點組成的線段就是規(guī)劃出的一條路徑。由于算法在進行路徑規(guī)劃時是隨機采樣，不需要對狀態(tài)空間進行預(yù)處理，因此有著很快的搜索速度，而且還考慮了車輛在運動過程的動力學約束和運動學約束，該算法也非常適用于智能車輛的運動規(guī)劃問題。但RRT算法存在一些不足：

1）度量函數(shù)（最近鄰算法）的合理選取決定算法的合理性和效率；

2）算法的隨機性使得規(guī)劃出的路徑曲率變化過大，甚至出現(xiàn)小范圍的直角變化，導致路徑不平滑，不符合車輛運動學；

3）采樣點在整個可行域內(nèi)隨機采樣的搜索方式存在很多不必要的運算，影響算法速度，降低搜索效率。

針對傳統(tǒng)RRT算法的改進，一些學者也提出了不同的方法。文獻[16]根據(jù)駕駛經(jīng)驗豐富的駕駛員，設(shè)計直道和彎道模型的期望避障路徑模型，最后為了使隨機采樣點分布在期望路徑模型周圍，利用高斯分布函數(shù)生成的點集中在均值周圍的特點，再結(jié)合設(shè)計好的期望路徑函數(shù)，則實現(xiàn)滿足汽車安全穩(wěn)定行駛的路徑。

文獻[17]利用A*算法進行路徑規(guī)劃，根據(jù)規(guī)劃結(jié)果生成引導域來修改RRT隨機采樣過程中的采樣策略，將目標偏向采樣策略和引導域偏向采樣策略相結(jié)合，使得隨機采樣點朝著目標點區(qū)域方向靠近，并在最近鄰搜索過程中加入角度約束，因為智能車輛在行駛過程中有最大轉(zhuǎn)向角限制。文獻[18]提出動態(tài)步長并引入目標引力思想，在傳統(tǒng)RRT算法基礎(chǔ)上，添加動態(tài)步長特性，減少RRT的隨機性，讓路徑朝著目標方向擴展，改善了RRT的不確定性，提高了避障能力。

文獻[19]提出一種連續(xù)曲率RRT算法，該算法在RRT框架中結(jié)合了環(huán)境約束以及車輛自身的約束。它首先采用了目標偏向采樣策略以及合理的度量函數(shù)，保證了算法隨機性的同時也加快了向目標點收斂的速度，大大地提高了規(guī)劃速度和質(zhì)量。最后針對智能車輛的實際應(yīng)用提出基于最大曲率的約束的剪枝函數(shù)對樹進行后處理，刪除不必要的節(jié)點并插入必要的節(jié)點，接著使用3次B樣條曲線對剩余的節(jié)點進行平滑處理以生成平滑且曲率連續(xù)的可執(zhí)行軌跡。文獻[20]采用簡單有效的3次B樣條曲線平滑算法，對路徑點進行曲率連續(xù)的擬合以生成平滑且曲率連續(xù)的智能車可執(zhí)行的平滑路徑。

此外，還有 RRT GoalBias，RRT GoalZoom，RRT*，RRT-Connect等改進方法。

2.4　多種算法結(jié)合

在車輛的實際避障過程中，往往會采用2種或多種算法相結(jié)合，通過互補來提高算法效率。

文獻[21]利用模糊邏輯和遺傳算法構(gòu)建一種智能車輛避障路徑規(guī)劃算法。以智能車輛與目標點及障礙物中心點的角度差、智能車輛與障礙物的距離為輸入量，智能車輛的速度、轉(zhuǎn)角為輸出量，分別建立避障行為模糊規(guī)則表和趨向目標模糊規(guī)則表，設(shè)計模糊控制器，如圖3所示。最后利用遺傳算法對避障行為模糊規(guī)則表進行優(yōu)化，從而實現(xiàn)避障。

圖3　避障模糊控制器結(jié)構(gòu)圖

文獻[22]將RRT算法與基于滾動窗口的路徑規(guī)劃相結(jié)合。采用反復的局部路徑規(guī)劃代替一次性的全局路徑規(guī)劃，保證了算法的實時性。同時以概率來實現(xiàn)隨機采樣取點，并引入啟發(fā)式估價函數(shù)，使隨機樹易于朝著目標點方向生長。

文獻[23]為了避免經(jīng)典人工勢場法（APF）的局部最小值問題，提出一種基于修正APF算法與模糊邏輯相結(jié)合的新方法。該算法克服了局部極小值問題，提高了算法在復雜環(huán)境中的有效性。并使用粒子群優(yōu)化（PSO）算法優(yōu)化模糊邏輯算法的隸屬度函數(shù)。在靜態(tài)和動態(tài)的環(huán)境中響應(yīng)速度快，并能有效避開障礙物。

文獻[24]在移動機器人上結(jié)合蟻群算法和人工勢場法的優(yōu)缺點進行路徑規(guī)劃。提出一種以柵格地圖為環(huán)境模型，在蟻群算法搜索過程中加入針對具體問題的人工勢場局部搜索尋優(yōu)算法，將人工勢場法中力因素轉(zhuǎn)換為局部擴散信息素，使蟻群傾向于具有高適應(yīng)值的子空間搜索，減少了蟻群算法在盲目搜索路徑過程中產(chǎn)生的局部交叉路徑及螞蟻“迷失”數(shù)量，提高了蟻群對障礙物的預(yù)避障能力。隨著自動駕駛技術(shù)的發(fā)展，車輛避障路徑規(guī)劃算法與其他方法結(jié)合，從而更快地優(yōu)化其規(guī)劃過程，將能更準確和迅速地進行避障。

3　結(jié)語

文章主要分析了在局部危險避障環(huán)境中的優(yōu)化算法，對傳統(tǒng)算法和智能算法及其改進算法的優(yōu)缺點做出了分析以及多種算法的聯(lián)合求解。傳統(tǒng)算法和智能算法都可在一定程度上解決自動駕駛車輛避障的問題，每種算法都有其優(yōu)點和局限性。人工勢場法算法簡明，實時性良好，規(guī)劃的路徑軌跡圓滑，適合自動駕駛智能車領(lǐng)域，但存在容易進入局部最小點、目標不可達及碰撞障礙物問題；智能算法在傳統(tǒng)算法的基礎(chǔ)上，引入了更加智能化的計算，如遺傳算法可以同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風險，同時算法本身容易實現(xiàn)并行化。因此在實際情況下，要進行精確、安全和快速的避障僅僅依靠單一算法是有限的。車輛進行局部避障時，可以依靠2種或多種算法進行求解，得出避障路徑，將多種算法的優(yōu)缺點相互融合，產(chǎn)生更加完美的算法將是未來該領(lǐng)域研究的重點與難點。