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．