可靠的运输需要一个健壮的地图堆栈，提供诸如路由、导航指示和ETA计算等服务。地图数据中的错误会严重影响服务，导致用户体验不佳。优步工程师使用各种反馈来源来识别地图错误，例如，机器学习模型记录和理解用户反馈，或通过评估地图度量提高地图质量。
在本文中，我们将讨论另一种反馈来源:利用GPS轨迹来检测地图数据中的不一致性。为了演示，在上面的图1中，我们比较了在相同位置开始和结束的两次旅行，以显示地图数据错误如何导致明显较长的旅行时间。
为了解决这类问题，我们构建了CatchMapError (CatchME)，这是一个通过司机应用程序的匿名GPS跟踪自动捕获地图数据错误的系统。CatchME使用来自大型地理区域的数千万次旅行的匿名和聚合数据来捕获地图数据错误。通过CatchME，我们的运营商可以快速识别并修复这些错误，从而在我们的平台上提供更准确的路线，并改善驾驶员与合作伙伴的体验。
用GPS识别地图错误
CatchME的基本思想是优步行程GPS轨迹反映地面真相。通过分析地图匹配的异常，CatchME识别出地图与地面真相之间的差异。这些差异通常是由地图数据错误引起的，可以通过更新地图来解决。
CatchME的第一个挑战是找出司机的导航行为(由GPS记录的行程轨迹)是否与我们建议的地图路线不符。我们设计了CatchME来捕捉地图数据上的GPS旅行轨迹隐马尔可夫模型(HMM)，使工具能够报告预期和实际路由之间的差异。与传统的假设地图数据有效的地图匹配不同，CatchME专注于发现差异，而不一定信任地图数据。
GPS追踪并不完全准确，尤其是在城市环境中，所以我们不知道平台上车辆的确切位置。我们把车辆定位概率输入HMM，然后维特比算法根据这些轨迹计算出车辆最可能经过的路段序列。有了这些信息，CatchME就会报告这一序列的异常轨迹，并突出显示司机行为与应用程序建议路线之间的差异。
下图2描述了GPS轨迹如何突出地图数据中的不准确性的示例。在本例中，旧金山金门公园的一条路线(a)显示，一名司机在第八大道和富尔顿街的十字路口右转，但该司机的搭档偏离了(b)建议的路线:
在图2中，我们发现有一个右转限制，不鼓励平台上的驾驶员伙伴右转。然而，根据司机和伴侣的行为，我们意识到地图中的这条信息可能是不准确的。CatchME将我们建议的导航和实际驾驶员行为之间的差异可视化，使操作人员能够识别和修复错误。
建议路线和GPS轨迹之间的差异不一定是由于地图数据错误造成的。下面的图3强调了造成这些差异的其他两个潜在原因:(a)非法或危险的司机行为;(b)嘈杂的GPS痕迹不能提供足够的具体数据来清楚地确定所走的路线。
CatchME错误检测算法
如前所述，HMM是连接行程GPS点与地图数据的桥梁。从概念上讲，维特比算法计算一条路径，其中包括HMM中所有可能状态的最可能状态序列。理想情况下，该序列中的状态转换在所有可能的状态中应该有很高的概率。然而，如果存在地图数据错误，该序列仍将包括低概率的状态转换。在这种情况下，我们将序列中状态之间的低概率称为异常概率。
发射概率(EP)和跃迁概率(TP)将首先放入HMM中。排放概率表示车辆在特定时刻出现在特定路段的可能性。过渡概率表示车辆在一定时间内从一个路段移动到另一个路段的可能性。因此，对于一个GPS点用米附近有多少路段，都会有米表示GPS轨迹在每个路段上的可能性的发射概率。GPS点G1，哪有米附近段，和G2，其中有n附近的部分，有M * n过渡的可能性。这些概率在HMM中，Viterbi算法从中提取具有最大概率的状态序列，这些状态最有可能代表车辆行驶的路段。
上图4给出了计算某路段GPS点的发射概率所考虑的因素。公式概述如下:
在哪里
为GPS点与其在路段上的抓点之间的距离。发射概率表示如果车辆确实在道路段上，GPS将被观察到的可能性。(了解更多关于发射概率的信息，请参阅微软研究院的论文，雷竞技是骗人的基于噪声和稀疏性的隐马尔可夫映射匹配）.
上图5说明了计算一个GPS点的转移概率所考虑的因素
在某个片段上
到另一个GPS点
在某个片段上
，计算公式如下:
在哪里
为两个GPS点的哈弗距离与与GPS点关联的两个快照点之间的可路由距离之差的绝对值。如果发射GPS位置时，车辆穿越这两个段的可能性较小比别人更伟大。
在这个计算中，发射概率和跃迁概率形成一个矩阵。维特比提取全局最优路段序列，这些路段最有可能是车辆正在行驶的路线。下面的图6演示了一个示例G1，G2,G3是GPS点，S1通过S7是分段，绿色圆圈是发射概率，黑色箭头是跃迁概率。运行Viterbi算法后，得到道路段序列S4，S3,S1，以及G1，G2,G3继续这些序列。
通常情况下，维特比算法从HMM中提取的路段序列表示车辆穿过的路段。然而，如果我们的地图数据有错误，比如缺少图7中描述的段，这个序列将包含异常低的转换概率，这表明车辆不能在地图数据上下文中的某个段上行驶或在某些段之间行驶，即使车辆实际上在现实世界中是这样做的。这就是CatchME感兴趣的道路分段序列的差异。
CatchME通过使用绿色和蓝色来可视化可疑的GPS点移动来识别GPS迹线之间的差异(图7)。在这些情况下，运营商可以快速定位该区域并修复这些错误(图2)。
缩放精度
由于建议路线和实际路线之间的差异并不一定代表地图数据中的错误，因此捕捉给定路线上的错误不能仅仅依赖于一次旅行的结果。相反，CatchME使用来自大地区数千万次旅行的匿名和聚合数据来捕捉地图数据错误。
CatchME应用分治(D&C)方法在行程中横向缩放。D&C的主要目标是分割GPS轨迹和地图数据，以便它们可以并行处理。分片是基于S2细胞轨迹和地图数据。跨多个S2单元的跟踪被分成多个子跟踪，每个子跟踪完全包含在单个S2单元中。检测在不同的S2单元中并行独立运行。下面的图8演示了这种高级分片。为了保证每个S2单元格包含所有可能用于检测错误的地图数据，我们通常扩展S2单元格边界，以便所有地图数据及其相关的GPS点都在范围内。
但是，使用静态S2单元划分行程和映射数据有时不能提供足够的并发性。例如，某些地区(如旧金山国际机场(SFO))的S2单元比农村地区相同水平的S2单元有更多的行程。
为了进一步提高CatchME的性能，我们为每个高密度单元制作了多个副本。每个副本都有相同的地图数据，但有不同且均匀分布的行程集，如下图9所示:
这种方法消除了高密度单元造成的瓶颈，并导致更准确的结果，因为每个单元仍然足够大，可以包含完整的地图数据上下文和用于地图匹配和错误检测的GPS点。
过滤虚假警报
作为缩放CatchME的结果，足够的差异信号(异常概率)为我们提供了评估数据错误的统计视图。从大量出行中汇总结果背后的理念是，如果我们看到出行报告的给定地点的异常概率的一致性，这种差异的根本原因更可能是地图数据错误，而不是非法驾驶行为或嘈杂的GPS信号。
由于CatchME已经识别出位于某些S2单元的16级大小的GPS点之间的异常概率差异(S2小区统计)，平均面积为19793平方米，CatchME将每个S2单元作为基本误差单元。通过聚合这些单元，CatchME确定哪些错误更有可能影响司机-合作伙伴应用程序的用户体验。
如图3(b)所示，差异不一定是错误。CatchME将视差信号(或异常转换概率)存在的GPS点以多边形链的形式连接起来(通常该多边形链包含大约40个GPS点)。如果这条链的几何形状不是有效的， CatchME将忽略此错误信号。CatchME还观察到一定数量的错误警报，这是由于GPS轨迹偏移如图10所示，其中GPS轨迹穿过建筑物，而不是靠近道路。如果这些GPS点跨越了超过一定阈值的多个物理建筑，CatchME将忽略这种差异。
更好的地图，更好的用户体验
虽然我们只是触及了我们团队使用被动信号检测地图数据错误的表面工作，但CatchME的结果已经证明了一种非常有前途的方法。在推出的头三个月里，CatchME检测到超过2.8万个地图错误。纠正地图上的这些错误极大地提高了我们的旅行预估、导航和用户体验的准确性。
在未来，我们计划通过增强我们的算法和利用额外的证据，如卫星图像，进一步提高CatchME的精度和召回率。结合客户报告的地图错误，CatchME发现的错误将为乘客和司机合作伙伴在我们的应用程序上提供更无缝的体验。
如果你有兴趣为Uber的地图堆栈做出贡献，并解决大规模跨越数字和物理世界的问题，可以考虑申请一个职位角色在我们队。
