如何打到离你最近的网约车，算法来分配！

全文共3448字，预计学习时长9分钟

图源：unsplash

 

当你用手机叫车时，Lyft是如何匹配与你行程最为适合的司机的呢？要做出调度决策，首先要解决一个问题：司机在哪里？Lyft根据司机手机中的GPS数据来回答该问题。然而，这样得到的GPS数据通常存在噪声，而且与道路不匹配。

 

为使原始数据更清晰，我们通过算法来运行数据，该算法获取原始位置，并返回更精确的路网位置，这个过程被称为地图匹配。最近开发并推出的一项全新的地图匹配算法，能够提高司机定位精确度和Lyft的市场效率。本文就将讨论这一新模型的细节。

 

 

定位数据通常存在噪声，而且与道路不匹配。

什么是地图匹配？

 

地图匹配是将原始GPS位置映射到路网上路段的过程，用于对车辆的行驶道路做出判断。

 

 

为什么需要地图匹配？

 

对于Lyft，地图匹配有以下两个主要用途：

 

· 旅程结束时，计算司机驾驶距离以结算车费。

· 实时地向ETA（预计到达时间）团队提供确切位置，做出调度决策，并在司机应用程序上显示司机车辆。

 

实时地图匹配有两个应用程序：在司机应用程序上准确显示司机车辆（左）；做出高效的调度决策（右）。

这两种情况的不同之处在于它们的限制条件：我们需要快速执行实时的地图匹配（低延迟），且位置仅在当前时间可用。然而，在行程结束时，延迟要求的迫切性降低，我们可以获得整个驾驶过程（允许我们从未来的位置“倒放”）。

 

因此，可使用略有不同的方法解决行程结束地图匹配（EORMM）和实时地图匹配（RTMM）。本文将专注用于实时地图匹配的算法。

 

为什么地图匹配具有挑战性？

 

糟糕的地图匹配会导致ETA不准确，进而做出糟糕的调度决策，导致司机和乘客都不愉快。因此，地图匹配的质量将会直接影响Lyft的市场，并对用户体验产生重要影响。地图匹配主要面临以下几大挑战。

 

首先，正如Yunjie博客中所说的，在城市峡谷（被高大建筑环绕的街道）、立体交叉道路或者地下隧道这些区域，从手机中收集的位置数据充满噪声。这些区域对于地图匹配算法具有很大的挑战性，并且由于许多Lyft呼叫地点都在这里，因此在这些区域进行准确的地图匹配更显重要。

 

除了噪声和道路形状，另一挑战是缺乏地面实况：司机行驶过程中，我们不能确切知道司机的真实位置，因此必须寻找替代指标来评估模型的准确性。

 

最后，地图匹配算法的表现取决于路网数据的质量。该问题已经由Lyft的另一地图团队解决。详见Albert的博客以了解我们是如何使内部地图更加精确的：https://eng.lyft.com/how-lyft-creates-hyper-accurate-maps-from-open-source-maps-and-real-time-data-8dcf9abdd46a。

 

那么，我们如何解决地图匹配问题呢？

 

这里不会详细讨论解决地图匹配的所有技术，对于常见解决方案的回顾，可以去看看Quddus等人的研究。

 

使用状态空间模型（statespace models）可以较好地解决该问题。该模型是时间序列模型，其系统具有“隐含”状态，不能直接观察，但能引起可见观察。这里，隐含状态是尝试估算的车辆在路网上的实际位置。

 

我们只观察隐含状态的修正版本：观察值（原始位置数据）。我们假设系统状态的演化仅依赖于当前状态（马尔可夫假设），并进一步定义了隐含到隐含状态的转移密度和隐含到观察状态的转移密度。

 

我们尝试估算的车辆在路网上的实际位置即“隐藏”状态，但是只观察隐藏状态的修正版本：观察值（原始位置数据）。

地图匹配常用的状态空间模型是离散状态的隐马尔可夫模型（HMM，HiddenMarkov Model）。在该系统中，通过观察路段上的最接近点找到候选，并使用维特比算法（Viterbi algorithm）找到可能性最大的隐藏状态序列。

 

然而，隐马尔可夫模型（HMM）具有以下局限性：

 

· 对于不同建模选择和输入数据，灵活性相对不好

· 复杂度高（O(N²)，N是每个状态下可能的候选数）

· 不能较好地处理高（稍高）频率观测

 

基于这些原因，我们开发了一种新型实时地图匹配算法，其更加精确，且能更灵活地结合额外的传感器数据。

 

基于（无迹）卡尔曼滤波器的新型模型

 

卡尔曼滤波器基础知识

 

先来回顾一下卡尔曼滤波器（Kalmanfilter）的基础知识。与离散态的HMM不同，卡尔曼滤波器允许隐含状态连续分布。就其核心来说，卡尔曼滤波器仅仅是一个线性高斯模型，其使用以下方程对系统建模。

 

通过这些方程，卡尔曼滤波器使用闭环预测-修正步骤迭代更新其系统状态的表示，从t-1阶到t阶。

 

卡尔曼滤波器估计

然而，卡尔曼滤波器也具有局限性，它只能处理线性问题。为了处理非线性问题，卡尔曼滤波器已经推广为扩展卡尔曼滤波器（EKF）和无迹卡尔曼滤波器（UKF）等。卡尔曼滤波器和UKF之间的技术差异并不十分重要：可以简单假设UKF像标准的线性卡尔曼滤波器一样工作。

 

边缘化粒子滤波器（Marginalized ParticleFilter）

 

现在讨论新型RTMM算法的工作机理，我们将其称为边缘化粒子滤波器（MPF，MarginalizedParticle Filter）。

 

在较高水平时，MPF算法对多个“粒子”进行追踪，每个粒子代表路网轨迹上的位置，然后在每个轨迹上运行无迹卡尔曼滤波器。为了更准确地表达，先要来定义以下对象。

 

一种MPF状态是一组粒子。一个粒子代表车辆在地图上一个可能的路网位置，与某种概率相关。每个粒子有4种属性：

 

· 概率p∈[0,1]

· 轨迹（如地图上的一组交叉点）

· 平均向量x=[dv]’，d即车在轨迹上的位置（单位：米），v即车速（单位：米/秒）

· 2x2协方差矩阵P，代表车辆位置和速度的不确定性。

一种MPF状态是一组粒子，每个粒子都与某个分布和概率相关（左）。车辆的路网位置由轨迹和均值向量x来描述（右）。

我们每次收到来自司机手机的新观测值时，都会更新MPF状态，如下所示：

 

如果之前的MPF状态无粒子（例如，当司机刚登陆应用程序时），需要初始化一个新状态。初始化步骤仅仅是将GPS观测数据“快照”到地图上，并返回最近的道路位置。通过每个粒子到观测值的距离来计算其概率。

 

轨迹扩展步骤从当前的路网位置，找到所有可能轨迹。

在下次更新（新观测值），我们遍历状态的（非空）粒子组，并对每个粒子执行两个步骤。首先，轨迹扩展步骤根据当前的路网位置，找到所有可能轨迹。第二步，循环通过这些新轨迹，在每条轨迹上，运行UKF并更新最新创建的粒子概率。在这两个嵌套循环后，以一个新粒子组结束。为避免在MPF状态追踪过多粒子，我们简单丢弃最不可能的路径（剪枝）。

 

接着，下游团队可以决定使用最可能来自MPF状态的粒子作为地图匹配位置，或者直接利用概率输出（例如，创建一个可能的ETA分布）。

 

简言之，边缘化粒子滤波器包含了一组粒子，它们代表车辆可能的轨迹位置，并使用卡尔曼滤波算法更新每个粒子。新算法不仅提供位置，还包括速度估测和不确定性。事实上，我们已经观察到，它比HMM生成的地图匹配位置更加精确，特别是在市区和交叉路口附近，这里的错误可能会导致非常不准确的ETA。

 

图源：unsplash

在实验了该新型实时地图匹配算法后，我们发现了它对Lyft市场的积极效应。该新型模型减少了ETA误差，这意味着它能更加精确地为乘客匹配到最适合的司机。它也降低了乘客的取消次数，表明它增加了乘客对于司机能准时到来的信心。

 

但还有没做到的地方：在未来几个月里，我们计划用许多方法来改进该模型。整合来自其他手机传感器的数据，如陀螺仪，能让我们探测到司机何时转弯。我们还计划将司机的目的地作为优先考虑项（如果他们有目的地的话，例如在接乘客的路上）。

 

事实上，边缘化粒子滤波器还具有另一优点，它允许我们按原则轻松地将这些新类型信息添加到模型中，这是一个很好的基础，在此之上，我们能继续为乘客和司机提供极致的Lyft体验。

 

一起分享AI学习与发展的干货

欢迎关注全平台AI垂类自媒体 “读芯术”

（添加小编微信：dxsxbb，加入读者圈，一起讨论最新鲜的人工智能科技哦～）