a*算法求最短路径,找最短路径的方法

转载来源： https://new.QQ.com/rain/a/2020 10 12 a0hd 5200

几种常用车辆路径规划算法2020

10/12

21:55

大鱼窝

企鹅号

共享

评论

0

根据车辆导航系统的研究历史，车辆路径规划算法分为静态路径规划算法和动态路径算法。 静态路径规划是以物理地理信息和交通规则等条件为约束来寻求最短路径的，静态路径规划算法正在成熟，比较简单，但很少适用于实际交通状况。 动态路径规划是在静态路径规划的基础上，结合实时交通信息，及时调整预先规划的最佳行驶路线，到达目的地最终得到最佳路径。 介绍几种常用的车辆路径规划算法。

1. Dijkstra算法

Dijkstra(Dijkstra )算法是最短路算法的典型算法之一，1959年由E.W.Dijkstra提出。 该算法适用于计算道路权重均为非负的最短路径问题，可以给出图中从一个节点到所有其他节点的最短路径，思路清晰，搜索准确，长度较长。 与此相对，由于输入是大型的稀疏矩阵，所以存在需要时间、占用空间大的缺点。 该算法的复杂度为o(n )，n为节点的个数。

2. Lee算法

Lee算法最先用于印刷电路和集成电路的路径跟踪，与Dijkstra算法相比更适合数据随时变化的道路路径规划，其执行成本小于Dijkstra算法。 只要存在最佳路径，该算法就能找到最佳优化路径。 Lee算法的复杂性很难表达，多层路径规划需要很大的空间。

3 .流动算法

Floyd算法是Floyd在1962年提出的，是计算图中任意两点之间最短距离的算法。 可以正确处理有向图和负权重的最短路径问题，也用于计算有向图的传递闭包。 流转向搜索算法的时间复杂度为o(n )，空间复杂度为o )，n为节点数。 虽然为每个节点创建一次Dijkstra算法的时间复杂性相同，但实际运算效果优于Dijkstra算法。

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

启发式搜索有：局部偏好搜索法、最优优先级搜索法、A*算法等多种算法。 其中，A*算法最早由Hart、Nilsson、Raphael等人提出，算法通过引入评价函数来提高搜索速度，提高局部偏好算法的搜索精度，应用广泛，是目前最为流行的短路*算法比Dijkstra算法消耗更少的存储容量。 其时间复杂度为o(BD )，b为节点的平均出次数，d为从起点到终点的最短路搜索深度。

5 .双向搜索算法

双向搜索算法是Dantzig提出的基本思想，Nicholson正式提出了算法。 该算法在从起点寻找最短路径的同时从终点向前进行路径搜索，但最有效的是两者在中间点汇合，可以缩短搜索时间。 然而，如果终止规则不合适，该算法很可能将搜索时间增加一倍，即两个方向都很可能被搜索到最后并终止。

6 .蚁群算法

蚁群算法由意大利学者M.Dorigo于1991年提出，是一种随机搜索算法，是在自然界蚁群群体行为研究基础上总结的优化算法，鲁棒性强，也容易与其他方法结合

另外，还有实时启发式搜索算法、基于层次网络的搜索算法、神经网络、遗传算法、模糊理论等，根据实际需求的不同，对算法的要求和侧重点也不同，因此这些算法由于许多算法在用于求解车辆路径规划问题时存在一定的缺陷，目前的研究重点是利用多种算法的融合构建混合算法。

关键决策算法的利弊

从上面的内容可以看出，决策算法面临的最大挑战是如何达到自动驾驶所需的极高的安全性和可靠性。 自动驾驶决策的结果输出到控制器，根据ISO26262现有的功能安全规定，相反决策系统也需要达到ASIL-D标准。 目前，ISO组织正在制定专门针对自动驾驶的功能安全标准，虽然新标准可能会加以考虑，但功能安全的基本原则仍然有效。

自动驾驶处理的场景极其复杂，必须考虑所有已知和未知的极端情况，以及适应各个国家和地区的交通状况。 目前，识别和决策算法部分也有一些技术路线，但最重要的是深度学习和增强学习(Reinforcement Learning )，这是alpha go使用的方法。 但这些算法路线不是万金油，各有明显的优缺点。

端到端深度学习算法具有危险性

深度学习适合大数据时代，很多训练都很容易调整可用算法，因此专门针对复杂场景。 但深度学习受到质疑的一点是，该算法是端到端(输入数据、输出结果)决策系统，无法描述计算过程，即不透明，无法调试错误。

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

专家系统基于诸如地图、交通规则等独立知识库来生成条件IF )

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

理性决策是必然趋势

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

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

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

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

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

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

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

总结

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