一篇讀懂自動駕駛汽車決策層演算法的新思路

如果說過去是演算法根據晶元進行優化設計的時代，那麼英特爾對Mobileye的收購，預示著一個新時代的到來：演算法和晶元協同進化的時代。今天我們著重了解下智能駕駛發展驅動下，「演算法」這一細分技術領域都有哪些創新和進步。

決策演算法成為競爭焦點

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

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

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

傳統車廠出身的John Krafcik顯然深知這一點。在他出任Waymo CEO之後，谷歌一改之前模稜兩可的商業策略，明確表示要向車廠提供解決方案，這其實是將自己定位成Tier 1的角色。在該解決方案中，外購的硬體無法成為谷歌的競爭壁壘，最有價值的，還是一整套經過驗證的軟體，尤其是其中的決策演算法。可以想象的是，谷歌將會向業界提供軟體授權，就像它之前在安卓系統上所做的一樣。

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

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

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

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

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

車輛路徑規劃演算法

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

1. Dijkstra演算法

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

2. Lee演算法

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

3. Floyd演算法

Floyd演算法是由Floyd於1962年提出的，是一種計算圖中任意兩點間的最短距離的演算法。可以正確處理有向圖或負權的最短路徑問題，同時也被用於計算有向圖的傳遞閉包，Floyd-Warshall演算法的時間複雜度為O(n³)，空間複雜度為O(n²)，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）

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

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

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

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

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

小結

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