汽车驾驶自动化分级（GB/T40429-2021）–无人驾驶汽车路径规划

–获得《汽车驾驶自动化分类》（GB/T 40429-2021）–

自主车辆路径规划是指在给定无人驾驶车辆的起点和目标点的情况下，基于一定的环境模型，规划出一条没有碰撞且安全到达目标点的有效路径。

路径规划主要包括两个步骤：建立包括障碍区和自由区的环境地图，在环境地图中选择合适的路径搜索算法，实时快速搜索出可行驶的路径。路径规划结果对车辆的导航起到一定的作用。它引导车辆从当前位置到目标位置。

环境地图表示法

根据表示方式的不同，环境图表示方法主要分为度量图表示、拓扑图表示等。

度量地图符号

度量地图表示使用坐标系中的网格是否被障碍物占据的方法来描述环境特征，分为几何表示和空间分解。

几何表示利用包括点、线和多边形在内的几何元素来表示环境信息。与其他环境图表示相比，几何特征图更加紧凑，有利于位置估计和目标识别；缺点是环境几何特征提取困难。几何特征图适用于在已知环境的室内环境中提取一些简单的几何特征，但在室外环境中很难提取几何特征。常用的几何图有Voronoi图、概率路线图等。

几何表示

停车场Voronoi图

空间分解法是将环境分解成网格状的局部单元，根据是否被障碍物占据来描述状态。如果网格单元被障碍物占据启发式搜索算法解决8数码问题，则为障碍网格；否则，它是一个自由网格。空间分解法通常采用均匀分解法和基于网格大小的分层分解法。均匀分解法中的网格大小是均匀分布的，占用的网格用数值表示。均匀分解法可以快速直观地融合传感器信息；然而，均匀分解方法使用相同大小的网格，导致大规模环境下路径规划的存储空间巨大，计算复杂度高。

均匀分解法

四叉树分解

统一网格地图是度量地图路径规划中最常用的。它将环境分解为一系列离散的网格节点。所有网格节点大小一致，分布均匀。网格以值占用的方式表示障碍物信息。例如，使用最简单的二进制表示方法，1表示障碍物网格，不可通过；0 表示自由网格。

当环境信息用统一的网格图表示时，只有网格节点之间建立了一定的连接关系，才能保证从起点到目标点的有效路径。

八种连接方式

拓扑图表示

拓扑图模型选择节点来表示道路上的特定位置，并使用节点之间的关系来表示道路之间的连接。这种地图表示方法具有结构简单、存储方便、全局相干性好、规划效率高、鲁棒性强等特点，适用于大范围环境下的道路规划，但包含的信息较少，需要使用其他传感器进一步描述道路环境。

路径规划算法

目前的路径规划方法大致分为以下几种：

路径规划

比较常用的路径规划算法是基于采样的路径规划算法和基于搜索的路径规划算法。

基于采样的路径规划算法

基于采样的路径规划算法已经在车辆路径规划中使用了很长时间。比较常见的基于抽样的规划算法包括概率路线图（PRM）和快速探索随机树（Rapidly-exploring Random Tree，RRT）。

概率图算法在规划空间中随机选择N个节点，然后将每个节点连接起来，并去掉与障碍物接触的连接线，从而得到一条可行路径。显然，当采样点太少或分布不合理时，PRM算法是不完备的，但可以增加采样点使算法完备，所以PRM是概率完备但不是最优的。

PRM 算法

快速随机扩展树最初主要用于解决具有运动学约束的路径规划问题。由于 RRT 采用随机抽样来确定状态空间中的扩展节点，因此无需预处理，搜索速度快。因此，该算法作为一种快速搜索算法被广泛应用于路径规划问题。

RRT算法

基于搜索的路径规划算法

基于搜索的路径规划算法通过搜索表示环境信息的环境图得到最终路径。比较有代表性的算法是 Dijkstra 算法和 A 算法。

Dijkstra 算法是典型的广度优先搜索算法。它是一种按路径长度递增的顺序生成最短路径的方法，是求解最短路径的经典算法之一。Dijkstra 算法是一种贪心算法，它在每一步都选择一个局部最优解来产生最优解。这也导致了算法的高时间复杂度。当图规模较大时，算法计算速度较慢，难以满足路径规划的实时性要求。

A* 算法是一种经典的启发式搜索算法，是从 Dijkstra 算法改进而来的。其最显着的特点是在搜索过程中加入了启发式函数，通过给定的启发式函数减少搜索节点启发式搜索算法解决8数码问题，从而提高路径搜索效率。研究表明，A*算法得到的路径能够同时满足实时性和最优性的要求。

真实的环境远比这复杂。良好的规划必须建立对周围环境的深刻理解。此外，还需要建立大量的数学方程，还需要考虑障碍物、车道线、路径曲率、曲率变化率以及车速、加速度等。受多种因素影响。