使用定位和导航全球定位系统(GPS)已经深入到我们的日常生活中，对优步的服务尤其重要。为了安排快速、高效的搭车，我们的GPS技术需要知道匹配的乘客和司机的位置，并提供从司机当前位置到需要搭车的地方，再到乘客选定的目的地的导航指导。为了使这一过程无缝衔接，对乘客和司机的位置估计需要尽可能精确。
自1973年全球定位系统(GPS)的推出在美国，我们提高了对世界的理解，经历了计算能力的指数增长，并开发了强大的算法来模拟机器人等领域的不确定性。虽然我们的生活越来越依赖GPS，但GPS工作的基本原理并没有发生太大变化，这导致了显著的性能限制。在我们看来，现在是时候重新考虑1973年的一些初始假设了，这些假设是正确的，关于我们在哪里和如何使用GPS，以及我们可以带来的计算能力和附加信息来改进它。
虽然GPS在晴朗的天空下运行良好，但当我们最需要它的时候，它的位置估计可能非常不准确(误差幅度达50米或更多):在人口密集和建筑密集的城市地区，我们的许多用户都位于这些地区。为了克服这一挑战，我们为Android开发了GPS软件升级，通过利用3D地图和对GPS数据执行复杂的概率计算的客户端-服务器架构，大大提高了城市环境中的定位精度Android的GNSS api．
在本文中，我们将讨论GPS在城市环境中表现不佳的原因，并概述我们如何使用在服务器基础设施上大规模部署的先进信号处理算法来解决这个问题。
一点关于GPS/GNSS的背景知识
在详细讨论我们的方法之前，让我们快速回顾一下GPS是如何工作的，以便理解为什么它在高层城市环境中会不准确。
全球定位系统(GPS)是由美国政府运营的30多颗卫星组成的网络，在大约2万公里的高空绕地球运行。(现在大多数手机都能接收到类似的俄语信号。”格洛纳斯“卫星。)这些卫星发出无线电频率信号，GPS接收器，比如手机上的接收器，可以锁定这些信号。重要的是，这些卫星会公布发射信号的时间。
对于接收器处理其信号的每颗卫星，接收时间和发射时间(飞行时间)之间的差，乘以光速，称为伪距．如果卫星和接收器的时钟是同步的，并且信号沿着直线视距路径传播，那么这将等于到卫星的实际距离。然而，时钟不是同步的，因此接收器需要解决四个未知数，它自己在地球仪上的3D坐标，以及它的时钟偏差。因此，我们需要至少四个卫星(四个方程)来求解这四个未知数。
如果我们忽略时钟偏差，我们可以直观地解释GPS接收器执行的位置估计，通过以卫星为中心的球与每个球的半径由伪橙度给出的相交。在实践中，GPS接收器处理来自大量卫星的信号(在一个开放的领域中可以看到多达20颗GPS和GLONASS卫星)，拥有超过最小数量的方程提供了额外的抗噪声、阻塞等的鲁棒性。除了GPS和GLONASS，一些新的/未来的接收器可以/将处理来自其他卫星系统的信号。其他即将上线的卫星导航系统也是如此伽利略，由欧盟运营，IRNSS在印度,北斗该公司由中国运营。更一般的说法GNSS(全球卫星导航系统)包含了这些系统。(我们将在本文的其余部分使用这个术语。)
为什么在城市环境中GNSS定位不准确
基于gnss的定位背后的一个主要假设是接收器对其计算的每颗卫星都有直接的视线。这种方法在开阔的地形中非常有效，但在城市环境中就行不通了，如下图3所示:
建筑物经常挡住卫星的视线，因此接收器经常处理与其他建筑物强烈反射相对应的信号。这种现象造成的伪坐标的显著误差(正偏移)可能导致位置估计的误差，在城市峡谷中可达50米或更多。我们大多数在大城市闲逛、开车或叫优步的人都亲身经历过这些问题。
卫星信号强度救援
我们提高定位精度的方法利用了GNSS信号的阻塞，这给标准接收器带来了麻烦。怎么做?对于Android手机，LocationManager API不仅提供手机的位置估计，还提供每个GNSS卫星的信噪比(SNR)。如果我们把这些“信号强度”信息与3D地图放在一起，那么我们就可以获得非常有价值的位置信息。下面的图4显示了如何使用卫星信噪比和3D地图来推断我们在街道的哪一边的简化版本:
放大到细节，我们的方法依赖于将以下直觉放在一个数学框架中:如果卫星的信噪比很低，那么视线路径可能被阻塞或阴影;如果信噪比高，则LOS可能是清晰的。限定词“可能”在这里是至关重要的:即使当接收器在阴影区域，强反射信号仍然可以到达它，即使它在一个清晰的区域，接收到的信号可能是弱的(因为LOS和反射路径之间的破坏性干扰，一种现象称为多径衰落)．此外，通常情况下，3D地图并不完全准确，当然也不能捕捉到地图中未出现的大型移动物体(如卡车)的随机阻塞。这给这个过程增加了额外的不确定性。
使用射线追踪的概率阴影匹配
虽然对携带有用位置信息的卫星信号强度的直觉是可靠的，但它必须在概率框架内加以充实。对于接收器的任何可能位置，我们可以使用3D地图检查连接该位置到卫星的光线是否被阻挡。现在，使用LOS和阴影条件下信噪比的概率分布模型，我们确定了该卫星的信噪比测量的可能性。例如，如果位置被遮蔽，那么高信噪比的可能性就很低。基于卫星信噪比的给定位置的总体可能性是不同卫星对应的可能性的乘积。通过在可能位置的网格上这样做，我们获得了可能接收器位置的似然表(或热图)，仅基于卫星信号强度。我们称之为过程匹配概率的影子．
来自概率阴影匹配的似然面或热图总结了来自卫星信噪比测量的信息。然而，正如我们从下面的图6中看到的，这个热图可能非常复杂。它可以有许多不同的、广泛分离的火锅(本地最大值)，通常对应于街道的特定一侧，但有时仍然在错误的位置(例如，幽灵)。为了缩小我们的定位范围避免锁定幽灵，我们现在必须把这些信息和更多的信息融合起来。
粒子滤波信息融合
对于Android手机，除了卫星信号强度之外，我们使用的信息通常只是标准的GNSS定位，但也可以是Android fusion定位，其中可能包括基于wifi的定位。由于这个位置可能非常不准确，单时间瞬间(一次)融合GNSS固定与阴影匹配可能性通常会导致糟糕的性能。为了充分利用来自卫星信号强度的信息，我们在建成区较少信任GPS(图6中的灰色GPS不确定度椭圆是我们使用的典型模型，而改进GPS的黑色不确定度椭圆是我们算法的输出)。因此，我们使用过去的测量数据，并使用适应于应用程序的运动模型(例如，行人vs.车辆运动)来限制位置随时间的演变。这是通过使用粒子滤波，该算法通过一组加权粒子近似计算了接收器在任何给定时间位置的概率分布。换句话说，我们使用数千个假设的位置(即粒子)来估计手机的位置。
随着时间的推移，概率权重和粒子位置根据测量和运动模型而演变。由于来自概率阴影匹配的热图有如此多的局部极大值，而且由于GNSS修正可能有如此大的异常值，我们不能使用标准的技术，如卡尔曼滤波器或者是扩展卡尔曼滤波器，这依赖于跟踪的概率分布很好地近似于钟形高斯分布．粒子过滤器允许我们以更高的复杂性为代价近似任意分布，这就是我们的服务器基础设施的作用。
从信号处理到大规模软件
粒子过滤和光线跟踪的结合为后端服务器生态系统带来了复杂性，使服务具有非常强的状态。
有两种状态在起作用:每个用户粒子过滤器状态和用于射线追踪的每个区域3D地图。粒子过滤器的使用需要一定程度的服务器亲和。对我们的服务的每个新请求都必须路由到相同的后端服务器进行处理，以便更新正确的粒子过滤器。此外，由于3D地图的规模很大，每个后端服务器只能在RAM中保存一小部分3D世界。
由于每台服务器只能保存几平方公里的地图数据，并不是所有的服务器都能够为所有用户服务。本质上，为我们的解决方案实现后端系统需要创建一个考虑服务器3D映射状态的粘性会话路由层。除了内部测试和性能评估，我们还使用Uber骑手应用的内部版本在我们自己的Android设备上运行抽查，如下图9所示:
前进
准确估计乘客和司机的位置是实现优步的使命的关键条件，该使命是为每个人提供像自来水一样可靠的交通，在任何地方。为了完成我们的使命，传感、智能和研究团队正在研究多种方法，通过创造性地使用移动设备上的传感器和计算，以及雷竞技是骗人的我们服务器基础设施的计算能力，来改善定位。先进的信号处理、机器学习算法和软件的大规模结合具有巨大的潜力，我们一直在寻找有才华和高度上进心的个人(软件和算法工程师，数据可视化的工程师,机器学习工程师)加入我们，帮助实现这一潜力。
有兴趣了解更多吗?看看我们最近关于这项研究的介绍:雷竞技是骗人的
Danny Iland, Andrew Irish, Upamanyu Madhow和Brian Sandler是Uber感知、推断和研究团队的成员。雷竞技是骗人的丹尼、安德鲁和乌帕曼尤尼是加州大学圣巴巴拉分校领导这项研究的最初小组的成员。雷竞技是骗人的在将这项工作转化为一家初创公司后，他们演示了基于服务器的粒子过滤技术，使用公开的空中激光雷达数据构建的3D地图来改善旧金山的位置。他们于2016年7月加入Uber。
