码头作为航运的起点和终点，是贸易与物流的重要枢纽。而码头水平运输堆场作业一直受人为因素影响（货运司机数量、司机疲劳驾驶、人工调度等）无法实现高效协同自动化作业。

随着人工智能，5G等技术的的成熟，实现码头生产自动化成为港口未来发展的趋势。此前华为联合天津港口打造了智能水平运输系统，实现了港口L4级的自动驾驶。

该智能水平运输系统，华为采用了全局路径规划算法，基于车辆运动学特征，可以保障单车行驶的平顺稳定，且实现IGV在路口并行转弯，是多车协同驾驶安全高效的前提。

同时，云端的动态短路径规划，解决了码头作业场景多变、任务需实时调整的难题，实现全局效率最优。

为了实现港口的L4级自动驾驶，华为可能用了哪些路径规划算法？

全局路径规划,就是在路网中，搜索到一条最优路径，以便可以到达目标地点。为了实现这一目标，目前使用最广泛的两种全局路径搜索算法：

1.Dijkstra算法

一种用于解决单源最短路径问题的图算法，该算法可以找到从给定起点到所有其他顶点的最短路径。Dijkstra算法的基本思想是通过不断更新起点到各个顶点的最短距离来逐步扩展最短路径的范围。它维护一个距离数组，记录起点到各个顶点的当前最短距离，同时使用一个集合来存储已经确定最短路径的顶点。 算法的步骤如下：

• 初始化距离数组和集合。将起点的距离设为0，其他顶点的距离设为无穷大，将所有顶点加入集合。

• 从集合中选择距离起点最近的顶点，将其标记为已确定最短路径。

• 更新与该顶点相邻顶点的距离。如果经过已确定最短路径的顶点到达相邻顶点的距离更短，则更新距离数组。

• 重复步骤2和步骤3，直到集合为空或者所有顶点都被标记为已确定最短路径。

经过该算法，可以得到起点到其他所有顶点的最短路径以及对应的距离。Dijkstra算法的时间复杂度为O(V^2)，其中V是顶点的数量。在使用优先队列等数据结构进行优化后，时间复杂度可以降低到O((V+E)logV)，其中E是边的数量。

2.A*算法

是一种基于采样搜索的粗略路径规划算法，是要在地图上找到一条从起到到终点的最短路径。该算法使用了两种评估函数来决定下一步的移动：g(n)表示起点到当前节点的实际代价，h（n）表示从当前节点到终点的预估代价。 A*算法通过计算每个节点的f(n) = g(n) + h(n)来选择下一个节点进行扩展。它使用一个优先级队列来存储待扩展的节点，并按照f(n)的值进行排序。在每次迭代中，A算法选择具有最小f(n)值的节点进行扩展。 该算法在搜索过程中维护了一个开放列表和一个关闭列表。开放列表存储待扩展的节点，关闭列表存储已经扩展过的节点。在每次迭代中，A*算法将当前节点加入关闭列表，并将其相邻的未访问节点加入开放列表。 A*算法在满足一些条件下能够保证找到最短路径。首先，评估函数h(n)必须是一致的（即满足三角不等式），这样保证了A算法不会错过最优解。其次，如果h(n)是准确的，则A*算法能够找到最短路径。 总结来说，A*算法是一种常用的启发式搜索算法，适用于解决图搜索问题，并且能够找到最短路径。 A*算法是如何搜索并找到一条既短又无障碍的路径，非常详细的算法原理分享，可以参考这篇文章：路径规划之A*算法

华为在打造L4级无人驾驶港口的时候，除了使用全局路径规划算法来实现多车协同驾驶之外，还用了局部路径规划算法来解决码头作业场景多变，任务实时调整运作的难题。

自动驾驶常用局部路径规划算法有哪些？

局部路径规划根据当前环境和目标位置，决定如何在局部区域内安全、高效地规划出一条路径。全局路径规划确定了整个形成的大致路线，而局部路径规划负责处理具体的障碍物避让和路径调整。需要借助传感器实时获得障碍物信息来响应环境变化。

运动规划的第一步往往采用随机采样算法，走一步看一步，不断更新行驶轨迹。代表算法有基于采样的方法：PRM、RRT、Lattice。这类算法通过随机采样的方式在地图上生成子节点，并与父节点相连，若连线与障碍物无碰撞风险，则扩展该子节点。重复上述步骤，不断扩展样本点，直到生成一条连接起点到终点的路径。

1.PRM算法

一种经典的采样方法，主要包含三个阶段：一是采样阶段、二是碰撞检测阶段，三是搜索阶段。

采样阶段：在地图空间进行均匀的随机采样，也就是对地图进行系数采样，将大地图简化为较少的采样点

碰撞检测阶段：剔除落在障碍物上的采样点，并将剩下的点与其一定距离范围内的点相连，同事剔除穿越障碍物的链接，从而构成一张无向图。

在搜索阶段：利用全局路径规划算法章节介绍的搜索算法（Dijkstra、A*等）在无向图中进行搜索，从而找出一条起点A到终点B之间的可行路径。

2.RRT算法

RRT算法是一种对状态空间随机采样的算法，通过对采样点进行碰撞检测，避免了对空间的精确建模带来的大计算量，能够有效地解决高维空间和复杂的约束的路径规划问题。可以轻松处理障碍物和差分约束的问题，被广泛应用于机器人路径规划。

3.Lattice算法

第一步，采集足够多的轨迹，提供尽可能多的选择；第二步计算每一条轨迹计算的cost，这个cost考虑了轨迹的可行性，安全性等因素。第三部，循环检测，在这个循环检测的过程中，每次会先挑选出cost最低的轨迹，对其进行物理限制检测和碰撞检测。如果挑出来的轨迹不能同时通过这两个检测，就将其筛除，考察下一条cost最低的轨迹。

局部路径规划算法，除了这些，还有多项式曲线、贝塞尔曲线等方法。可以参照往期分享的常用规划算法分享：自动驾驶路径规划五大常用算法

为了实现自动驾驶无人驾驶，这些常用规划算法，也是我们自动驾驶规划算法训练营重点学习的内容，如果你也想在无人驾驶领域，深研规划算法，可以加入我们的训练营学习！

本训练营详细介绍了自动驾驶系统中规划与感知、高精地图、控制等模块之间的关系、数据信息流向及数据处理，深入讲解A*、Lattice等常用规划算法原理以及双环PID、LQR等控制算法原理，系统梳理了规划、控制算法代码；同时通过实践演示、学员练习，带领学员完成路径规划、循迹行驶、借道绕障行驶等仿真场景功能代码学习与实现。

训练营通过互动直播教学、学习群答疑辅导、项目任务指导，为学习者提供灵活的学习途径、创造即时学习的良好氛围，引导学习者养成独立思考、学以致用的良好学习习惯。课程收益

• 学会开发环境配置、开发工具基本使用方法；

• 学会基于A*算法的全局路径规划及调参方法；

• 学会基于Lattice算法的局部路径规划及调参方法；

• 学会基于规划轨迹实现车辆横、纵向控制及参数调试方法；

• 能够在开发平台上实现循迹行驶、借道绕障行驶仿真功能。

课程大纲

• 自动驾驶路径规划概述

• 开发环境配置、工具链及开发平台熟悉

• 全局路径规划

• 局部路径规划

• 车辆横纵向控制

• 总结、答疑

  （详细课程目录可以联系堂主查看）

面向对象

• 希望从事自动驾驶规划算法研发岗位的在校生；

• 希望系统学习自动驾驶规划控制实际应用的在岗研发工程师；

• 自动驾驶相关产业产品经理、项目经理等；

• 希望了解自动驾驶规划与控制研发的相关人士。

咨询报名

学习形式：在线直播，

上课地点：班级群集中上课、互动答疑

联系人：汽车学堂堂主