『3D视觉工坊』自动驾驶综述|定位、感知、规划常见算法汇总( 七 ) 作者：TomHardyDate：2020-05-05来源：

三、决策模块在本节中，我们将对文献中所报道的自动驾驶汽车决策系统的相关技术进行研究，包括路线规划、行为选择、运动规划和控制子系统。
1、RoutePlanning路线规划子系统负责计算从自驾车的初始位置到用户操作员定义的最终位置之间通过道路网络的路线。如果用一个加权有向图来表示道路网，其边权表示通过一个路段的代价，那么计算一条路线的问题就可以归结为在加权有向图中寻找最短路径的问题。然而，对于大型道路网络，经典的最短路径算法，如Dijkstra和A*的复杂度是不切实际的。在过去的十年中，道路网络中的路线规划算法的性能有了显著的进步。新开发的算法可以在毫秒或更短的时间内计算出行驶方向。道路网中的路径规划方法在查询时间、预处理时间、空间利用率和对输入变化的鲁棒性等方面提供了不同的权衡。它们主要可分为四类：goal-directed,separator-based,hierarchical,bounded-hop,andcombinations 。
(1)Goal-DirectedTechniques目标导向技术通过避免扫描不在目标顶点方向上的顶点来引导从源顶点到目标顶点的搜索。 A*是一种经典的目标导向最短路径算法。与Dijkstra算法相比，该算法在每个顶点上使用一个较低的距离函数，从而使更接近目标的顶点更早地被扫描，从而获得更好的性能。 ALT（A*、地标和三角形不等式）算法通过选取一小组顶点作为地标来增强A* 。在预处理阶段，计算所有地标和所有顶点之间的距离。在查询阶段，利用包含地标的三角形不等式估计任意顶点的有效下界距离。查询性能和正确性取决于是否明智地选择顶点作为标记。另一个目标定向算法是ArcFlags 。在预处理阶段，图被划分成具有少量边界顶点和平衡（即类似）顶点的单元。通过从每个边界顶点向后生长最短路径树，为树的所有弧（或边）设置第i个标志，计算单元i的弧标志。在查询阶段，该算法将修剪没有为包含目标顶点的单元格设置标志的边。 arcflags方法具有较高的预处理时间，但在目标定向技术中查询时间最快。
(2)Separator-BasedTechniques基于分隔符的技术基于顶点或边分隔符。顶点（或边）分隔符是顶点（或边）的一个小子集，其移除将图分解为几个平衡的单元。基于顶点分隔符的算法使用顶点分隔符来计算覆盖图。快捷边将添加到覆盖图中，以便保留与完整图的任何顶点对之间的距离。覆盖图比完整图小得多，用于加速查询算法。 HPML（HighPerformancemultivelRouting ，高性能多级路由）算法是这种方法的一个变种，它显著减少了查询时间，但代价是增加了空间使用量和预处理时间，在不同的级别上为图添加了更多的快捷方式。
基于弧分隔符的算法使用边界分隔符将图分解为平衡的单元，试图最小化连接不同单元边界顶点的切割边数。快捷方式将添加到覆盖图中，以保持每个单元内边界顶点之间的距离。 CRP（CustomizableRoutePlanning ，可定制路线规划）算法DEL15是为满足现实道路网络的需求而设计的，例如处理转弯成本和执行成本函数的快速更新。它的预处理有两个阶段。第一阶段计算多层分区和覆盖的拓扑。第二阶段通过自下而上和并行处理单元来计算团边的代价。查询作为覆盖图中的双向搜索进行处理。
(3)HierarchicalTechniques层次技术利用了道路网络固有的层次结构，其中主要道路（如公路）组成一个小的干线子网。一旦源顶点和目标顶点距离较远，查询算法只扫描子网的顶点。预处理阶段根据实际的最短路径结构计算顶点或边的重要性。 CH（compressionHierarchies）算法是一种分层技术，它实现了创建快捷方式以跳过重要性较低的顶点的思想。它重复执行顶点压缩操作，如果图中最短路径唯一且包含要压缩的顶点，则从图中删除最不重要的顶点并在每对相邻顶点之间创建快捷方式。 CH是通用的，因此可以作为其他点到点算法和扩展查询的构建块。 REACH算法是一种分层技术，在预处理阶段计算顶点的中心度度量（REACH值），并在查询阶段使用它们来修剪基于Dijkstra的双向搜索。设P是从源顶点s到包含顶点v的目标顶点t的最短路径。 v相对于P的到达值是r（v ， P）=min{距离（s ， v），距离（v ， t）} 。