想让自动驾驶更安全，这个问题很重要

智能车的自动驾驶行为即是将车从起始位姿“搬运”到目标位姿，车辆的运动限制在路面上、同时其运动学及动力学模型使得其不能像空中的无人机一样随意调整航向角，因此，规划的路径除了考虑路程最短、无碰撞外还需要考虑车辆运动轨迹的可执行性。

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

1. Dijkstra算法

（图6 Dijkstra算法动态图）

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

2．Lee算法

Lee算法最早用于印刷电路和集成电路的路径追踪, 与Dijkstra算法相比更适合用于数据随时变化的道路路径规划, 而且其运行代价要小于Dijkstra 算

法。只要最佳路径存在, 该算法就能够找到最佳优化路径。Lee算法的复杂度很难表示, 而且对于多图层的路径规划则需要很大的空间。

3. Floyd算法

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

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

（图7 A* 算法动态示意图）

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

5． 双向搜索算法

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

6. 蚁群算法

（图8 蚁群算法示意图）

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

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

目前, 投入市场应用的成熟车辆导航系统大多基于静态的路径规划, 然而面对存在众多不稳定因素的交通现实, 用户并不满足于现有的系统。尤其是发生交通事故和交通堵塞时, 静态路径规划不能及时改变路线。因此, 车辆导航动态路径规划就成为新一代智能车辆导航系统的研究热点问题。车辆动态路径规划基于历史的、当前的交通信息数据对未来交通流量进行预测, 并用于及时调整和更新最佳行车路线, 从而有效减少道路阻塞和交通事故。

（图9 多导航器协调规划示意图）

随着计算机科学技术、无线通信技术以及交通运输业的高速发展, 车辆导航系统的动态路径规划研究趋势还将向多导航器相互协调规划的方向发展。现在的车辆导航都是单个车辆为对象进行路径引导,而没有考虑到总体的大局协调, 这样容易引起新的交通拥塞等问题, 所以多导航器协调规划将是一种更加符合实际需求的规划方法。

[参考文献]

1、 考虑全局最优性的汽车微观动态轨迹规划

2、 车辆导航动态路径规划的研究进展

3、 Adaptive Routing for road traffic

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!