自動駕駛車輛避障所采用的傳統(tǒng)算法和智能算法

避障作為自動駕駛車輛在行駛過程中非常重要的部分，對發(fā)展自動駕駛車輛具有重要意義。文章介紹了車輛避障技術(shù)，概括了自動駕駛車輛避障所采用的傳統(tǒng)算法和智能算法，分析了各種算法的優(yōu)缺點(diǎn)以及改進(jìn)方法。

隨著人工智能技術(shù)的興起，以自動駕駛車輛為研究對象的運(yùn)動路徑規(guī)劃問題越來越受到重視。而避障路徑規(guī)劃是自動駕駛車輛的關(guān)鍵部分，對自動駕駛車輛的研究具有重大意義。在自動駕駛汽車行駛過程中，準(zhǔn)確地避開障礙物是智能車輛的基本要求。一個好的避障路徑規(guī)劃算法可以安全實(shí)時地避開障礙物，且具有較高的乘坐舒適性，從而提高出行效率。

文章總結(jié)了目前文獻(xiàn)中經(jīng)常出現(xiàn)的各種適用于自動駕駛車輛路徑規(guī)劃的算法，分別從算法路徑尋優(yōu)能力、算法實(shí)時性及算法復(fù)雜度等方面分析比較了它們在理論上的優(yōu)勢和缺點(diǎn)，為今后的深入研究提供參考。

1. 避障技術(shù)分析

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

圖 1 智能車輛避障原理圖

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

2. 局部危險避障算法研究

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

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

自動駕駛車輛的全局路徑規(guī)劃為車輛規(guī)劃出了一條在已知環(huán)境地圖信息下的最優(yōu)路徑。車輛在前進(jìn)過程中，處在不可預(yù)測和高度動態(tài)的城市道路環(huán)境中，障礙物很可能出現(xiàn)在已經(jīng)規(guī)劃好的全局路徑上，也有可能在前進(jìn)的過程中一些障礙（行人或車輛等）動態(tài)地出現(xiàn)在路徑上。自動駕駛車輛必須對這些不可預(yù)測的事件以某種方式做出反應(yīng)，進(jìn)行局部避障，使之仍然能夠順利到達(dá)目的地、完成任務(wù)。

因此，局部避障必須速度快、實(shí)時性好和效率高，而可靠的避障算法正是保證自動駕駛車輛成功避障的主要方法。因此，在全局路徑規(guī)劃的基礎(chǔ)上，還需要進(jìn)行實(shí)時的局部危險避障。

目前，對于自動駕駛車輛動態(tài)目標(biāo)及城市道路區(qū)域的相關(guān)避障方法的研究，正是智能駕駛車輛研究的熱點(diǎn)和重要方向，也是一項(xiàng)實(shí)現(xiàn)車輛智能化的關(guān)鍵技術(shù)。

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

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

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

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

針對傳統(tǒng)人工勢場的改進(jìn)，大量學(xué)者展開研究，文獻(xiàn) [3] 利用高斯組合隸屬函數(shù)建立引力的目標(biāo)點(diǎn)函數(shù)，在引力點(diǎn)函數(shù)中考慮障礙物約束和車輛約束，并引入調(diào)節(jié)因子，建立了改進(jìn)的無人駕駛汽車人工勢場模型，消除了傳統(tǒng)人工勢場法容易陷入局部極小的問題。

文獻(xiàn) [4] 通過調(diào)整勢力場范圍、改進(jìn)斥力勢函數(shù)和動態(tài)調(diào)整斥力場系數(shù)，解決了陷入局部極小值的情況。文獻(xiàn) [5] 在人工勢場中加入速度元素，能夠規(guī)劃出同時避開靜態(tài)和動態(tài)障礙物且能到達(dá)目標(biāo)點(diǎn)的理想路徑。文獻(xiàn) [6] 解決了傳統(tǒng) APF 算法在無人車避障應(yīng)用中虛擬勢場作用域固定、避障角度過大的問題。

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

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

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

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

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

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

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

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

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

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

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

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

采樣點(diǎn)在整個可行域內(nèi)隨機(jī)采樣的搜索方式存

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

文獻(xiàn) [17] 利用 A* 算法進(jìn)行路徑規(guī)劃，根據(jù)規(guī)劃結(jié)果生成引導(dǎo)域來修改 RRT 隨機(jī)采樣過程中的采樣策略，將目標(biāo)偏向采樣策略和引導(dǎo)域偏向采樣策略相結(jié)合，使得隨機(jī)采樣點(diǎn)朝著目標(biāo)點(diǎn)區(qū)域方向靠近，并在最近鄰搜索過程中加入角度約束，因?yàn)橹悄苘囕v在行駛過程中有最大轉(zhuǎn)向角限制。

文獻(xiàn) [18] 提出動態(tài)步長并引入目標(biāo)引力思想，在傳統(tǒng) RRT 算法基礎(chǔ)上，添加動態(tài)步長特性，減少 RRT 的隨機(jī)性，讓路徑朝著目標(biāo)方向擴(kuò)展，改善了 RRT 的不確定性，提高了避障能力。

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

文獻(xiàn) [20] 采用簡單有效的 3 次 B 樣條曲線平滑算法，對路徑點(diǎn)進(jìn)行曲率連續(xù)的擬合以生成平滑且曲率連續(xù)的智能車可執(zhí)行的平滑路徑。

此外，還有 RRT GoalBias，RRT Goal Zoom，RRT*，RRT-Connect 等改進(jìn)方法。

2.4 多種算法結(jié)合

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

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

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

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

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

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

3. 結(jié)語

文章主要分析了在局部危險避障環(huán)境中的優(yōu)化算法，對傳統(tǒng)算法和智能算法及其改進(jìn)算法的優(yōu)缺點(diǎn)做出了分析以及多種算法的聯(lián)合求解。傳統(tǒng)算法和智能算法都可在一定程度上解決自動駕駛車輛避障的問題，每種算法都有其優(yōu)點(diǎn)和局限性。

人工勢場法算法簡明，實(shí)時性良好，規(guī)劃的路徑軌跡圓滑，適合自動駕駛智能車領(lǐng)域，但存在容易進(jìn)入局部最小點(diǎn)、目標(biāo)不可達(dá)及碰撞障礙物問題。

智能算法在傳統(tǒng)算法的基礎(chǔ)上，引入了更加智能化的計(jì)算，如遺傳算法可以同時處理群體中的多個個體，即對搜索空間中的多個解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身容易實(shí)現(xiàn)并行化。

因此在實(shí)際情況下，要進(jìn)行精確、安全和快速的避障僅僅依靠單一算法是有限的。車輛進(jìn)行局部避障時，可以依靠 2 種或多種算法進(jìn)行求解，得出避障路徑，將多種算法的優(yōu)缺點(diǎn)相互融合，產(chǎn)生更加完美的算法將是未來該領(lǐng)域研究的重點(diǎn)與難點(diǎn)。