傳統(tǒng)拓撲地圖

我們先了解下傳統(tǒng)拓撲地圖，這是從地圖app里截出來的圖，從這張圖我們可以得到很多信息：

◆ 拓撲信息：我們可以從地圖里辨認出北清路的主干道，以及了解到北清路能延伸向哪些其他道路等，這些都是人們可辨認的拓撲信息。

◆ 各類 POI（信息點）：我們能看到許多 POI 信息，包括中關村壹號-A1座，拉卡拉大廈等。

◆ 地圖的用戶是人。

◆ 米級精度：地圖精度是米級別的，對于人類使用這已經(jīng)足夠了，因為人會自覺判別周圍的環(huán)境，做出自己的變化。

但是這些信息對于自動駕駛的車輛來說，是不是必要的、準確的或者足夠的呢？

一個自動駕駛典型場景

上圖展示了一個典型的駕駛場景——假設我們正在駕駛的車輛是后面的白車，可以看到我們前方有輛自行車，那么對于白車而言，可以有兩個決策：跟車或者變道。

對于自動駕駛車輛來說, 它作出變道決策需要知道很多具體的信息：

◆ 在哪條車道上以及當前車道的具體位置。

◆ 是否有隔壁車道，如果沒有車道你是變不過去的。

◆ 是否允許變道，車道的類型，車道線是虛線還是實線，變道距離是否足夠長，變道后是否能夠達到終點。

自動駕駛車輛不能像人一樣做出各種復雜的動作，這時就需要有一些先驗的約束條件，那么這些先驗信息都可以從地圖中來。

HD Road Graph如何應用于自動駕駛

HD Road Graph （高精道路圖）也是高精地圖的一部分，又叫做拓撲地圖。HD Road Graph 以厘米級精度來描述道路細節(jié)，主要包含：車道類型、車道連通性、交通標注/交通燈、人行橫道、道路幾何特征、其他語義信息。

大家可以看一下上圖左側(cè)，每一條路都已精細到車道，包括直行或左轉(zhuǎn)的車道，當然也包括周邊的一些幾何信息?？傮w上你會發(fā)現(xiàn)高精地圖上的信息要比傳統(tǒng)地圖大很多。

感知系統(tǒng)+高精地圖

高精地圖在自動駕駛里有很多應用，首先是與感知系統(tǒng)相結(jié)合。例如，高精地圖里會描述紅綠燈所在位置，當自動駕駛車輛到達路口后，可以根據(jù)當前的位置，更加準確地識別前方的紅綠燈。

上圖左邊是一個普通的道路場景，而右邊則是安裝有幾十盞紅綠燈的特殊場景（其實現(xiàn)實情況基本不存在），在這種極端情況下，人類都很難分辨在哪個路口對應哪盞紅綠燈。但如果前期在離線地圖上就能把這個對應信息驗證準確，無疑將對自動駕駛的安全性、可靠性起到很大幫助。

決策規(guī)劃+高精地圖

我們再來看下高精地圖在決策規(guī)劃方面的應用。前面我提到了一個典型駕駛場景，以及在此情況下，自動駕駛車輛的行駛需要得到一個全局的路徑信息以及變道所需要的信息。

上圖右側(cè)的地圖強調(diào)了綠化帶，這其實為自動駕駛提供了語義信息。而地圖里包含的語義信息將幫助自動駕駛做出更好的行駛決策。

還是以綠化帶為例，當自動駕駛車輛能夠提前知道旁邊是綠化帶，它便可以做一些先驗的決策，例如可以提前判斷在行駛中是否有行人、車輛直接從對向車道穿過來。這不僅提升了決策的準確性，也使得系統(tǒng)性能得到提升，因為自動駕駛車輛此時不需要過多關心對面車道的物體，計算量也因此減少。通過上面的例子，你會發(fā)現(xiàn)先驗信息對自動駕駛決策來說必不可少，并且非常關鍵。

高精地圖生成與發(fā)布

當前高精地圖生成發(fā)布用到的流程（Pipeline）一般分為以下幾個環(huán)節(jié)：

◆ 數(shù)據(jù)收集，地圖信息的采集。

◆ 數(shù)據(jù)清洗/聚合。

◆ 自動化識別，把地圖里的必要信息處理出來，包括車道線、紅綠燈、十字路口等等各種信息。

◆ 人工檢查/標注，現(xiàn)有的算法還做不到100%的自動抽取，所以仍會加入人工檢查和標注的環(huán)節(jié)。

◆ 后處理和驗證，整個數(shù)據(jù)出來之后，還需要進行后處理和驗證。處理的最終目的是保證提供的地圖信息是準確的，假設一個紅綠燈位置標錯了或者自動識別錯了，那可能會導致路測過程中會出現(xiàn)安全隱患，所以驗證環(huán)節(jié)是很重要的部分。

◆ Release（發(fā)布），驗證通過后，將會進行數(shù)據(jù)的發(fā)布（Data Release），所有數(shù)據(jù)會納入統(tǒng)一的管理中，每一版本Release的地圖的質(zhì)量已得到嚴格驗證。

這是一個常規(guī)的發(fā)布流程?，F(xiàn)實中整個路網(wǎng)結(jié)構(gòu)是不斷往外擴張的，且周圍環(huán)境會有變化，所以也會有增量的更新。

成本與挑戰(zhàn)

前面簡單介紹了整個HD Road Graph的生成發(fā)布流程，我們來看下HD Road Graph可能會遇到的問題與挑戰(zhàn)。

成本

◆ 厘米級別的精度：需要各類傳感器（LiDAR、Cameras、GNSS/IMU），上圖右邊是蘋果的地圖車，大家可以看到上面裝了很多傳感器，顯然制造這樣一輛高精地圖車輛的成本不低。

◆ 數(shù)據(jù)量：海量存儲資源和計算資源。

◆ 覆蓋范圍：當?shù)貓D從局部區(qū)域逐步向外擴張，例如從中關村壹號附近地區(qū)，擴張到海淀區(qū)，再到北京市，甚至是半個中國，這其中涉及的硬件成本和人力成本等，都會相應增加。

復雜性挑戰(zhàn)

第二個是高精地圖的復雜性帶來的挑戰(zhàn)。復雜性體現(xiàn)在地圖Data Model（數(shù)據(jù)模型）需要包含三部分信息：

◆ 語義信息，從上圖里的標志牌示例圖可以看出，目前道路存在各式各樣的交通標記。因此，高精地圖需提高語義信息的準確性，并且盡可能提高覆蓋度。

◆ 空間信息，上圖中的立交橋是以復雜聞名的西直門立交橋——有人說，即使借助導航軟件，你都未必能夠從縱橫交錯的道路中準確找到下一條你要行駛的車道。因此挑戰(zhàn)就是如何能夠把整個空間信息描述好，集成到地圖中去。

◆ 時間信息，北京有一些潮汐街道，早高峰和晚高峰走的方向是不一樣的；或者某些公交車道在早高峰的時候只允許公交車行駛，其他車輛禁止使用。這類時間信息也需要包含進地圖里。

當三類信息準確地整合進高精地圖時，決策規(guī)劃模塊和感知模塊才能有效地運作。

拓展性挑戰(zhàn)

◆ 自動駕駛車輛每行駛一公里會產(chǎn)生GB級別的原始數(shù)據(jù)，處理這些數(shù)據(jù)會使得功能架構(gòu)面臨很大的挑戰(zhàn)。

◆ 地圖更新方面，從“天”級別到“小時”級別再到“分鐘”級別的更新，對應的整體功能架構(gòu)是不一樣的。

實時性挑戰(zhàn)

交通管制、環(huán)境變化等怎么反饋到HD Road Graph上？假設今天某條路修路，對于人類駕駛員而言，他可以選擇繞過這條路。對于自動駕駛而言，這樣的信息如何反饋到行駛過程呢？是靠人去反饋，還是系統(tǒng)自動去識別？得到反饋之后，怎么實時更新到地圖數(shù)據(jù)里？

所以說，自動駕駛需要打通offline（線下）到online（線上）的環(huán)節(jié)，及時更新到我們正在運行的自動駕駛車輛里去。

什么是3D柵格地圖

前面介紹了拓撲地圖的部分，接下來介紹3D柵格地圖（3D Grid Map）。3D柵格地圖的定義認為一個真實的三維世界可以用一個概率模型來表示。

比如像今天這個會場，我們可以將它離散化成一個個立體方格，每個方格里會存儲一個概率，這個概率即方格空間不為空的概率。

上圖是一個 3D 柵格地圖，從數(shù)學的角度講，它并不是一個連續(xù)的描述，而是離散化后的地圖，只會保留一些概率值和屬性。這里展示的是一張厘米級精度的柵格地圖，我們可以很清楚看到周圍的環(huán)境，包括樹、建筑等等。

SLAM與自動駕駛

那么，如何制作高精地圖呢？傳統(tǒng)上有一種地圖制作方法叫SLAM（即時定位與地圖構(gòu)建）。它指運動物體根據(jù)傳感器的信息，一邊計算自身位置，一邊構(gòu)建環(huán)境地圖的過程。目前，SLAM的應用領域主要有機器人、虛擬現(xiàn)實和增強現(xiàn)實。其用途包括傳感器自身的定位，以及后續(xù)的路徑規(guī)劃、場景理解。

傳統(tǒng)SLAM與自動駕駛SLAM的區(qū)別

傳統(tǒng) SLAM：

• 2D；

• 視覺傳感器，單靠攝像頭，在某個空間轉(zhuǎn)來轉(zhuǎn)去，最終通過算法來建模；

• 沒有 GPS 信息，很多室內(nèi)場景是收集不到 GPS 信息的；

• 生成地圖和定位同時進行。

自動駕駛SLAM：

• 3D，描繪的是一個三維環(huán)境；

• 激光傳感器，需要達到比較高的精度；

• GPS 信息，室外場景的優(yōu)勢就是可以接收 GPS 信息；

• 離線處理，數(shù)據(jù)不需要在線處理，前面介紹過，如果選擇在線，某些場景算法無法得到良好的處理，所以需要抽取一些信息來做離線的驗證。

3D柵格地圖的挑戰(zhàn)

相比于傳統(tǒng) SLAM，我們來看下有哪些問題是3D柵格地圖需要解決的：

全局 GPS 信息并不總是好的。上圖左下角是3D柵格地圖的底圖，里面包含一條當時車輛的行駛軌跡。你會發(fā)現(xiàn)依據(jù) GPS 的這條行駛軌跡，這輛車已經(jīng)開到馬路牙子（路肩）上了，但實際情況并非如此。因此，當拿到這樣一份地圖數(shù)據(jù)時，我們需要從算法層做出優(yōu)化，并且做好細節(jié)。

不同時間段的數(shù)據(jù)如何align（校準）。一般來說，地圖的采集不可能一次完成，因此，從算法層面上看，3D柵格地圖需要處理把不同時間段的數(shù)據(jù)校準到一起的問題。

去除非靜態(tài)的物體。我們所建立的是一個概率的模型，3D柵格地圖只需要保留一些靜態(tài)的物體以輔助感知系統(tǒng)，許多非靜態(tài)的物體都需要從地圖中去除。

應對挑戰(zhàn)：位姿圖 Pose Graph

位姿圖其實是一個優(yōu)化問題

整體上我們認為位姿圖（Pose Graph）是一個優(yōu)化問題。假設將路線采集以時間去劃分——比如每隔4分鐘采一個點，最后能得到不同的位置的環(huán)境。舉個例子：在一個大廳里，我現(xiàn)在站在某點，一分鐘后我可能站在另一處，再繞一圈的話后站在門口，通過把整個GPS獲得的位置信息離散化之后，將我在每一點所看到的周圍的環(huán)境直接拼起來，就可能得到一個三維的地圖，因為每個點看到的角度都是不一樣的。

但因為原始位置可能跟真實位置有偏差，直接拼起來常常導致很多問題。所以我們把這些點離散化之后，希望能夠把所有點都對齊調(diào)整到準確的位置。那怎么確保最終的結(jié)果是正確的？

對整個圖來說, 除了頂點之外，還有邊。我們希望通過邊的約束將點調(diào)好，邊的約束你可以認為是個相對約束，假設我知道下個點的準確位置，那么便可倒推另一個點的準確位置。也就是說，在有準確的相對位置的基礎上，輔以一些比較少的絕對位置，就可以得到一個全局的準確位置。

總的來說，位姿圖的優(yōu)化目標是把整個圖離散化到一個個點之后，通過建立一些邊的約束，最終通過優(yōu)化某些點的位置來滿足邊的約束。位姿圖也就成為了一個優(yōu)化問題。

位姿圖的挑戰(zhàn)

位姿圖整體的數(shù)學模型看似簡單，但是存在許多細節(jié)問題需要做優(yōu)化：

◆ 如何選擇頂點。比如需要考慮是不是毫秒的點都要加進去，GPS 信號不好時的點要不要加進去。

◆ 如何保證邊的準確性。一個頂點到另一個頂點的相對位置，需要通過什么方式去建立。

◆ 如何求解非線性優(yōu)化。圖建好之后如何去做非線性的優(yōu)化。

◆ 如何評估優(yōu)化效果。圖是否和真實的環(huán)境一致，以及如何評估結(jié)果滿足要求。

◆ 效率和資源。對于工程來講，數(shù)據(jù)量這么大，你需要考慮怎么設計工程算法以保證效率和資源。比如說，考慮是不是需要在算法基礎上進行定制優(yōu)化，如何用 GPU 或者分布式的計算方式。

我想通過上圖右邊的例子解釋位姿圖——左側(cè)原始的圖展示的是有一個物體來回在球面上運動旋轉(zhuǎn)，通過在邊與邊之間建立相對約束，進行優(yōu)化后，你會發(fā)現(xiàn)整個環(huán)境的重建成了右側(cè)一個比較理想、完整的球體，概括來說，我們的工作就是需要把左側(cè)的圖來變成右側(cè)的圖。

迭代最近點算法：保證邊的約束

我們前面提到位姿圖需要保證邊的約束，為了計算出這個約束，業(yè)界用的比較多的傳統(tǒng)經(jīng)典算法叫做 ICP（Iterative Closest Point algorithm）——迭代最近點算法。

舉個例子：左邊是只紅色的兔子，右邊是只藍色的兔子，現(xiàn)實中這兩只兔子的位置是一樣的，但在圖片里兩只兔子位置不一樣，說明位置存在偏差。也就是說，輸入是兩組點云 A 和 B，輸出是兩組點云之間在空間上的旋轉(zhuǎn)和平移。

具體算法的思路大致是：找到點云集合 A 中的每個點在集合 B 中的對應點，通過求解最佳的剛體變換，不斷的迭代優(yōu)化，最終得到一個收斂解。

應對挑戰(zhàn)：去除非靜態(tài)障礙物體

◆ 通過概率模型去除。

◆ 點云處理，單純的概率模型是不夠的，例如有時候小區(qū)路邊經(jīng)常停著車，而某些時候車是被開走的。數(shù)據(jù)采集時，恰好車停在路邊，后續(xù)那就需要依賴離線點云處理。

◆ 機器學習，即利用機器學習算法去把非靜態(tài)的物體從地圖里面摳出來。

上圖是一個簡單的去除非靜態(tài)障礙物前后對比圖，處理之前，你會發(fā)現(xiàn)右側(cè)道路有一些車的輪廓，當從空間上去除之后，地圖變得清晰許多。

自動駕駛定位的特點

對于定位系統(tǒng)和傳統(tǒng)定位來說，自動駕駛車輛的位置和姿態(tài)有以下特點：

◆ 厘米級別的精度，需要精確到車在車道線的具體位置，例如距離左右邊線幾公分。

◆ 高頻低延遲，需要毫秒級別的時間延遲，實時傳輸車的位置，否則會出現(xiàn)安全事故。

幾種定位方式

全球?qū)Ш叫l(wèi)星系統(tǒng)

相對定位：慣性測量單元IMU

點云定位

定位系統(tǒng)

多傳感器融合定位

綜合來說，靠單一傳感器定位是不夠的，所以采取多傳感器融合的方案。基于卡爾曼濾波模型，整體定位效果會有更高的精度和更好的魯棒性。

卡爾曼濾波模型

卡爾曼濾波是一種高效率的遞歸濾波器，它能夠從一系列的不完全和包含噪聲的測量中，估計動態(tài)系統(tǒng)的狀態(tài)。

基于卡爾曼濾波模型，我們把自動駕駛車輛當時的位置看作是高斯分布，也就是說，車輛定位在某個區(qū)域范圍之內(nèi)，且位于中間的可能性是最大的。

隨著車輛行駛，根據(jù)運動方程，定位系統(tǒng)能夠得到車輛的位置預測。假設一輛車往前行駛了10米，于是車輛產(chǎn)生一個預測位置，然而實際行駛中，預測位置和實際位置的誤差逐漸變大。這是因為，此數(shù)據(jù)可能是由IMU給出，而IMU作為傳感器自然會存在誤差。同時假設這輛車還裝有GPS，那么GPS給出的位置信息便相當于上圖中的藍色的部分，這個定位數(shù)據(jù)也是包含一定誤差的。

于是，我們得到關于這輛車的兩個位置信息，將二者結(jié)合后便可得到較為準確且可信的結(jié)果。由此可見，卡爾曼濾波是不斷在更新迭代的，最終實現(xiàn)得到一個比較準確位置的目標。

定位系統(tǒng)的最終目標是萬里無憂，對自動駕駛的挑戰(zhàn)則是更低成本和更苛刻的外部環(huán)境。最終我們一定會把這些問題解決好，實現(xiàn)這個目標。