几种常见的车辆路径规划算法

根据车辆导航系统的研究历程 , 车辆路径规划算法可分为静态路径规划算法和动态路径算法。静态路径规划是以物理地理信息和交通规则等条件为约束来寻求最短路径，静态路径规划算法已日趋成熟 , 相对比较简单 , 但对于实际的交通状况来说 , 其应用意义不大。动态路径规划是在静态路径规划的基础上 , 结合实时的交通信息对预先规划好的最优行车路线进行适时的调整直至到达目的地最终得到最优路径。下面介绍几种常见的车辆路径规划算法。

1. Dijkstra 算法

Dijkstra（迪杰斯特拉）算法是最短路算法的经典算法之一，由 E.W.Dijkstra 在 1959 年提出的。该算法适于计算道路权值均为非负的最短路径问题，可以给出图中某一节点到其他所有节点的最短路径，以思路清晰，搜索准确见长。相对的，由于输入为大型稀疏矩阵，又具有耗时长，占用空间大的缺点。其算法复杂度为 O ( n ² ) ，n 为节点个数。

2. Lee 算法

Lee 算法最早用于印刷电路和集成电路的路径追踪，与 Dijkstra 算法相比更适合用于数据随时变化的道路路径规划，而且其运行代价要小于 Dijkstra 算法。只要最佳路径存在，该算法就能够找到最佳优化路径。Lee 算法的复杂度很难表示，而且对于多图层的路径规划则需要很大的空间。

3. Floyd 算法

Floyd 算法是由 Floyd 于 1962 年提出的，是一种计算图中任意两点间的最短距离的算法。可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包，Floyd-Warshall 算法的时间复杂度为 O ( n ³ ) ，空间复杂度为 O ( n ² ) ，n 为节点个数。与对每一节点作一次 Dijkstra 算法的时间复杂度相同，但是实际的运算效果比 Dijkstra 算法要好。

4. 启发式搜索算法—— A* 算法

启发式搜索有很多的算法，如 : 局部择优搜索法、最好优先搜索法、A* 算法等。其中 A* 算法是由 Hart、Nilsson、Raphael 等人首先提出的，算法通过引入估价函数，加快了搜索速度，提高了局部择优算法搜索的精度，从而得到广泛的应用，是当前较为流行的最短路算法。A* 算法所占用的存储空间少于 Dijkstra 算法。其时间复杂度为 O ( bd ) ，b 为节点的平均出度数，d 为从起点到终点的最短路的搜索深度。

5. 双向搜索算法

双向搜索算法由 Dantzig 提出的基本思想，Nicholson 正式提出算法。该算法在从起点开始寻找最短路径的同时也从终点开始向前进行路径搜索，最佳效果是二者在中间点汇合，这样可缩短搜索时间。但是如果终止规则不合适，该算法极有可能使搜索时间增加 1 倍，即两个方向都搜索到最后才终止。

6. 蚁群算法

蚁群算法是由意大利学者 M.Dorigo 等于 1991 年提出的，它是一种随机搜索算法 , 是在对大自然中蚁群集体行为的研究基础上总结归纳出的一种优化算法，具有较强的鲁棒性，而且易于与其他方法相结合，蚁群算法的复杂度要优于 Dijkstra 算法。

此外 , 还有实时启发式搜索算法、基于分层路网的搜索算法、神经网络、遗传算法及模糊理论等，由于实际需求不同对算法的要求和侧重点也会有所不用，所以也出现了许多以上算法的各种改进算法。大多数算法应用于求解车辆路径规划问题时都会存在一定的缺陷，所以目前的研究侧重于利用多种算法融合来构造混合算法。

主流决策算法的利弊相随

从上部分的内容我们不难发现，决策算法面临的最大挑战，就是如何达到自动驾驶所需要的极高的安全性和可靠性。自动驾驶决策的结果会输出到控制器，根据 ISO26262 已有的功能安全的规定，这会反过来要求决策系统也需要达到 ASIL-D 的标准。目前，ISO 组织专门针对自动驾驶的功能安全标准还在制定中，有可能会用一种新的标准进行考量，但功能安全的基本原则依然有效。

由于自动驾驶所要处理的场景极其复杂，必须考虑已知和未知的所有极端情况，以及适应各个国家和地区的交通状况。目前在识别和决策算法部分也有多条技术路线，最主要的是深度学习（Deep Learning）加增强学习（Reinforcement Learning），也就是 AlphaGo 使用的方法。不过这些算法路线并非万金油，各自都有自己明显的优缺点。

△端到端的深度学习算法有隐患

深度学习适合大数据时代，只要大量训练就比较容易调校出可用的算法，因此专门用来处理复杂场景。不过深度学习受到质疑的点在于，它的算法是端到端（输入数据，输出结果）的决策系统，计算过程不能被解释，即没有透明度，无法 debug。

△基于规则的专家系统不灵活

专家系统（Expert System）是基于独立知识库（如地图、交通规则），让条件 IF（输入）产生出相应的动作或结论 THEN（输出）的系统；还可以用 AND、OR、NOT 运算来复合输入、输出。但专家系统的缺点在于：一、采访 " 专家 " 来建模所需时间过长，成本过高；第二，知识库可能有错误，多条规则可能出现矛盾，从而造就脆弱系统。所以，这种方法不能单独用于构建自动驾驶的决策算法。

因此，我们需要在自动驾驶领域引入新的决策机制。自动驾驶决策技术路线的一个重大趋势，就是从相关推理到因果推理。

理性决策是必然趋势

上世纪 80 年代初，Judea Pearl 为代表的学术界出现了一种新的思路：从基于规则的系统转变为贝叶斯网络。贝叶斯网络是一个概率推理系统，贝叶斯网络在数据处理方面，针对事件发生的概率以及事件可信度分析上具有良好的分类效果。它具有两个决定性的优势：模块化和透明性。

图灵奖得主、贝叶斯之父朱迪亚 · 珀尔（Judea Pearl）

模块化的优势非常重要。我们可以把深度学习的系统作为一个子模块融入到其中，专家系统可以是另一个子模块，也融入其中，这意味着我们有了多重的冗余路径选择，这种冗余构成了贝叶斯网络的子节点，将有效强化输出结果的可靠性，避免一些低级错误的发生。

透明性是贝叶斯网络的另一个主要优势。对于自动驾驶而言，这尤为关键，因为你可以对整个决策的过程进行分析，了解出错的哪一个部分。可以说贝叶斯网络是理性决策的极佳实现，适合用于设计整个决策的顶层框架。

因果推理的另一个典型范例就是基于增强学习的决策框架，它把一个决策问题看作是一个决策系统跟它所处环境的一个博弈，这个系统需要连续做决策，就像开车一样。优化的是长期总的收益，而不是眼前收益。这有点像巴菲特的价值投资，优化的目标不是明天的收益，而是明年或者十年以后的长期总收益。

谷歌把这样的框架用在下围棋上，取得了革命性的成功。自动驾驶的场景也非常适合应用这样的决策系统。比如说要构建价值网络，评估当前的驾驶环境风险，评估的是从现在时间到未来时间的整体风险；然后利用策略网络输出本车的控制决策，选择最优的驾驶路径和动力学输出。

同时，我们还可以构建一个基于模拟路况的仿真环境，通过增强学习去做虚拟运行，获得最优的决策模型，并且还将产生大量的模拟数据，这对决策算法的成熟至关重要。可以说，向因果推理型决策模型转化是自动驾驶技术迈向成熟的重大标志。

总结

在训练和测试自动驾驶汽车决策能力的过程中，其实收集到的绝大部分数据都是正常路况下的行车数据，极端情况极其罕见。深度学习加增强学习的算法只能无限趋近于处理所有场景，贝叶斯网络的因果推理逻辑可以在一定程度上处理未知的极端情况。决策层的不同技术路线也各有优缺点，可能包括深度学习、增强学习、专家系统、贝叶斯网络在内的多种方法融合，将是下一步的主流方案。