高精度的地圖需要強大的地圖堆棧，提供路由、導航指令和ETA計算等服務。以往， Uber工程師使用各種反饋來識別地圖錯誤，例如，記錄和理解用戶反饋的機器學習模型，或通過評估地圖指標來提高地圖精度。這次，Uber發布博客稱，Uber工程師構建了CatchME系統。

CatchMapError（CatchME）是一個系統，可以通過驅動程序應用程序中的匿名GPS跟蹤自動捕獲地圖數據中的錯誤。CatchME使用來自大型地理區域的數千萬次駕駛的匿名和聚合數據來捕獲地圖數據錯誤。通過CatchME，運營商可以快速識別并修復這些錯誤，從而在Uber平臺上實現更準確的路線和改進的駕駛員合作體驗。

圖1：左側地圖上缺少的路段導致7.6分鐘的ETA；右側的精確地圖顯著降低了ETA，為騎手和駕駛者提供了更好的體驗。

使用GPS識別地圖錯誤

CatchME的基本理念是Uber使用GPS追蹤反映地面實況。通過分析道路地圖匹配的異常，CatchME識別地圖與地面實況之間的差異。這些差異通常是由地圖數據錯誤引起的，可以通過更新地圖來解決。

CatchME的第一個挑戰是找出駕駛員的導航行為（由GPS軌跡記錄）是否與建議的地圖路線顯示不一致。CatchME，使用隱馬爾可夫模型（HMM）在地圖數據上捕捉GPS軌跡，從而報告預期路線和實際路線之間的差異。

在城市環境中，GPS軌跡并不完全準確，因此無法得知平臺上車輛的確切位置。Uber工程師將車輛位置概率放入HMM中，維特比算法根據這些軌跡計算出車輛駛過的最可能的路段序列。有了這些信息，CatchME會報告此序列中的跟蹤異常，并突出顯示驅動程序行為與應用程序建議路徑之間的差異。

下面的圖2描繪了GPS軌跡如何突出地圖數據中的不準確性的示例。在這種情況下，舊金山金門公園的一條路線（a）顯示一名司機在第8大道和富爾頓街的交叉路口右轉，但司機偏離了（b）建議路線：

圖2（a）

圖2（b）

在圖2中，可以看見存在右轉限制，阻止平臺上的駕駛員向右轉。但是，根據駕駛員的行為，可以判斷這條信息可能不準確。CatchME發現了平臺建議的導航和實際駕駛員行為之間的差異，使系統能夠識別并修復錯誤。

建議路線與GPS軌跡之間的差異不一定是由于地圖數據錯誤造成的。下面的圖3突出顯示了造成這些差異的另外兩個可能原因：（a）非法或危險的駕駛員行為；（b）噪聲GPS軌跡，即沒有提供足夠的具體數據來清楚地確定所采用的路線。

圖3（a）：一名駕駛員左轉非法，在此圖像中以紅點突出顯示。駕駛員行為導致實際行程路線與建議路線之間的差異。

圖3（b）：噪聲GPS信號導致實際行程路線與建議路線之間的差異。

CatchME錯誤檢測算法

如前所述，HMM是將GPS點與地圖數據連接起來的橋梁。從概念上講，維特比算法通過HMM中的所有可能狀態計算包括最可能狀態序列的路徑。理想情況下，此序列中的狀態轉換在所有可能狀態中應具有高概率。但是，如果存在地圖數據錯誤，則此序列仍將包括具有低概率的狀態轉換。在這種情況下，我們將序列中的狀態之間的低概率稱為異常概率。

排放概率（EP）和轉移概率（TP）將首先放入HMM中。EP表示車輛在某些時刻出現在某些路段上的可能性。TP表示車輛在一定持續時間內從一個路段移動到另一個路段的可能性。因此，對于附近具有m個路段的一個GPS點，將存在m個EP，其表示每個路段上的該GPS軌跡的可能性。對于GPS點G1，其中有米附近的部分，和G2，其中有?鄰近段，有m*n個TP。這些概率在HMM中，維特比算法從中獲取具有最大概率的狀態序列，該概率最可能代表車輛正在移動的路段。

圖4

上面的圖4顯示出了用于計算某個路段上的GPS點的EP所考慮的因素。公式概述如下：

GPS點與路段上的捕捉點之間的半徑距離在哪里。EP表示如果車輛實際上在路段上，GPS將被觀察的可能性。（在MicrosoftResearch論文中了解有關發射概率的更多信息，通過噪聲和稀疏性匹配隱藏馬爾可夫地圖）。

圖5：通過在其捕捉點S1到S2之間創建路線并測量該路線的距離來計算從G1到G2的轉換概率。

圖5顯示出了用于計算關于一個點的GPS轉移概率考慮到的因素上的特定段到另一GPS點上的特定段，使用下面的公式計算：

是兩個GPS點的半徑距離與兩個與GPS點相關聯的捕捉點之間的可路由距離之間的差值的絕對值。當發射GPS位置時車輛穿過這兩個部分的可能性小于其他部分。

在該計算中，EP和TP形成矩陣。維特比以最大概率獲取全球最佳路段序列，這些概率最有可能是車輛正在行駛的路線。下面的圖6示出了G1，G2和G3是GPS點的示例，S1到S7是段，綠色圓圈是發射概率，黑色箭頭是轉換概率。運行維特比算法后，得到路段序列S4，S3和S1，以及G1，G2和G3的表示繼續這些序列。

圖6：在該示例中，維特比算法通過使用HMM來計算道路過渡S4，S3和S1的最可能的分段序列。這三個段代表GPSG1，G2和G3。

圖7：路段A和B之間存在缺失段。但是，由綠色和藍色點標記的GPS點顯示駕駛員穿過A到B。從GPS點G1到GPS點G2的轉換概率異常低，表明G1和G2周圍可能存在地圖錯誤。

通常，維特比算法從HMM中拾取的路段序列表示車輛經過的路段。但是，如果地圖數據有錯誤，例如圖7中描繪的段，則該序列將包括異常低的轉移概率，表明車輛無法在段上行進或在地圖數據上下文中的某些段之間轉換。

CatchME通過使用綠色和藍色顏色可視化可疑的GPS點來識別GPS軌跡之間的差異，這些顏色指示給定路線上的異常過渡（圖7）。在這些情況下，操作員可以快速找到該區域并修復這些錯誤（圖2）。

縮放準確性

由于建議路線和現實路線之間的差異不一定表示地圖數據中的錯誤，因此捕捉給定路線上的錯誤不能僅依賴于一次駕駛的結果。相反，CatchME使用來自大地理區域的數千萬次駕駛的匿名和聚合數據來捕獲地圖數據錯誤。

CatchME采用分而治之（D＆C）方法在不同行程中橫向擴展。D＆C的主要目標是對GPS軌跡和地圖數據進行分片，以便可以并行處理它們。分片基于跟蹤和地圖數據的S2單元。跨越多個S2細胞的跡線被分成多個子跡線，每個子跡線由單個S2細胞完全包含。檢測在不同的S2細胞中平行獨立運行。下面的圖8說明了這種高級分片。為了保證每個S2單元包括可用于檢測錯誤的所有地圖數據，我們通常擴展S2單元邊界，以便所有地圖數據及其相關的GPS點都在范圍內。

圖8：使用S2單元對GPS軌跡和地圖數據進行分片使我們能夠大規模地收集有關地圖數據錯誤的見解。

但是，使用靜態S2單元分區行程和映射數據有時無法提供足夠的并發性。例如，舊金山國際機場（SFO）等某些地區的S2小區的駕駛次數遠遠多于農村地區相同水平的S2小區。

為了進一步提高CatchME的性能，為每個高密度單元制作了多個副本。每個副本具有相同的地圖數據，但是具有不同且均勻分布的行程集，如下面的圖9所示：

圖9：一個S2單元中的跡線被劃分為具有相同地圖數據的兩個S2單元。

這種方法消除了由高密度單元引起的瓶頸，并且導致更準確的結果，因為每個單元仍然足夠大，以包含用于地圖匹配和錯誤檢測的完整地圖數據上下文和GPS點。

過濾誤報

作為縮放CatchME的結果，足夠的差異信號（異常概率）提供了用于評估數據錯誤的統計視圖。聚合來自大量駕駛的結果背后的哲學是，如果看到在駕駛報告的給定地點的異常概率的一致性，這種差異的根本原因更可能是地圖數據錯誤而不是非法駕駛行為或噪聲GPS信號。

由于CatchME已經確定了位于具有16級大小（S2小區統計）的某些S2小區中的GPS點之間的異常概率方面的差異，平均大小為19，793平方米，因此CatchME將每個S2小區視為基本錯誤單元。通過聚合這些單元，CatchME可以確定哪些錯誤更有可能影響驅動程序合作伙伴應用程序的用戶體驗。

如圖3（b）所示，差異不一定是錯誤。CatchME連接GPS點，其中視差信號（或異常轉移概率）作為多邊形鏈存在（通常該多邊形鏈包括大約40個GPS點）。如果此鏈的幾何無效，CatchME將忽略此錯誤信號。CatchME還觀察到一定數量的錯誤警報，這些錯誤警報是由于下面的圖10所示的GPS軌跡偏移引起的，其中GPS軌跡穿過建筑物而不是靠近道路移動。如果這些GPS點跨越多個物理建筑大于某個閾值，CatchME將忽略這種差異。

圖10：由黃點動畫顯示的GPS跟蹤顯示GPS跟蹤移位。CatchME忽略了這種情況，即使它引發了視差信號。

更好的地圖，更好的用戶體驗

CatchME的結果已經證明了一種非常有前景的方法。在推出后的前三個月內，CatchME檢測到超過28，000個地圖錯誤。在Uber的地圖上糾正這些錯誤大大提高了駕駛ETA，導航和用戶體驗的準確性。

未來，Uber計劃通過增強算法和利用衛星圖像等其他證據來進一步提高CatchME的精度。結合客戶報告的地圖錯誤，CatchME發現的地圖錯誤將為駕駛員提供更好的體驗。