自动驾驶车辆的系统架构

1.5.2交通标志检测和识别

交通标志检测和识别涉及检测环境中的交通标志的位置并识别它们的类别（如，限速、停止信号和普通让行）。

早些时候，大多数用于交通标志检测和识别的方法都是基于模型的并使用了简单的特征（如，颜色、形状和边缘）来检测识别的。后来，基于学习的方法（如SVM，级联分类器和LogitBoost）开始利用其简单的功能，但演变为更复杂的功能（如，模式、外观和模板）。然而，这些方法通常不能很好地概括，并且这些方法通常需要对几个超参数进行微调。此外，一些方法可能由于数据的缺乏，仅用于识别而不用于检测。只有在大型数据库可用之后（如，众所周知的德国交通标志识别（GTSRB）和检测（GTSDB）基准数据，数据分别为51,839和900帧），基于学习的方法最终可以显示出算法的能力。尽管其中有一些方法只能够应对更少的例子。随着更大型数据库的发布（如超过20,000帧的STSD，6,610帧的LISA，用于检测的25,634帧和用于分类的7,125帧的BTS，以及10万帧数据的清华-腾讯100K）,相比于基于模型的方法，基于学习的方法得到了改进，并取得了更好的结果。上述一些数据集的帧数包括仅具有背景的帧。随着一般计算机视觉任务中深度学习的兴起，卷积神经网络是交通标志检测和识别中最先进技术（SOTA）。深度学习方法已经分别在GTSRB和和BTS的识别任务中实现了高达99.71％和98.86％的F1得分。

1.5.3路面标记检测和识别

路面标记检测和识别涉及检测路面标记的位置并识别其类型（如，车道标记、道路标记、消息和人行横道）。大多数研究一次只处理一种类型的路面标记，而不是同时处理所有类型的路面标记。一个重要的路面标记是道路中的车道定义。早些时候，大多数用于车道标记检测的方法都是基于模型或学习的。形状和颜色是最常见的特征：直线和曲线（例如，抛物线和样条）是最常见的车道表示。深度学习是另一种最近流行的流行方法，像这样的方法已经显示出非常好的结果。一种使用两个横向安装的向下摄像机和将横向距离估计建模为分类问题，并且通过使用CNN来完成任务。

许多用于车道标记检测的方法也被尝试用于道路标记检测。它们通常使用几何和光度特征。此外，用于道路标记检测和识别的各种方法使用了逆透视映射（IPM）来减少了透视效果，以此让问题更容易解决并提高结果的准确性。最近，几种方法采用最大稳定极值区域（MSER）来检测感兴趣区域（即可能包含道路标记的区域）和用卷积网络来识别道路标记。一种基于IPM、MSER和DBSCAN的算法的融合来执行道路标记的检测以及PCANet（一种简单的图像分类的深度学习基线）与SVM或线性回归的组合以进行分类。

在道路标记的背景下，道路消息通常是单独处理的。一些用于道路消息检测和识别的方法将不同的消息视为不同的类别（即，算法首先检测场景中消息的位置，然后识别它们的类别），而大多数方法使用基于OCR的方法识别字母。

在道路标记的环境中，人行横道仍经常被单独检测。大多数人行横道检测方法利用人行横道通常呈现的规则形状和黑白图案来进行识别。因此，在许多实际应用中，这项任务不进行，因为强大的行人检测算法的支持。

决策与规划系统

无人驾驶汽车行为决策系统指无人车通过传感器感知得到交通环境信息，考虑周边环境、动静态障碍物、车辆汇入以及让行规则等，与无人驾驶库中的经验知识等进行匹配，进而选择适合当前交通环境之下的驾驶行为。

行为决策的目标主要是保证车辆可以像人类一样产生安全的驾驶行为，满足车辆安全性能、遵守交通法规等原则。该部分包括路线规划、运动规划和控制三个子系统。

2.1路线规划

路线规划子系统负责计算从自动驾驶汽车的初始位置到用户操作员定义的最终位置的通过道路网络的路线。

道路网络中的路线规划方法在查询时间、预处理时间、空间使用和对输入变化的鲁棒性等方面提供了不同的权衡。它们主要可分为四类：基于目标导向的、基于分隔符、基于分层技术的、有界跳跃和多种算法组合。

2.1.1基于目标导向

基于目标导向的路线规划通过避免扫描不在目标点方向上的顶点来引导从起点到目标点的搜索。

(1)ALT（A*+landmark+triangle inequality）算法:

使用A∗ 结合基于界标和三角形不等式的新图论下界技术进行搜索。通过选取一组顶点作为界标来增强A*。在预处理阶段，计算所有地标和所有顶点之间的距离。在查询阶段，使用涉及界标的三角形不等式来估计任意顶点的有效下界距离。搜索的性能和正确性取决于界标选择的正确性。如下图为ALT算法与其他算法的对比，下图32主要是Dijkstra算法，加入曼哈顿下限的A∗算法和ALT算法的对比（Dijkstra算法访问的顶点（左），A∗ 在同一输入上使用曼哈顿下限（中间）和ALT算法（右侧）进行搜索）。

图32  Dijkstra搜索算法

(2)Arc Flag算法:

Arc Flag算法通过对路网中每条边附加额外的指示信息减少搜索的范围,提升最短路径查询速度。设置导航信息时,如果将图中每个点都作为目的点进行预处理,则在标记指示信息时占用太大内存,需对图的数据进行划分,以更大范围地表示目的地,减少预处理消耗。Arc-flags算法主要分为2部分：①预处理阶段的图划分和设置标志位算法，该算法为路网数据中每条边设置导航信息，即标志位；②在线查询算法,使用改造的 Dijkstra算法提供在线查询服务。2.1.2分割法分割法是基于顶点或边缘分隔符的。顶点（或边缘）的分隔是顶点（或边）的一部分，这些定点（或边）的移除可以将图分解为若干平衡单元。基于顶点分隔符的算法使用顶点的分隔来计算叠加图。将“捷径”方式边缘添加到叠加图中，以保留完整图形中任何一对顶点之间的距离。叠加图比完整的图小，多用于加速查询算法。

(1)HPML算法（High-Performance Multilevel Routing，高性能多级路由）

HPML（High Performance multivel Routing，高性能多级路由）算法是分割法的一个变种，它显著减少了查询时间，但代价是增加了空间使用量和预处理时间，在不同的级别上为图添加了更多的快捷方式。

该方法基于输入图的分层分解和包含附加信息的辅助图的计算。在联机阶段，使用这些预先计算的数据可以减少搜索空间，从而缩短查询时间。该方法最大限度地开发了预处理：其的新变体外包了计算到预处理阶段的最短路径所需的几乎所有工作。因此，它最适合于查询时间非常宝贵但预处理时间较长（以及大量预计算数据）的环境

(2)CRP算法（可定制路线规划算法）

该算法的主要创新点为区分网络的拓扑性质和度量性质。拓扑是网络的图形结构，以及每个路段或转弯的一组静态属性，例如物理长度、车道数、道路类别、速度限制、单向或双向以及转弯类型。该度量生成了穿越路段或转弯的实际成本。它通常可以简洁地描述为一个函数，将电弧/转弯的静态特性映射（在恒定时间内）为成本。例如，在所用时间度量中（假设自由流动的交通），弧的成本可以是其长度除以其速度限制。该算法假设拓扑由度量共享，很少改变，而度量可能经常改变，甚至可能是用户特定的。该算法具有三个阶段的现实路线规划算法。,第一个独立于度量的预处理可能相对较慢，因为它很少运行。它只将图形拓扑作为输入，并可能产生相当数量的辅助数据（与输入大小相当）。第二个阶段，即度量定制，针对每个度量运行一次，并且必须更快（几秒钟），并且只生成少量数据（原始图的一部分）。最后，查询阶段使用前两个阶段的输出，并且对于实时应用程序必须足够快。该算法适用于具有任意度量的实时应用程序，包括分层方法失败的应用程序。CRP可以快速地处理新的度量，并且度量特定的信息足够小，可以同时将多个度量保存在内存中。该方法通过重新审视和彻底重新设计已知的加速技术，并将它们与图形划分的最新进展相结合来实现这一点。2.1.3基于层次化的方法层次化方法利用道路网络的固有层次结构，其中诸如高速公路的主要道路复合了小的动脉子网络。一旦源顶点和目标顶点相距很远，查询算法仅扫描子网的顶点。预处理阶段根据实际的最短路径结构计算顶点或边的重要性。

(1)CH算法(Contraction Hierarchies algorithm)

CH算法是一种优化的加速方法，可以利用代表道路网络的图的特性。通过在预处理阶段创建“shortcuts”来实现提速，然后在最短路径查询中使用这些“shortcuts”来跳过“不重要的”顶点。这是基于对道路网络高度分层的观察。与一些通向小区内部路的路口相比，某些路口（例如高速公路路口）在层次结构中“更重要”并且在层次上更高。“shortcuts”可用于保存两个重要路口之间预先计算的距离，从而算法无需在查询时考虑这些路口之间的完整路径。CH不知道人类认为哪条道路“很重要”，但是它能够使用启发式方法计算出顶点的重要性。(2)REACH算法：REACH算法是一种层次化的方法，在预处理阶段，首先计算顶点的中心度量（到达值），并在查询阶段使用这个度量来修剪基于Dijkstra的双向搜索。设P是从源顶点s到包含顶点v的目标顶点t的最短路径。v相对于P的距离是r(v,P)= min { distance(s,v)，distance(v,t)}。2.1.4基于有界跳跃（bounded-hop 法）bounded-hop 的方法是通过向图形添加虚拟shortcuts来预先计算顶点对之间的距离。由于所有顶点对之间的预计算的距离对于大型网络而言是不允许的，因此bounded-hop 方法旨在获得具有非常少的跳跃的任一的一条虚拟路径的长度。(1)HL算法（Hub Labeling）它在预处理阶段计算图形的每个顶点u的标签L(u)，其主要由u的一组中心顶点和它们的距离组成。选择这些标签使得它们遵守覆盖属性：对于任何顶点对(s,t)，标记L(s)和L(t)的交集必须包含从s到t的最短路径的至少一个顶点。在查询阶段期间，通过评估标记L(s)和L(t)的交集中存在的中心点之间的距离，可以在线性时间内确定距离(s,t）。HL在道路网络查询方法是最快的，但代价是空间占用率高。(2)HL-∞算法（Customizable Route Planning algorithm）HL-∞算法则利用了集线器标签和顶点排序之间的关系，并开发了预处理算法来计算产生小标签的排序。顶点排序的迭代范围优化算法使HL-∞算法的查询时间比HL快两倍。它以一些顶点排序（例如，由CH给出的）开始并且在给定数量的迭代步骤中进行，每个迭代步骤按重要性的降序重新排序不同范围的顶点。(3)HLC算法（Hub Label Compression）HLC算法通过组合出现在多个标签中的常见子结构，以更高的查询时间为代价：将空间使用减少一个数量级。(4)TNR算法（Transit Node Routing）它使用顶点子集上的距离表示。在预处理阶段，它选择一组顶点作为传输节点，并计算它们之间的所有成对距离。从传输节点，对于每个顶点u，它可以计算一组访问节点。如果存在来自u的最短路径使得v是其中的第一个传输节点，则传输节点v是u的接入节点。它还计算每个顶点与其访问节点之间的距离。选择传输节点集的一种自然方法是选择弧分隔符的顶点分隔符或边界顶点作为传输节点。在查询阶段，距离表用于选择从源顶点s到目标顶点t的路径，该路径最小化组合距离s-a(s)-a(t)-t，其中a(s)和a(t)是接入节点。如果最短路径不包含传输节点，则执行本地查询（通常为CH）。2.1.5多种算法组合可以将各个方法进行组形成不同图形属性的混合算法。以上各种技术方法进行组合可形成不同图形属性的混合算法。REAL算法结合了REACH和ALT。ReachFlags算法是结合了REACH和Arc Flags边标记法）。SHARC算法将shortcut的计算与多级的Arc Flags（边标记法）相结合。CHASE算法将CH与Arc Flags相结合。TNR + AF算法结合了TNR和Arc Flags（边标记法）。PHAST算法可以将若干技术进行组合，以便通过利用多核CPU和GPU的并行性进行加速。2.2运动规划

运动规划子系统负责计算从自动驾驶汽车的当前状态到由行为选择子系统定义的下一个局部目标状态的路径或轨迹。运动计划执行局部驾驶行为，满足汽车的运动学和动力学约束，为乘客提供舒适度，并避免与环境中的静态和移动障碍物发生碰撞。

运动计划可以是路径或轨迹。路径是汽车状态的序列，并没有定义汽车状态如何随时间演变。该任务可以委托给其他子系统（例如，行为选择子系统），或者速度分布可以定义为曲率和接近障碍物的函数。而轨迹是一条指定汽车状态随时间演变的路径。

2.2.1路径规划

路径规划涉及生成从汽车当前状态到下一目标状态的一系列状态，这并不定义汽车状态随时间的演变。路径规划通常分为全局路径规划和局部路径规划。在全局路径规划中，在汽车开始移动之前，使用环境的离线全局地图计算全局路径。在局部路径规划中，当汽车移动时，使用周围环境的在线局部地图生成局部路径，这允许汽车处理移动障碍物。路径规划方法主要可分为两类：基于图搜索的方法和基于插值曲线的方法。

2.2.1.1基于图搜索的方法：

（1）Dijkstra算法是通过找到图的初始节点和目标节点之间的最短路径。Dijkstra算法通过重复检查最近尚未检查的节点，将其邻点添加到要检查的节点集，并在达到目标节点时停止。Dijkstra算法适用于全局路径规划。然而，由于检查的节点数量很多，它在大面积地区的计算成本很高，并且有时候结果不连续。

（2）A*算法是Dijkstra的扩展，其主要通过基于对目标节点的启发式估计成本向节点分配权重来执行快速图搜索。然而，这种算法找到解决方案并不容易。一种局部路径规划方法，该方法将A*算法与两种不同的启发式成本函数相结合，即（RTR）度量和Voronoi。其中第一个考虑了汽车的运动学约束，而第二个考虑了障碍物的形状和位置的常识。

2.2.1.2基于插值曲线的方法基于曲线插值的方法是通过使用插值处理。该方法通过插值处理：在已知的点集内插入新的点集。方法采用之前已知的一组点（如，描述路线图的航点）并生成描绘更平滑路径的新点集。用于自动驾驶汽车的路径规划的最常用曲线插值的方法是样条曲线。样条曲线是以子间隔划分为分段多项式参数曲线，这些曲线可以将其定义为多项式曲线。每个子段之间的连接称为结（或控制点），其通常具有高度平滑约束。这种曲线具有较低的计算成本，因为其行为是由结来定义的。然而，这种方法的结果可能不是最优的，因为它更侧重于实现部件之间的连续性而不是满足道路的约束，并且它取决于全局航路点。（1）一种实时路径规划算法，该算法为静态避障的越野自动驾驶提供了最优路径。所提出的规划算法基于一组预定义的航路点来计算路径。预定义的路线点提供曲线坐标系的基础框架，以生成用于自动驾驶车辆路径规划的路径候选。将每个候选对象转换为笛卡尔坐标系，并使用障碍物数据进行评估。为了选择最优路径，通过考虑路径安全成本、路径平滑度和路径一致性来确定每条路径的优先级。

（2）在该方法中，首先从一组预定义的路线点构建中心线，这些路线点通常是从车道级的地图中获得的。通过弧长和到中心线的偏移确定。然后，所有这些候选都被转换为笛卡尔坐标。考虑静态安全性、舒适性和动态安全性的总成本，选择最优路径；同时，还确定了最佳路径的适当加速度和速度。设计了各种类型的道路，包括具有静态和移动障碍物的单车道道路和多车道道路，以测试所提出的方法。该方法的流程图如下图33所示.

图33  基于曲线插值的规划方法