侵權(quán)投訴
訂閱
糾錯(cuò)
加入自媒體

Uber提高地圖精度絕招:CatchME系統(tǒng)

高精度的地圖需要強(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ē)赡艽嬖诘貓D錯(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.

聲明: 本文由入駐維科號(hào)的作者撰寫(xiě),觀點(diǎn)僅代表作者本人,不代表OFweek立場(chǎng)。如有侵權(quán)或其他問(wèn)題,請(qǐng)聯(lián)系舉報(bào)。

發(fā)表評(píng)論

0條評(píng)論,0人參與

請(qǐng)輸入評(píng)論內(nèi)容...

請(qǐng)輸入評(píng)論/評(píng)論長(zhǎng)度6~500個(gè)字

您提交的評(píng)論過(guò)于頻繁,請(qǐng)輸入驗(yàn)證碼繼續(xù)

  • 看不清,點(diǎn)擊換一張  刷新

暫無(wú)評(píng)論

暫無(wú)評(píng)論

文章糾錯(cuò)
x
*文字標(biāo)題:
*糾錯(cuò)內(nèi)容:
聯(lián)系郵箱:
*驗(yàn) 證 碼:

粵公網(wǎng)安備 44030502002758號(hào)