01 決策算法成為競爭焦點

從技術角度講，自動駕駛分為感知定位、規劃決策、執行控制三個部分。隨著 ADAS 系統的廣泛部署和以及長時間的技術開發，可以說感知技術已經不是主要瓶頸；控制則是主機廠和 Tier1 非常擅長的領域，自不必多說，顯然自動駕駛技術實現的真正門檻就落在了決策層上。

事實是，要區分一套系統是 ADAS 還是自動駕駛，主要是看該系統是否有決策部分。而無論谷歌還是特斯拉，它們的核心競爭力基本體現在決策算法方面。

傳統車企的研發是基于功能安全的設計方法學建立的，滲透到開發流程的每一個環節，在過去的一個世紀，將汽車的安全性提高到了極高的水準。如今，頂尖的公司已經可以確保汽車發動機能使用一百萬公里。盡管如此，面對洶涌而至的機器學習熱潮，主機廠突然發現自己嚴重缺乏技術儲備，這已經成為制約傳統車廠開發自動駕駛的最大短板。因此，很多 OEM 選擇或收購或合作的方式，試圖盡快補足自身的缺陷。

傳統車廠出身的 John Krafcik 顯然深知這一點。在他出任 Waymo CEO 之后，谷歌一改之前模棱兩可的商業策略，明確表示要向車廠提供解決方案，這其實是將自己定位成 Tier 1 的角色。在該解決方案中，外購的硬件無法成為谷歌的競爭壁壘，最有價值的，還是一整套經過驗證的軟件，尤其是其中的決策算法?？梢韵胂蟮氖牵雀鑼驑I界提供軟件授權，就像它之前在安卓系統上所做的一樣。

       02 如何解決智能汽車的路徑規劃問題

路徑規劃是智能汽車導航和控制的基礎，是從軌跡決策的角度考慮的，可分為局部路徑規劃和全局路徑規劃。

全局路徑規劃的任務是根據全局地圖數據庫信息規劃出自起始點至目標點的一條無碰撞、可通過的路徑。目前正在研究的有準結構化道路環境多種約束條件下的路徑規劃技術，自然地形環境下的路徑規劃技術，以及重規劃技術等。由于全局路徑規劃所生成的路徑只能是從起始點到目標點的粗略路徑，并沒有考慮路徑的方向、寬度、曲率、道路交叉以及路障等細節信息，加之智能車輛在行駛過程中受局部環境和自身狀態的不確定性的影響，會遇到各種不可測的情況。因此，在智能車輛的行駛過程中，必須以局部環境信息和自身狀態信息為基礎，規劃出一段無碰撞的理想局部路徑，這就是局部路徑規劃。通常路徑規劃的方法有 : 空間搜索法、層次法、動作行為法、勢場域法、柵格法、模糊邏輯法和神經網絡法等。

汽車自動駕駛任務可以分為三層，如下圖所示，每層執行不同任務，包括上層路徑規劃、中層行駛行為規劃和下層軌跡規劃。車輛路徑規劃問題中還包括路網模型、路徑規劃算法和交通信息的智能預測這幾個關鍵點，下文主要針對決策層中路徑規劃算法做簡單探討。

汽車自動駕駛任務執行示意圖

03車輛路徑規劃算法

根據車輛導航系統的研究歷程 , 車輛路徑規劃算法可分為靜態路徑規劃算法和動態路徑算法。靜態路徑規劃是以物理地理信息和交通規則等條件為約束來尋求最短路徑，靜態路徑規劃算法已日趨成熟 , 相對比較簡單 , 但對于實際的交通狀況來說 , 其應用意義不大。動態路徑規劃是在靜態路徑規劃的基礎上 , 結合實時的交通信息對預先規劃好的最優行車路線進行適時的調整直至到達目的地最終得到最優路徑。下面介紹幾種常見的車輛路徑規劃算法。

1. Dijkstra 算法

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

2. Lee 算法

Lee 算法最早用于印刷電路和集成電路的路徑追蹤，與 Dijkstra 算法相比更適合用于數據隨時變化的道路路徑規劃，而且其運行代價要小于 Dijkstra 算法。只要最佳路徑存在，該算法就能夠找到最佳優化路徑。Lee 算法的復雜度很難表示，而且對于多圖層的路徑規劃則需要很大的空間。

3. Floyd 算法

Floyd 算法是由 Floyd 于 1962 年提出的，是一種計算圖中任意兩點間的最短距離的算法。可以正確處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包，Floyd-Warshall 算法的時間復雜度為 O ( n 3 ) ，空間復雜度為 O ( n 2 ) ，n 為節點個數。與對每一節點作一次 Dijkstra 算法的時間復雜度相同，但是實際的運算效果比 Dijkstra 算法要好。

4. 啟發式搜索算法—— A* 算法

啟發式搜索有很多的算法，如 : 局部擇優搜索法、最好優先搜索法、A* 算法等。其中 A* 算法是由 Hart、Nilsson、Raphael 等人首先提出的，算法通過引入估價函數，加快了搜索速度，提高了局部擇優算法搜索的精度，從而得到廣泛的應用，是當前較為流行的最短路算法。A* 算法所占用的存儲空間少于 Dijkstra 算法。其時間復雜度為 O ( bd ) ，b 為節點的平均出度數，d 為從起點到終點的最短路的搜索深度。

5. 雙向搜索算法

雙向搜索算法由 Dantzig 提出的基本思想，Nicholson 正式提出算法。該算法在從起點開始尋找最短路徑的同時也從終點開始向前進行路徑搜索，最佳效果是二者在中間點匯合，這樣可縮短搜索時間。但是如果終止規則不合適，該算法極有可能使搜索時間增加 1 倍，即兩個方向都搜索到最后才終止。

6. 蟻群算法

蟻群算法是由意大利學者 M.Dorigo 等于 1991 年提出的，它是一種隨機搜索算法 , 是在對大自然中蟻群集體行為的研究基礎上總結歸納出的一種優化算法，具有較強的魯棒性，而且易于與其他方法相結合，蟻群算法的復雜度要優于 Dijkstra 算法。

此外 , 還有實時啟發式搜索算法、基于分層路網的搜索算法、神經網絡、遺傳算法及模糊理論等，由于實際需求不同對算法的要求和側重點也會有所不用，所以也出現了許多以上算法的各種改進算法。大多數算法應用于求解車輛路徑規劃問題時都會存在一定的缺陷，所以目前的研究側重于利用多種算法融合來構造混合算法。

主流決策算法的利弊相隨

從上部分的內容我們不難發現，決策算法面臨的最大挑戰，就是如何達到自動駕駛所需要的極高的安全性和可靠性。自動駕駛決策的結果會輸出到控制器，根據 ISO26262 已有的功能安全的規定，這會反過來要求決策系統也需要達到 ASIL-D 的標準。目前，ISO 組織專門針對自動駕駛的功能安全標準還在制定中，有可能會用一種新的標準進行考量，但功能安全的基本原則依然有效。

由于自動駕駛所要處理的場景極其復雜，必須考慮已知和未知的所有極端情況，以及適應各個國家和地區的交通狀況。目前在識別和決策算法部分也有多條技術路線，最主要的是深度學習（Deep Learning）加增強學習（Reinforcement Learning），也就是 AlphaGo 使用的方法。不過這些算法路線并非萬金油，各自都有自己明顯的優缺點。

△端到端的深度學習算法有隱患

深度學習適合大數據時代，只要大量訓練就比較容易調校出可用的算法，因此專門用來處理復雜場景。不過深度學習受到質疑的點在于，它的算法是端到端（輸入數據，輸出結果）的決策系統，計算過程不能被解釋，即沒有透明度，無法 debug。

△基于規則的專家系統不靈活

專家系統（Expert System）是基于獨立知識庫（如地圖、交通規則），讓條件 IF（輸入）產生出相應的動作或結論 THEN（輸出）的系統；還可以用 AND、OR、NOT 運算來復合輸入、輸出。但專家系統的缺點在于：一、采訪 " 專家 " 來建模所需時間過長，成本過高；第二，知識庫可能有錯誤，多條規則可能出現矛盾，從而造就脆弱系統。所以，這種方法不能單獨用于構建自動駕駛的決策算法。

因此，我們需要在自動駕駛領域引入新的決策機制。自動駕駛決策技術路線的一個重大趨勢，就是從相關推理到因果推理。

理性決策是必然趨勢

上世紀 80 年代初，Judea Pearl 為代表的學術界出現了一種新的思路：從基于規則的系統轉變為貝葉斯網絡。貝葉斯網絡是一個概率推理系統，貝葉斯網絡在數據處理方面，針對事件發生的概率以及事件可信度分析上具有良好的分類效果。它具有兩個決定性的優勢：模塊化和透明性。

圖靈獎得主、貝葉斯之父朱迪亞 · 珀爾（Judea Pearl）

模塊化的優勢非常重要。我們可以把深度學習的系統作為一個子模塊融入到其中，專家系統可以是另一個子模塊，也融入其中，這意味著我們有了多重的冗余路徑選擇，這種冗余構成了貝葉斯網絡的子節點，將有效強化輸出結果的可靠性，避免一些低級錯誤的發生。

透明性是貝葉斯網絡的另一個主要優勢。對于自動駕駛而言，這尤為關鍵，因為你可以對整個決策的過程進行分析，了解出錯的哪一個部分?？梢哉f貝葉斯網絡是理性決策的極佳實現，適合用于設計整個決策的頂層框架。

因果推理的另一個典型范例就是基于增強學習的決策框架，它把一個決策問題看作是一個決策系統跟它所處環境的一個博弈，這個系統需要連續做決策，就像開車一樣。優化的是長期總的收益，而不是眼前收益。這有點像巴菲特的價值投資，優化的目標不是明天的收益，而是明年或者十年以后的長期總收益。

谷歌把這樣的框架用在下圍棋上，取得了革命性的成功。自動駕駛的場景也非常適合應用這樣的決策系統。比如說要構建價值網絡，評估當前的駕駛環境風險，評估的是從現在時間到未來時間的整體風險；然后利用策略網絡輸出本車的控制決策，選擇最優的駕駛路徑和動力學輸出。

同時，我們還可以構建一個基于模擬路況的仿真環境，通過增強學習去做虛擬運行，獲得最優的決策模型，并且還將產生大量的模擬數據，這對決策算法的成熟至關重要?？梢哉f，向因果推理型決策模型轉化是自動駕駛技術邁向成熟的重大標志。

04 小結

在訓練和測試自動駕駛汽車決策能力的過程中，其實收集到的絕大部分數據都是正常路況下的行車數據，極端情況極其罕見。深度學習加增強學習的算法只能無限趨近于處理所有場景，貝葉斯網絡的因果推理邏輯可以在一定程度上處理未知的極端情況。決策層的不同技術路線也各有優缺點，可能包括深度學習、增強學習、專家系統、貝葉斯網絡在內的多種方法融合，將是下一步的主流方案。