01 決策算法成為競爭焦點

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

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

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

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

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

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

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

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

汽車自動駕駛任務執(zhí)行示意圖

03車輛路徑規(guī)劃算法

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

1. Dijkstra 算法

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

2. Lee 算法

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

3. Floyd 算法

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

4. 啟發(fā)式搜索算法—— A* 算法

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

5. 雙向搜索算法

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

6. 蟻群算法

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

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

主流決策算法的利弊相隨

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

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

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

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

△基于規(guī)則的專家系統(tǒng)不靈活

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

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

理性決策是必然趨勢

上世紀 80 年代初，Judea Pearl 為代表的學術界出現(xiàn)了一種新的思路：從基于規(guī)則的系統(tǒng)轉(zhuǎn)變?yōu)樨惾~斯網(wǎng)絡。貝葉斯網(wǎng)絡是一個概率推理系統(tǒng)，貝葉斯網(wǎng)絡在數(shù)據(jù)處理方面，針對事件發(fā)生的概率以及事件可信度分析上具有良好的分類效果。它具有兩個決定性的優(yōu)勢：模塊化和透明性。

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

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

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

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

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

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

04 小結

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