高精度的地圖需要強(qiáng)大的地圖堆棧，提供路由、導(dǎo)航指令和ETA計(jì)算等服務(wù)。以往， Uber工程師使用各種反饋來(lái)識(shí)別地圖錯(cuò)誤，例如，記錄和理解用戶(hù)反饋的機(jī)器學(xué)習(xí)模型，或通過(guò)評(píng)估地圖指標(biāo)來(lái)提高地圖精度。這次，Uber發(fā)布博客稱(chēng)，Uber工程師構(gòu)建了CatchME系統(tǒng)。

CatchMapError（CatchME）是一個(gè)系統(tǒng)，可以通過(guò)驅(qū)動(dòng)程序應(yīng)用程序中的匿名GPS跟蹤自動(dòng)捕獲地圖數(shù)據(jù)中的錯(cuò)誤。CatchME使用來(lái)自大型地理區(qū)域的數(shù)千萬(wàn)次駕駛的匿名和聚合數(shù)據(jù)來(lái)捕獲地圖數(shù)據(jù)錯(cuò)誤。通過(guò)CatchME，運(yùn)營(yíng)商可以快速識(shí)別并修復(fù)這些錯(cuò)誤，從而在Uber平臺(tái)上實(shí)現(xiàn)更準(zhǔn)確的路線(xiàn)和改進(jìn)的駕駛員合作體驗(yàn)。

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

使用GPS識(shí)別地圖錯(cuò)誤

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

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

在城市環(huán)境中，GPS軌跡并不完全準(zhǔn)確，因此無(wú)法得知平臺(tái)上車(chē)輛的確切位置。Uber工程師將車(chē)輛位置概率放入HMM中，維特比算法根據(jù)這些軌跡計(jì)算出車(chē)輛駛過(guò)的最可能的路段序列。有了這些信息，CatchME會(huì)報(bào)告此序列中的跟蹤異常，并突出顯示驅(qū)動(dòng)程序行為與應(yīng)用程序建議路徑之間的差異。

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

圖2（a）

圖2（b）

在圖2中，可以看見(jiàn)存在右轉(zhuǎn)限制，阻止平臺(tái)上的駕駛員向右轉(zhuǎn)。但是，根據(jù)駕駛員的行為，可以判斷這條信息可能不準(zhǔn)確。CatchME發(fā)現(xiàn)了平臺(tái)建議的導(dǎo)航和實(shí)際駕駛員行為之間的差異，使系統(tǒng)能夠識(shí)別并修復(fù)錯(cuò)誤。

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

圖3（a）：一名駕駛員左轉(zhuǎn)非法，在此圖像中以紅點(diǎn)突出顯示。駕駛員行為導(dǎo)致實(shí)際行程路線(xiàn)與建議路線(xiàn)之間的差異。

圖3（b）：噪聲GPS信號(hào)導(dǎo)致實(shí)際行程路線(xiàn)與建議路線(xiàn)之間的差異。

CatchME錯(cuò)誤檢測(cè)算法

如前所述，HMM是將GPS點(diǎn)與地圖數(shù)據(jù)連接起來(lái)的橋梁。從概念上講，維特比算法通過(guò)HMM中的所有可能狀態(tài)計(jì)算包括最可能狀態(tài)序列的路徑。理想情況下，此序列中的狀態(tài)轉(zhuǎn)換在所有可能狀態(tài)中應(yīng)具有高概率。但是，如果存在地圖數(shù)據(jù)錯(cuò)誤，則此序列仍將包括具有低概率的狀態(tài)轉(zhuǎn)換。在這種情況下，我們將序列中的狀態(tài)之間的低概率稱(chēng)為異常概率。

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

圖4

上面的圖4顯示出了用于計(jì)算某個(gè)路段上的GPS點(diǎn)的EP所考慮的因素。公式概述如下：

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

圖5：通過(guò)在其捕捉點(diǎn)S1到S2之間創(chuàng)建路線(xiàn)并測(cè)量該路線(xiàn)的距離來(lái)計(jì)算從G1到G2的轉(zhuǎn)換概率。

圖5顯示出了用于計(jì)算關(guān)于一個(gè)點(diǎn)的GPS轉(zhuǎn)移概率考慮到的因素上的特定段到另一GPS點(diǎn)上的特定段，使用下面的公式計(jì)算：

是兩個(gè)GPS點(diǎn)的半徑距離與兩個(gè)與GPS點(diǎn)相關(guān)聯(lián)的捕捉點(diǎn)之間的可路由距離之間的差值的絕對(duì)值。當(dāng)發(fā)射GPS位置時(shí)車(chē)輛穿過(guò)這兩個(gè)部分的可能性小于其他部分。

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

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

圖7：路段A和B之間存在缺失段。但是，由綠色和藍(lán)色點(diǎn)標(biāo)記的GPS點(diǎn)顯示駕駛員穿過(guò)A到B。從GPS點(diǎn)G1到GPS點(diǎn)G2的轉(zhuǎn)換概率異常低，表明G1和G2周?chē)�可能存在地圖錯(cuò)誤。

通常，維特比算法從HMM中拾取的路段序列表示車(chē)輛經(jīng)過(guò)的路段。但是，如果地圖數(shù)據(jù)有錯(cuò)誤，例如圖7中描繪的段，則該序列將包括異常低的轉(zhuǎn)移概率，表明車(chē)輛無(wú)法在段上行進(jìn)或在地圖數(shù)據(jù)上下文中的某些段之間轉(zhuǎn)換。

CatchME通過(guò)使用綠色和藍(lán)色顏色可視化可疑的GPS點(diǎn)來(lái)識(shí)別GPS軌跡之間的差異，這些顏色指示給定路線(xiàn)上的異常過(guò)渡（圖7）。在這些情況下，操作員可以快速找到該區(qū)域并修復(fù)這些錯(cuò)誤（圖2）。

縮放準(zhǔn)確性

由于建議路線(xiàn)和現(xiàn)實(shí)路線(xiàn)之間的差異不一定表示地圖數(shù)據(jù)中的錯(cuò)誤，因此捕捉給定路線(xiàn)上的錯(cuò)誤不能僅依賴(lài)于一次駕駛的結(jié)果。相反，CatchME使用來(lái)自大地理區(qū)域的數(shù)千萬(wàn)次駕駛的匿名和聚合數(shù)據(jù)來(lái)捕獲地圖數(shù)據(jù)錯(cuò)誤。

CatchME采用分而治之（D＆C）方法在不同行程中橫向擴(kuò)展。D＆C的主要目標(biāo)是對(duì)GPS軌跡和地圖數(shù)據(jù)進(jìn)行分片，以便可以并行處理它們。分片基于跟蹤和地圖數(shù)據(jù)的S2單元�？缭蕉鄠�(gè)S2細(xì)胞的跡線(xiàn)被分成多個(gè)子跡線(xiàn)，每個(gè)子跡線(xiàn)由單個(gè)S2細(xì)胞完全包含。檢測(cè)在不同的S2細(xì)胞中平行獨(dú)立運(yùn)行。下面的圖8說(shuō)明了這種高級(jí)分片。為了保證每個(gè)S2單元包括可用于檢測(cè)錯(cuò)誤的所有地圖數(shù)據(jù)，我們通常擴(kuò)展S2單元邊界，以便所有地圖數(shù)據(jù)及其相關(guān)的GPS點(diǎn)都在范圍內(nèi)。

圖8：使用S2單元對(duì)GPS軌跡和地圖數(shù)據(jù)進(jìn)行分片使我們能夠大規(guī)模地收集有關(guān)地圖數(shù)據(jù)錯(cuò)誤的見(jiàn)解。

但是，使用靜態(tài)S2單元分區(qū)行程和映射數(shù)據(jù)有時(shí)無(wú)法提供足夠的并發(fā)性。例如，舊金山國(guó)際機(jī)場(chǎng)（SFO）等某些地區(qū)的S2小區(qū)的駕駛次數(shù)遠(yuǎn)遠(yuǎn)多于農(nóng)村地區(qū)相同水平的S2小區(qū)。

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

圖9：一個(gè)S2單元中的跡線(xiàn)被劃分為具有相同地圖數(shù)據(jù)的兩個(gè)S2單元。

這種方法消除了由高密度單元引起的瓶頸，并且導(dǎo)致更準(zhǔn)確的結(jié)果，因?yàn)槊總�(gè)單元仍然足夠大，以包含用于地圖匹配和錯(cuò)誤檢測(cè)的完整地圖數(shù)據(jù)上下文和GPS點(diǎn)。

過(guò)濾誤報(bào)

作為縮放CatchME的結(jié)果，足夠的差異信號(hào)（異常概率）提供了用于評(píng)估數(shù)據(jù)錯(cuò)誤的統(tǒng)計(jì)視圖。聚合來(lái)自大量駕駛的結(jié)果背后的哲學(xué)是，如果看到在駕駛報(bào)告的給定地點(diǎn)的異常概率的一致性，這種差異的根本原因更可能是地圖數(shù)據(jù)錯(cuò)誤而不是非法駕駛行為或噪聲GPS信號(hào)。

由于CatchME已經(jīng)確定了位于具有16級(jí)大�。⊿2小區(qū)統(tǒng)計(jì)）的某些S2小區(qū)中的GPS點(diǎn)之間的異常概率方面的差異，平均大小為19，793平方米，因此CatchME將每個(gè)S2小區(qū)視為基本錯(cuò)誤單元。通過(guò)聚合這些單元，CatchME可以確定哪些錯(cuò)誤更有可能影響驅(qū)動(dòng)程序合作伙伴應(yīng)用程序的用戶(hù)體驗(yàn)。

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

圖10：由黃點(diǎn)動(dòng)畫(huà)顯示的GPS跟蹤顯示GPS跟蹤移位。CatchME忽略了這種情況，即使它引發(fā)了視差信號(hào)。

更好的地圖，更好的用戶(hù)體驗(yàn)

CatchME的結(jié)果已經(jīng)證明了一種非常有前景的方法。在推出后的前三個(gè)月內(nèi)，CatchME檢測(cè)到超過(guò)28，000個(gè)地圖錯(cuò)誤。在Uber的地圖上糾正這些錯(cuò)誤大大提高了駕駛ETA，導(dǎo)航和用戶(hù)體驗(yàn)的準(zhǔn)確性。

未來(lái)，Uber計(jì)劃通過(guò)增強(qiáng)算法和利用衛(wèi)星圖像等其他證據(jù)來(lái)進(jìn)一步提高CatchME的精度。結(jié)合客戶(hù)報(bào)告的地圖錯(cuò)誤，CatchME發(fā)現(xiàn)的地圖錯(cuò)誤將為駕駛員提供更好的體驗(yàn)。

參考資料：

[1] https://eng.uber.com/mapping-accuracy-with-catchme/

[2] Newson P , Krumm J . [ACM Press the 17th ACMSIGSPATIAL International Conference - Seattle, Washington(2009.11.04-2009.11.06)] Proceedings of the 17th ACM SIGSPATIAL InternationalConference on Advances in Geographic Information Systems - GIS "09 -Hidden Markov map matching through noise and sparseness[J]. 2009:336.