自動駕駛能否識別障礙物的能力與環境感知同等重要，如何安全有效的規划行駛路線，是自動駕駛汽車需解決的最大的難題之一。事實上，路徑規劃技術，現階段是一個非常活躍的研究領域。路徑規劃之所以如此複雜，是因為其涵蓋了自動駕駛的所有技術領域，從最基礎的制動器，到感知周圍環境的傳感器，再到定位及預測模型等等。準確的路徑規劃，要求汽車要理解我們所處的位置以及周邊的物體（其他車輛、行人、動物等）會在接下來的幾秒鐘內採取什麼樣的行為。
首先來說一下三個名詞：路徑規劃、避障規劃、軌跡規劃
路徑規劃通常指全局的路徑規劃，也可以叫全局導航規劃，從出發點到目標點之間的純幾何路徑規劃，無關時間序列，無關車輛動力學。
避障規劃又叫局部路徑規劃，又可叫動態路徑規劃，也可以叫即時導航規劃。 主要是探測障礙物，並對障礙物的移動軌跡跟蹤（ Moving Object Detection and Tracking ，一般縮寫為MODAT）做出下一步可能位置的推算，最終繪製出一幅包含現存碰撞風險和潛在碰撞風險的障礙物地圖，這個潛在的風險提示是100毫秒級，未來需要進一步提高，這對傳感器、算法的效率和處理器的運算能力都是極大的挑戰，避障規劃不僅考慮空間還考慮時間序列，在複雜的市區運算量驚人，可能超過30TFLOPS，這是無人車難度最高的環節。未來還要加入V2X地圖，避障規劃會更複雜，加入V2X地圖，基本可確保無人車不會發生任何形式的主動碰撞。
軌跡規劃則源自機器人研究，通常是說機械臂的路徑規劃。 在無人車領域，軌跡規劃的定義感覺不統一。有人將避障規劃與軌跡規劃混淆了。軌跡規劃應該是在路徑規劃和避障規劃的基礎上，考慮時間序列和車輛動力學對車輛運行軌跡的規劃，主要是車縱向加速度和車橫向角速度的設定。將設定交給執行系統，轉向、油門、剎車。如果有主動懸掛，那麼軌跡規劃可能還要考慮地形因素。
三大規劃是無人車最複雜的部分，算法多不勝數，讓人眼花繚亂，這也是百度、谷歌和蘋果科技巨頭要切入無人車領域的主要原因，這些科技巨頭最擅長的就是算法的優化整合。當然傳統車廠如福特和豐田，擁有對車輛動力學的絕對優勢，在此領域實力並不比科技巨頭要差，尤其是豐田，從開源 SLAM到KITTI，軟體實力絲毫不次於谷歌。
對於全局型路徑規劃不算複雜，前提是有拓撲級地圖，這對地圖廠家來說很容易的。對於非地圖廠家是有點麻煩的，不過只能算小麻煩。
今天我們重點了解一下避障規劃，避障規劃的前提是對周圍環境有深刻的理解，有一個非常完善實時的環境理解。
在此之前不得不先要理解無人駕駛避障的含義，很明顯我們根據無人駕駛避障的過程，可以將無人駕駛避障分成三個方面：
1.運動障礙物檢測：對運動過程中環境中的運動障礙物進行檢測,主要由車載環境感知系統完成。
2.運動障礙物碰撞軌跡預測：對運動過程中可能遇到的障礙物進行可能性評級與預測,判斷與無人駕駛車輛的碰撞關係。（當你檢測到障礙物後，你就得讓機器判斷是否會與汽車相撞）
3.運動障礙物避障：通過智能決策和路徑規劃,使無人駕駛車輛安全避障,由車輛路徑決策系統執行。（判斷了可能會與汽車發生碰撞的障礙物後，你就得去讓機器做出決策來避障了）
運動障礙物檢測方法
運動障礙物檢測根據他們的sensor主要分成兩類：
一種是基於雷射雷達和毫米波雷達的
一種是基於立體視覺的
運動障礙物碰撞軌跡預測
這一部分與障礙物的檢測識別分不開的。無人車的感知系統需要實時識別和追蹤多個運動目標（Multi-ObjectTracking，MOT），例如車輛和行人。
物體識別是計算機視覺的核心問題之一，最近幾年由於深度學習的革命性發展，計算機視覺領域大量使用CNN，物體識別的準確率和速度得到了很大提升，但總的來說物體識別算法的輸出一般是有噪音的：物體的識別有可能不穩定，物體可能被遮擋，可能有短暫誤識別等。自然地，MOT問題中流行的Tracking-by-detection方法就要解決這樣一個難點：如何基於有噪音的識別結果獲得魯棒的物體運動軌跡。
運動障礙物的避障本質上它是一個路徑規劃的過程：在路段上有未知障礙物的情況下,按照一定的評價標準,尋找一條從起始狀態到目標狀態的無碰撞路徑。
預測
預測模塊的作用是對感知所探測到的物體進行行為預測，並且將預測的結果具體化為時間空間維度的軌跡傳遞給下遊模塊：行為決策模塊。然後行為決策模塊結合路由尋徑模塊從而進行行為決策。
這些選擇就是結合高精地圖的全局規劃，然後再通過汽車周邊傳感器感知的信息進行局部規劃，從而判斷汽車是否右轉、直行or並道。
路徑規劃
先簡單理解一下自動駕駛汽車的功能層，因為路徑規劃需要自動駕駛汽車不同功能層之間的合作、協調。
動作控制層：負責控制汽車，使其儘可能的按照「設定的」軌跡形式。該層需要最快的反應速度；
傳感器融合層：負責合併個傳感器的輸出（如雷達和雷射雷達）
定位層：負責儘可能準確的在地圖上定位車輛的位置，並計算其他物體相對於車輛的位置
預測層：負責識別傳感器檢測到的物體的性質(又名感知)，並根據汽車當前的軌跡、其他車輛的軌跡和場景中的各種元素(如交通燈)預測場景中近未來的變化。這個層的一個重要任務是預測衝突。
行為層：該層的主要作用是協調。根據底層的輸入信息來決定如何調整行車軌跡
軌跡層：負責計算既定條件（速度、距離、車道、jerk等等）下的行車軌跡
對於不同的環境，我們創造了環境模型，再加上路徑搜索就構成了路徑規劃。通常，環境模型有三大類，分別是柵格法、可視圖法、自由空間法。路徑搜索算法就多了，Dijkstra、Floyd-Warshall、A+算法、層次法、動作行為法、勢場域法、柵格法、模糊邏輯法、拓撲法、懲罰函數法、遺傳算法、模擬退火法、蟻群法和神經網絡法等。大多數算法都是誕生於六十年代。
對於環境建模來說，柵格法是公認最成熟的算法，柵格法應該也是安全係數最高的算法，也是最耗運算資源的算法。不過無人車要考慮安全，安全是第一位，成本是第二位，同時有英偉達和英特爾這樣的半導體巨人在不斷提高運算性能，運算資源不用過多考慮。
柵格法與雷射雷達很搭
可視圖法和自由空間法和柵格法相比的優點是比較靈活，對運算資源消耗少。缺點很明顯，障礙物多少與算法複雜程度成正比，算法太複雜時可靠性就降低，同時不太適合動態環境，要求運動速度變化儘量小。柵格法的缺點是如果解析度高，對運算資源和內存需求較高。 顯然，可視圖法和自由空間發適合機器人，柵格法更適合無人車，這在業內差不多已經是定論。這和傳感器也有部分關係，視覺系統難以適應太精細的格柵法，因為視覺系統的要做精細的定量邊界分割是不可能的，而雷射雷達非常適合柵格法。
Dijkstra（迪傑斯特拉）——最短路算法的經典算法
路徑算法的種類如此之多，可以看出他一直是一個熱門話題，也採用了許多技術。這些路徑規劃方法大致可以分為三種：
1.基於圖搜索的規劃器
2.基於採樣的方法
3.內插曲線規劃器
在基於圖形搜索的規劃器的範圍內，Dijkstra算法是一種基於圖形搜索的算法，給定一個起點，使用Dijkstra算法可以得到起點到其它所有節點的最短路徑。Dijkstra算法要求圖(Graph)中所有邊的權重都為非負值，只有保證了這個條件才能該算法的適用性和正確性。
在《自動駕駛路徑規劃-Graph Based的BFS最短路徑規劃》中介紹，將地圖抽象為Graph的數據結構，然後利用Graph廣度優先遍歷算法(Breadth-First Search, BFS)解決無權重的High-Level的地圖級別的規劃。但是實際應用場景中，地圖中各個路徑所代表的Graph的邊的權重都是不同的，比如距離長的Edge權重就應該比較低；交通擁堵的Edge權重就應該低等等。對於有權重的Graph如何進行最短路徑規劃呢，Dijkstra算法可以解決這個問題。
它的基本思路是：
考慮一個圖，該圖由兩部分組成：節點和連接結點的邊。其中每條邊還被指定了一個數值，表示從該邊的一個端點移動到另一端點的代價，通常指距離。
讓我們把圖中的開始節點稱為初始節點。讓節點Y的距離是從初始節點到Y的距離。Dijkstra的算法將分配一些初始距離值，並嘗試逐步改進。
1.為每個節點分配一個暫時的距離值：為我們的初始節點設置為零，對所有其他節點設置為無窮大。
2.將初始節點設置為當前節點。標記所有其他節點為未訪問節點，創建一組稱為未訪問集的未訪問節點。
3.對於當前節點，考慮其所有鄰居並計算其臨時距離。將新計算的臨時距離與當前分配的值進行比較，並分配較小的值。例如，如果當前節點A的距離為6，並且與鄰居B連接的邊的長度為2，則到B（途徑A）的距離將為 6 + 2 = 8，如果B先前標記的距離大於8，然後將其更改為8。否則，保持當前值。
4.當我們完成考慮當前節點的所有鄰居時，將當前節點標記為已訪問，並將其從未訪問集中移除，以後將不會再次檢查被訪問的節點。
5.如果目標節點已被標記為訪問（在兩個特定節點之間規劃路由時），或者未訪問集合中的節點之間的最小暫定距離都是無窮遠（當完整遍歷時；當初始節點和剩餘的未訪問節點之間沒有連接時），算法結束。
6.否則，選擇標有最小暫定距離的未訪問節點，將其設置為新的「當前節點」，然後返回到步驟3。
作為運動規劃領域最著名的算法之一，Dijkstra算法可以解決帶權重有向圖的最短路徑規劃問題，在實際的路徑規劃中也有大規模的實際應用。但是Dijkstra算法的搜索沒有方向性，會有大量冗餘的搜索操作。我們可以給Dijkstra加上一些啟發性的信息，引導搜索算法快速的搜索到目標，這就是A*算法。由於加入引導信息，A*算法在大多數情況下會比Dijkstra算法要快。
對於移動機器人來說，軌跡生成問題主要研究如何生成一系列動作，使得機器人由初始狀態到達目標狀態。對於無人車來說，其初始狀態包括其二維坐標 (x, y)、 航向角 ψ 以及曲率 κ。
實際情況遠比這複雜，還需要建立大量的數學方程。良好的規劃必須建立對周邊環境，尤其是動態環境的深刻理解。
參考資料：
1.智車科技：自動駕駛之——避障方法研究
2.智車科技：自動駕駛核心技術之路徑規劃
3.算法集錦之路徑規划算法：Dijkstra算法
4.自動駕駛基礎（十八)--路徑規劃
5.自動駕駛高速路上的路徑規划算法