导读
地图软件现在已成为人们出行必备的重要辅助工具。为了实现准确的导航，首先必须准确确定人或车的当前位置。因此，定位技术就是实现导航功能的基石。
本文较系统的介绍了手机、车机导航定位中使用的关键技术，以及高德地图在这些关键技术中的进展。最后，讨论了在传统导航向自动驾驶的演进过程中，定位技术的演进路径。
1.导航定位框架
导航定位的核心业务目标是为导航服务提供连续可靠的定位依据，包括：当前在哪条路上，是否偏离路线，距离下一个路口有多远，等等。
为实现这一目标，首先需要接收定位信号输入。最常见的定位信号是GPS，其可以提供全域米级精度（5~10m）的位置信息。在此基础上，大部分手机同时配置了惯性传感器（陀螺仪、加速度计）和磁力计，还有部分手机配置了气压计，可以感知高程方向的位置变化。
对于车机，通过CAN总线获取的车速脉冲、方向盘转角等信息是另一类重要的定位输入。基于上述定位信号，应用姿态融合、航位推算等算法，计算出连续可靠的位置和姿态。再依据地图数据将人/车的实际位置与地图道路关联，实时判断当前是否已经偏离导航路线，或更新当前在导航路线中的相对位置。
图1 导航定位框架
在上述定位框架中，针对不同端的形态（手机/车机），输入定位信号的配置不同，使用的定位技术及覆盖的定位场景也不同。
对于手机，存在步行、骑行、驾车等多种使用场景，需要对用户行为进行识别。在步行场景下，由于速度较低，GPS方向不准确，手机姿态通过融合惯导和磁力计计算实现。在驾车场景下，位置和姿态主要由GPS提供，针对GPS跳跃、漂移等复杂情况设计可靠的地图匹配算法是手机定位重点要解决的问题。
对于车机，只存在驾车使用场景。同时，由于车机具备稳定的安装状态并可以提供更丰富的车辆CAN总线信息，基于这些信息设计航位推算及融合算法，解决隧道、高架、平行路等复杂场景的连续定位问题是车机定位的重点。
2.手机导航定位
2.1.姿态融合技术
常用的姿态融合技术又称为AHRS（Attitude and heading reference system ）。对于六轴惯性传感器融合，包含陀螺仪和加速度计，其AHRS算法如下图所示。陀螺仪测量的是角速度，角速度积分即可得到某一时间段内的角度变化。加速度计测量的是物体的加速度，包含重力加速度，当静止时，通过获得重力加速度在三个轴上的分量可以计算相对倾斜角度。AHRS算法采用滤波方法，如互补滤波、Kalman滤波，对不同传感器姿态进行融合。
图2 AHRS融合算法
对于九轴传感器，额外提供了三个轴向的磁力计方向，同样利用上面的算法框架进行融合。
2.2.地图匹配技术
传统的地图匹配方法是在定位点附近道路中，根据距离、方向接近等一些判断准则找到最可能是汽车行驶道路的匹配道路。这种方法实现简单，但通常GPS定位误差是十米，在信号干扰、遮挡的情况下可以达到几十米甚至上百米，而地图测绘误差、地图简化误差同样可以达到十几到几十米。在各种误差条件下，单纯依靠距离、方向这样的几何特征判断做策略匹配是很不稳定的。
对于一个好的地图匹配算法，为了稳定准确的确定匹配道路，需要综合利用定位源和地图的各种输入数据，做融合计算，并根据汽车行驶的特点对各种特殊场景做处理。对于多源信息融合，隐马尔可夫（HMM）是一个比较常用并且有效的方法，因此我们采用HMM作为匹配算法的核心，并辅以场景策略算法，实现地图匹配。
在HMM地图匹配算法中，匹配道路是未知的，作为隐藏变量zn。每个时刻观测到的GPS定位信息是观测变量xn。地图匹配的目标是在已知定位信息的情况下对匹配道路进行估计：
对上述问题，可以采用维特比算法用递推的方法进行计算。
在HMM框架下建立地图匹配模型，核心在于确定发射概率模型和转移概率模型。发射概率模型的确定依据定位位置和方向。
1）对定位位置，与道路距离越接近概率越大，反之概率越小。同时考虑匹配道路的选择对横向距离误差较敏感，对纵向距离误差不敏感。采用正态分布建立模型。
2）对定位方向，与道路方向越接近概率越大，反之概率越小。同时概率与速度有关，速度越大越可信。采用Von Mises分布，以速度为超参数建立模型。
图3 位置发射概率 图4 方向发射概率
转移概率模型的确定依据道路距离、道路转角对汽车行驶的约束建立。
道路转弯的角度越大，速度较大的概率越低。采用Von Mises分布，以速度为超参数建立模型。根据车速和时间差计算移动距离，该距离和路径移动距离越接近，概率越大。采用指数分布建立模型。
图5 速度转移概率 图6 移动距离转移概率
上述算法在高德地图手机APP上实现了落地，为驾车导航提供准确的定位匹配结果，用于导航的引导播报等功能。对比原来使用策略的地图匹配方法，HMM算法在匹配准确率和稳定性上都有显著提升。
3.车机导航定位
3.1.车机定位方案
对于车机导航，如何充分利用车辆传感器和总线信息，优化驾车导航各种复杂场景体验是定位要解决的核心问题。其中，复杂场景包括：隧道、地下停车场定位失效，城市峡谷区域定位漂移等。
解决上述痛点问题的关键在于多传感器融合技术。例如，当GPS漂移或失效时，利用车速脉冲与惯导融合的航位推算技术进行持续定位，但航位推算会产生累计误差，需要地图数据进行反馈矫正，同时地图数据和GPS又可以对惯导参数进行标定，提升航位推算精度。
在实际车机导航项目中，传感器配置不同，又会衍生出不同的定位方案，如下表所示。
其中，纯GNSS方案无法使用任何传感器融合手段，定位效果最差。前端融合方案实现了惯导和车速的前置融合，可以满足部分GPS失效场景的持续定位，但由于累积误差的影响，提升有限。车辆模型方案和后端融合方案都实现了传感器、GPS与地图数据的完整融合，因此定位效果更好，其中车辆模型方案使用车辆CAN总线的传感器数据，而后端融合使用车机安装的惯导传感器，在对传感器选型及安装使用方式进行精细适配之后，可获得最佳的定位效果。
3.2.传感器融合技术
以后端融合为例，传感器融合算法框架如下。
图7 传感器融合算法框架
融合算法有两个目的：第一，将不同技术的导航信息融合成唯一导航信息，使之可靠性高于未融合前的；第二，估计器件误差（陀螺仪零偏、测速仪尺度误差等）。
融合算法基于Kalman滤波实现，其关键在于模型建立和模型参数设置。Kalman滤波模型由状态转移方程和观测方程构成。状态转移方程表示相邻导航状态之间的转移关系，它通过构建导航误差微分方程实现；模型参数是指状态转移噪声和观测噪声，观测噪声的设置与GPS质量评估模块相关。经Kalman滤波处理后，得到导航误差的最优估计。
实现了完整信息融合的传感器融合技术可以在使用低成本传感器条件下达到甚至超过高成本专业惯导设备的定位效果。
下图展示了采用后端融合方案的车机导航定位效果。图中蓝色是GPS位置，红色是高精度基准设备的定位轨迹，绿色是车机导航定位轨迹。可以看到，在GPS被遮挡的停车场，或GPS被干扰的区域，车机导航定位始终可以持续稳定的输出高精度的定位位置，保证了车载导航功能的可靠运行。
图8 停车场定位效果 图9 信号干扰区定位效果
4.高精定位演进
传统的导航定位仅需要解决道路级的定位问题，对定位精度的要求不高。但随着辅助驾驶、自动驾驶等越来越多的应用场景出现，对定位精度的要求也不断提高，如下图。
图10 高精定位演进
对于车道级导航，定位需要能分辨出汽车当前所在的车道，这就要求定位精度达到米甚至亚米级，而对于更先进的智能驾驶应用，为保证安全，需要定位精度达到厘米级。
为达到更高精度的定位能力，需要对现有的定位手段进行升级。一种升级的方法是，对现有的定位输入源直接升级，如普通GPS升级为更高精度的RTK-GPS，低成本MEMS惯导升级为高精度惯导，这样可以在基本不改变原有算法框架的基础上直接获得高精度的定位能力。但缺点是，原有算法的缺陷，如长时间GPS丢失场景的累积误差问题依然存在，且成本较高。另一种方法是引入新的定位源，如激光雷达、毫米波雷达、摄像头等。这就需要针对这些新的传感器开发新的融合定位算法。不同的高精定位方案对比如下表。
上面方案中，高德与千寻合作开发了基于千寻RTK服务的高精定位解决方案“知途”，实际道路评测在高速及普通道路场景下的定位精度可达到10cm以内。该方案不依赖于其他任何传感器或地图数据，具有全域高精度的特点，可作为独立的高精度定位解决方案。
图11 “知途”高精定位样机
在基于环境特征匹配的相对定位方案中，激光雷达方案是较成熟可靠的，也是自动驾驶早期原型阶段最普遍采用的定位方案。但受制于激光雷达的成本和可靠性问题，量产落地仍存在风险。基于视觉的相对定位方案成本更低，同时受益于近年来视觉算法和计算芯片领域突飞猛进的发展，在当前的量产自动驾驶中已经逐渐成为主流的定位方案。基于高德自身的图像及定位能力建设，将在三个业务方向上进行高精定位的业务实践。
1）面向L3自动驾驶的系统级定位：基于外部输入的视觉语义信息（如Mobileye发送的车道线形状、类型等），与高精地图数据（HD Map）匹配，并结合GPS/RTK和IMU等其他定位源，实时计算车道级高精定位结果，并驱动高精数据播发引擎（EHP）发送高精数据，为自动驾驶功能提供定位及数据服务。
2）车道级导航定位：基于自研的视觉算法和云端图像定位能力，实现全域覆盖的车道级定位能力，驱动传统道路级导航向车道级导航升级。
3）用于高精数据众包采集的软硬一体化高精定位：基于自研的低成本视觉+RTK+IMU硬件，实现基于vSlam技术的高精度绝对定位，为高精数据的采集、重建，并最终快速更新迭代提供支撑。
小结
传统导航定位采用10m精度的GPS定位为基础，针对手机/车机不同端，考虑他们独特的运动特征及输入信号配置，设计传感器融合算法、行为判断算法、地图匹配算法，最终满足导航对于全场景道路级定位的精度要求。未来面向半自动、全自动驾驶应用，要求定位精度向车道级甚至厘米级演进，这需要在考虑实际落地场景的基础上进行传感器和算法迭代，这是下一阶段定位技术演进的重要方向。
