Uber提高地图精度绝招——CatchME系统

高精度的舆图需要壮大的舆图客栈,提供路由、导航指令和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发现的舆图错误将为驾驶员提供更好的体验。

参考资料:

[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.

留下评论