1.背景

近年来，高德汽车业务从导车到人车共导，从车机版高德地图发展到车机版高德地图SDK，再到车厂深度定制项目多条业务线并存，虽然以各种不同形态面向用户，但不变的是对高质量车载导航服务的追求。

从车载导航来看，人、车、路三者缺一不可，截至2022年末全国公路总里程535.48万公里（交通部数据），在如此数量庞大的道路网上保障导航体验质量一直是高德汽车业务探索的方向之一。以往为了测试不同道路场景的导航功能，我们的测试同学需要反复将车行驶上路，进行路测。随着车厂项目越来越多，作为地图服务供应商，路测成本越来越高，为此我们开发了模拟导航功能，能够在端上模拟各个路线的规划和导航，省去了大量路测成本。

2021年高德在业内率先发布车道级导航，车辆导航精度进入亚米级。原先的模拟导航是基于标准地图信号构建，精度在5-10米。车道级导航对信号精度要求更高，模拟导航测试手段无法满足车道级场景的精度要求。另一方面，车道级导航下，需要面临各种复杂问题测试场景：如多层高架叠加渲染、车辆变道行为引导等。原有的模拟导航方案亦无法完成这类场景构建与测试。

综上，本文介绍了高德汽车工程团队如何通过一种仿真手段来解决上述车道级导航场景构建与还原的问题。

2.问题定义

在描述具体方案之前，先介绍一下我们拥有的已知条件和期望的目标产出，即问题的输入和输出。

2.1 输入

车道级数据

车道级导航依赖高精度定位信号，而车道级数据天然包含了这些信息，关键在于我们如何利用好这些数据。

车道级信号回放

车道级信号回放是开发车道级导航时建设的一个车道级传感器信号回放功能，该功能将车道级传感器相关数据记录至一份信号文件，并可在端上独立进行信号回放，还原整个车道级导航过程。这项能力通常用于车厂客户采集路测信号后，反馈给内部进行问题的场景还原与离线分析。

2.2 输出

根据上面的车道级回放模型，我们很自然地联想到，如果构造出一套仿真模拟方案，能够从车道级数据中尽可能还原出接近真实车驾场景的车道级信号，那就可以达到自定义还原车道级导航场景的能力。

同时，我们希望该方案能够满足以下车道级导航测试需求：

能够以最少的路线成本覆盖全国高快和城市普通路车道级路网；
能够自定义构造车道级导航场景；
能够自定义模拟车道级驾驶行为。

3.还原仿真方案

在车道级数据中首先考虑的是行驶路线的静态场景元素，即先考虑行驶过程中相对路面静止的元素，确保路线经过的道路场景元素满足要求。

其次，确定行驶路线后，再考虑仿真驾驶过程中可能出现的动态场景元素或行为，如加减速、车辆变道等操作。

因此，我们计划通过构建道路场景策略引擎和车辆行为仿真引擎来分别完成这两项任务，大图如下。

道路场景策略引擎：该引擎明确路线要经过的路段或执行的任务，并生产出对应的道路段数据。例如：城市道路覆盖或经过指定道路的场景测试。
车辆行为仿真引擎：该引擎负责明确车道级行驶过程中的车辆行为。例如：做出变道、变速等行为的控制。通过周边信息数据协议，可以根据跟随策略算法模拟出周边车辆的数量和行为（如拥堵、加塞等）。

4.道路场景策略引擎

在车道级数据中，路网被分割成一段一段的小道路段，每个段包含各自的道路属性，如道路类型、长度等。通过段与段之间的连通关系建立起一张完整的道路网。正如大多数路线规划算法一样，用图算法解决路线规划类问题是常见的手段，可以根据期望道路属性筛选出合适的道路段并构造出路线。

但是，对于一个大型城市动辄数万公里的城市普通道路网来说，其背后的道路段可能达到数十万个。如何用最低的路线成本覆盖所有城市道路网成为首要问题。这是一个典型的NP问题，需要合理考虑已经走过的路线，否则会导致重复率暴增。常见的图算法如欧拉算法、哈密尔顿算法都无法适用于充满环状图的城市道路网。下面重点介绍我们用于城市道路覆盖的蚁群算法。

4.1 基于蚁群算法的城市道路覆盖策略

很多人可能会联想到用时下流行的深度学习算法让AI完成探路覆盖的过程。其实在深度学习出现之前，就已经有一批活跃的“AI算法”。如同深度学习借鉴神经元理念，早期的人工智能算法中大部分都是受大自然启发。其中有一个分支领域叫做群体智能（Swarm Intelligence），源于对以蚂蚁、蜜蜂等为代表的社会性昆虫的群体行为的研究。

蚁群算法灵感来源于蚂蚁在寻找食物过程中发现路径的行为，是一种模拟进化算法。蚂蚁在寻找食物时会在经过的路线上留下信息素，供其它蚂蚁做出决策，而大量的蚂蚁搜索行为为路径带来了全局最优解，因此蚁群算法又称为蚁群优化算法(Ant Colony Optimization Algorithms，以下简称ACO)。

ACO中会为每只蚂蚁计算得分，得分排名靠前的蚂蚁有资格参与道路信息素的权重更新。信息素计算的关键因子取决于每只蚂蚁自身走过的道路长度倒数，即，其中是蚂蚁k走过的路线长度，是权重道路长度的权重因子，通常为固定常数。可见路线越短，信息素权重越大。这也符合蚂蚁觅食的自然规则。

在我们改进后的蚁群覆盖算法中，某只蚂蚁k的信息素关键因子计算公式如下：

其中：

是蚂蚁k走出的路径长度，是参与信息素更新的蚂蚁路径中的最大值。即走过越长路径的蚂蚁获得到信息权重越大。
是蚂蚁k的路线中未走过节点的数量，可以认为是这条道路的新鲜程度（Fresh）。是参与信息素更新的蚂蚁路径中走过最多未访问节点的数量（或长度）。即走过越多未访问道路的蚂蚁其信息素权重越大。
是控制上述两个权重的因子，即分别决定道路长度和道路新鲜程度的权重。有一个很好的指标可以用在这个因子上：覆盖率。

当前期覆盖率低时，尽可能用长的道路覆盖更多节点。因此道路长度L具有更大权重，而此时每条道路的新鲜程度都基本接近100%，新鲜程度权重不用太高。
当后期覆盖率高时，尽可能奖励访问未走过节点的路线。此时道路长度不再是主要因素，新鲜度越高的道路具有更大权重，从而进一步提高覆盖率。

应用上述算法后，能以较低的路线成本覆盖城市94%以上道路。相比模拟导航，具备了更加可靠的道路覆盖测试策略。

5.车辆行为仿真引擎

在确定了路线要经过的道路段后，下一步需要计算车辆精确驾驶行为和行驶轨迹。这时问题也从道路段进一步细分到车道层面。我们首要解决的是变道算法，其次是在变道决策后的车道轨迹上完成车辆行驶轨迹的仿真模拟。

5.1 基于最短路径的变道策略算法

如同道路在车道级数据中被分割成道路段一样，每条道路段也被进一步分割成数个并列的车道。

如上图所示，道路被分割成ID1到ID4四个道路段，前三个路段各包含三个机动车道，最后一个ID4路段仅有一个转向车道。在道路段中我们需要选择合适车道来进入下一个（及其后续的）转向道路段或者经过指定的测试车道。这里利用常见的最短路径算法解决变道策略问题。算法如下：

1.首先，将每个ID的每个车道认为是图中的一个节点；

2.其次，将当前ID的每个车道i与下一个ID的每个车道j做链接，每个链接权重计为损耗用以下公式计算：

3.最后，应用Dijkstra最短路径算法，计算出从当前车道到最终目标车道的最短权重路径。

其中：、

分别是下一个ID对应的车道号。以上图的ID1第一个车道11到ID2的各车道为例：

a.ID1第一个车道11-->ID2的第一个车道21在同一个车道，所以损耗为1;

b.ID1第一个车道11-->ID2的第二个车道22不在同一个车道，所以损耗为abs(2-1)=1;

c.同理ID1第一个车道11-->ID2的第三个车道23不在同一个车道，所以损耗为abs(3-1)=2;

以此类推，算出ID1出发路线中所有车道间的权重，如下图。

如上图所示，按照最短路径算法，可以得到11到41车道的合理变道路线（绿色数字权重）。实际算法中会加入对车道长度的考虑，让变道发生在尽可能长的路段上，符合人们的驾驶直觉，避免紧急变道。如果需要指定经过某车道，只需要将该路段的其余车道节点删除即可实现。同时，算法稍加修改即可实现车辆靠左、靠右行驶的驾驶行为习惯。

应用变道算法后，我们可以从车道级数据中得到各个车道的中心定位轨迹点，如下图。

为了拟合出接近真实的车辆行驶轨迹，我们还需要把这些车道轨迹做如下处理:

变道轨迹平滑拼接；
车速控制模拟。

对于第一点，我们应用了三次贝塞尔曲线算法，很容易得到如下的平滑轨迹点。

对于第二点，要加入车速控制需要我们拟合出更贴合人类驾驶行为习惯的算法。下面就重点介绍基于区间路形的动态车速模拟算法。

5.2 基于区间路形的动态车速模拟算法

我们打算从真实的驾驶行为出发来模拟车速轨迹。根据美国国家公路交通安全管理局的官方调查资料显示：驾驶员对紧急情况的典型响应时间为1.5秒。这1.5秒包含了3/4秒反应时间+3/4秒踩下刹车制动的时间。进一步推测，驾驶员对非紧急制动场景的响应和预判可能更宽松一些，同时考虑到我们模拟的车速一般都在90km/h左右，我们选取响应时间为2秒。

驾驶员的反应源自于对前方路况形态的判断。简单的说就是：直线加速踩油门，过弯减速踩刹车。但具体来说，对于路况要以多少时速通过，很大一部分来源于驾驶员的目测视觉感知。因此，对于真实驾驶行为的模拟，我划分成两个路段来处理：反应区间和测速区间。