如果說過去是算法根據(jù)芯片進(jìn)行優(yōu)化設(shè)計(jì)的時(shí)代，那么英特爾對 Mobileye 的收購，預(yù)示著一個(gè)新時(shí)代的到來：算法和芯片協(xié)同進(jìn)化的時(shí)代。今天我們著重了解下智能駕駛發(fā)展驅(qū)動下，「算法」這一細(xì)分技術(shù)領(lǐng)域都有哪些創(chuàng)新和進(jìn)步。

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

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

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

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

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

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

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

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

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

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

1. Dijkstra 算法

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

2. Lee 算法

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

3. Floyd 算法

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

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

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

5. 雙向搜索算法

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

6. 蟻群算法

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

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

主流決策算法的利弊相隨

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

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

△端到端的深度學(xué)習(xí)算法有隱患

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

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

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

因此，我們需要在自動駕駛領(lǐng)域引入新的決策機(jī)制。自動駕駛決策技術(shù)路線的一個(gè)重大趨勢，就是從相關(guān)推理到因果推理。

理性決策是必然趨勢

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

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

透明性是貝葉斯網(wǎng)絡(luò)的另一個(gè)主要優(yōu)勢。對于自動駕駛而言，這尤為關(guān)鍵，因?yàn)槟憧梢詫φ麄€(gè)決策的過程進(jìn)行分析，了解出錯(cuò)的哪一個(gè)部分?？梢哉f貝葉斯網(wǎng)絡(luò)是理性決策的極佳實(shí)現(xiàn)，適合用于設(shè)計(jì)整個(gè)決策的頂層框架。

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

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

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

小結(jié)

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