導讀

環境模型（不同于環境理解），再加上路徑搜索就構成了路徑規劃。通常，環境模型有三大類，分別是柵格法、可視圖法、自由空間法。路徑搜索的算法比較多，如：Dijkstra、Floyd-Warshall、A+算法、層次法、動作行為法、勢場域法、柵格法、模糊邏輯法、拓撲法、懲罰函數法、遺傳算法、模擬退火法、蟻群法和神經網絡法等。

無人駕駛汽車的技術路線已經確定，那就是輪式機器人的技術路線。輪式機器人技術完全適用于無人駕駛汽車，這已經從2007年的DARPA大賽一直到最近谷歌、福特、百度等的無人駕駛試驗汽車，有了超過十年的驗證。目前所有無人駕駛汽車基礎算法的研究都源自機器人技術。

無人駕駛汽車需要解決三個問題：即環境感知及實時定位，計算分析以及路徑規劃，還有就是控制執行。今天我們來討論一下計算分析以及路徑規劃的問題。

首先我們來說明一下以下三個概念：路徑規劃、避障規劃、軌跡規劃。

路徑規劃通常指全局的路徑規劃，也可以叫全局導航規劃，從出發點到目標點之間的純幾何路徑規劃，無關時間序列，無關車輛動力學。

避障規劃又叫局部路徑規劃，又可叫動態路徑規劃，也可以叫即時導航規劃。主要是探測障礙物，并對障礙物的移動軌跡跟蹤（Moving Object Detection and Tracking，一般縮寫為MODAT），做出下一步可能位置的推算，最終繪制出一幅包含現存碰撞風險和潛在碰撞風險的障礙物地圖，這個潛在的風險提示是100毫秒級，未來需要進一步提高，這對傳感器、算法的效率和處理器的運算能力都是極大的挑戰，避障規劃不僅考慮空間還考慮時間序列，在復雜的市區運算量驚人，可能超過30TFLOPS，這是無人車難度最高的環節。未來還要加入V2X地圖，避障規劃會更復雜，加入V2X地圖，基本可確保無人車不會發生任何形式的主動碰撞。

軌跡規劃則源自機器人研究，通常是說機械臂的路徑規劃。 在無人車領域，軌跡規劃的定義感覺不統一。有人將避障規劃與軌跡規劃混淆了。軌跡規劃應該是在路徑規劃和避障規劃的基礎上，考慮時間序列和車輛動力學對車輛運行軌跡的規劃，主要是車縱向加速度和車橫向角速度的設定。將設定交給執行系統，轉向、油門、剎車。如果有主動懸掛，那么軌跡規劃可能還要考慮地形因素。

三大規劃是無人車最復雜的部分，算法多不勝數，讓人眼花繚亂，這也是百度、谷歌和蘋果等科技巨頭要切入無人車領域的主要原因，這些科技巨頭最擅長的就是算法的優化整合。當然傳統車廠如福特和豐田，擁有對車輛動力學的絕對優勢，在此領域實力并不比科技巨頭要差，尤其是豐田，從開源SLAM到KITTI，軟件實力絲毫不次于谷歌。

全局型路徑規劃不算復雜，前提是有拓撲級地圖，這對地圖廠家來說很容易的。對于非地圖廠家是有點麻煩的，不過只能算小麻煩。所以我們重點講避障規劃，避障規劃的前提是對周圍環境有深刻的理解，有一個非常完善實時的的環境理解。

有了環境模型（不同于環境理解），再加上路徑搜索就構成了路徑規劃。通常，環境模型有三大類，分別是柵格法、可視圖法、自由空間法。路徑搜索的算法就多了，Dijkstra、Floyd-Warshall、A+算法、層次法、動作行為法、勢場域法、柵格法、模糊邏輯法、拓撲法、懲罰函數法、遺傳算法、模擬退火法、蟻群法和神經網絡法等。需要指出的是，大多數算法都是誕生于六十年代。

這還僅僅是2D層面的，3D層面的將更加復雜。每一種算法下面還有再細分的算法，讓人看了頭暈目眩。因為很少有文獻說3D路徑算法，我們就多說幾句，3D路徑算法大體可以分為五類，取樣算法（Sampling）、節點算法（Node）、工程數學模型算法（Mathematics）、仿生學算法（Bioinspired)、混合算法（MultiFusion）。以取樣型算法為例，下面可以再分主動型與被動型。主動型下面還可以再細分。

1.取樣型3D路徑規劃

2.節點型算法下面再分三大類

3.環境建模方面，柵格法是公認最成熟的算法，柵格法應該也是安全系數最高的算法，也是最耗運算資源的算法。不過無人車要考慮安全，安全是第一位的，成本是第二位的，同時有英偉達和英特爾這樣的半導體巨人在不斷提高運算性能，運算資源不用過多考慮。

4.柵格法把工作空間分割成規則而均勻的含二值信息的柵格。在機器人移動的過程中，柵格的尺寸和位置不變。二值信息分別表示該柵格處是否有障礙，沒有障礙的柵格稱為自由柵格，否則為障礙柵格。柵格的尺寸通常和機器人的基本移動步長相適應，故機器人移動轉化成從一個自由柵格移動到下一個自由柵格，機器人移動的路長對應于機器人爬過的柵格數。柵格法直觀且建模相對較容易，因此得到了廣泛的應用。

5.另外兩種算法，可視圖法和自由空間法和柵格法相比的優點是比較靈活，對運算資源消耗少。缺點很明顯，障礙物多少與算法復雜程度成正比，算法太復雜時可靠性就降低，同時不太適合動態環境，要求運動速度變化盡量小。柵格法的缺點是如果分辨率高，對運算資源和內存需求較高。顯然，可視圖法和自由空間法適合機器人，柵格法更適合無人車，這在業內差不多已經是定論。這和傳感器也有部分關系，視覺系統難以適應太精細的格柵法，因為視覺系統的要做精細的定量邊界分割是不可能的，而激光雷達非常適合柵格法。

路徑搜索方面，典型的如Dijkstra （迪杰斯特拉）算法。

Dijkstra（迪杰斯特拉）算法是最短路算法的經典算法之一，由E.W.Dijkstra在1959年提出的。該算法適于計算道路權值均為非負的最短路徑問題，可以給出圖中某一節點到其他所有節點的最短路徑，以思路清晰，搜索準確見長。相對的，由于輸入為大型稀疏矩陣，又具有耗時長，占用空間大的缺點。

軌跡規劃則研究的很少，因為大部分科技公司都沒能力在車輛動力學領域一展拳腳。科技公司都將精力花在如何生成軌跡上，而對于生成的軌跡是否滿足運動學約束、側滑約束以及執行機構約束，即軌跡的可行性，研究相對較少。對于無人車這一受非完整性約束的系統，研究人員通常基于車體模型進行軌跡規劃。按照車體模型的精確程度，軌跡規劃方法可以進一步分為基于模型預測控制(Model predictive control, MPC) 以及基于幾何軌線的規劃方法。基于模型預測的無人車軌跡規劃方法首先由 Kelly A和NagyB提出。

對于移動機器人來說，軌跡生成問題主要研究如何生成一系列動作，使得機器人由初始狀態到達目標狀態。對于無人車來說，其初始狀態包括其二維坐標(x, y)、 航向角 ψ 以及曲率 κ。

實際情況遠比這復雜，還需要建立大量的數學方程。良好的規劃必須建立對周邊環境，尤其是動態環境的深刻理解。這就是下面要闡述的自動駕駛核心技術第三部分：MODAT。

感知、決策（路徑規劃）、定位都是基于傳感器或軟件系統的，這也是科技類廠家的強項，不過線控執行系統則是傳統汽車產業（不一定是整車廠）的絕對強項，這也是科技類廠家注定無法獨立造車的主要原因，無論是谷歌還是百度，都必須要與傳統汽車產業聯合，才能進軍無人車領域。有機會我們說說線控執行。