自动驾驶能否识别障碍物的能力与环境感知同等重要，如何安全有效的规划行驶路线，是自动驾驶汽车需解决的最大的难题之一。事实上，路径规划技术，现阶段是一个非常活跃的研究领域。路径规划之所以如此复杂，是因为其涵盖了自动驾驶的所有技术领域，从最基础的制动器，到感知周围环境的传感器，再到定位及预测模型等等。准确的路径规划，要求汽车要理解我们所处的位置以及周边的物体（其他车辆、行人、动物等）会在接下来的几秒钟内采取什么样的行为。
首先来说一下三个名词：路径规划、避障规划、轨迹规划
路径规划通常指全局的路径规划，也可以叫全局导航规划，从出发点到目标点之间的纯几何路径规划，无关时间序列，无关车辆动力学。
避障规划又叫局部路径规划，又可叫动态路径规划，也可以叫即时导航规划。主要是探测障碍物，并对障碍物的移动轨迹跟踪（MovingObjectDetectionandTracking，一般缩写为MODAT）做出下一步可能位置的推算，最终绘制出一幅包含现存碰撞风险和潜在碰撞风险的障碍物地图，这个潜在的风险提示是毫秒级，未来需要进一步提高，这对传感器、算法的效率和处理器的运算能力都是极大的挑战，避障规划不仅考虑空间还考虑时间序列，在复杂的市区运算量惊人，可能超过30TFLOPS，这是无人车难度最高的环节。未来还要加入V2X地图，避障规划会更复杂，加入V2X地图，基本可确保无人车不会发生任何形式的主动碰撞。
轨迹规划则源自机器人研究，通常是说机械臂的路径规划。在无人车领域，轨迹规划的定义感觉不统一。有人将避障规划与轨迹规划混淆了。轨迹规划应该是在路径规划和避障规划的基础上，考虑时间序列和车辆动力学对车辆运行轨迹的规划，主要是车纵向加速度和车横向角速度的设定。将设定交给执行系统，转向、油门、刹车。如果有主动悬挂，那么轨迹规划可能还要考虑地形因素。
三大规划是无人车最复杂的部分，算法多不胜数，让人眼花缭乱，这也是百度、谷歌和苹果科技巨头要切入无人车领域的主要原因，这些科技巨头最擅长的就是算法的优化整合。当然传统车厂如福特和丰田，拥有对车辆动力学的绝对优势，在此领域实力并不比科技巨头要差，尤其是丰田，从开源SLAM到KITTI，软件实力丝毫不次于谷歌。
对于全局型路径规划不算复杂，前提是有拓扑级地图，这对地图厂家来说很容易的。对于非地图厂家是有点麻烦的，不过只能算小麻烦。
今天我们重点了解一下避障规划，避障规划的前提是对周围环境有深刻的理解，有一个非常完善实时的环境理解。
在此之前不得不先要理解无人驾驶避障的含义，很明显我们根据无人驾驶避障的过程，可以将无人驾驶避障分成三个方面：
1.运动障碍物检测：对运动过程中环境中的运动障碍物进行检测,主要由车载环境感知系统完成。
2.运动障碍物碰撞轨迹预测：对运动过程中可能遇到的障碍物进行可能性评级与预测,判断与无人驾驶车辆的碰撞关系。（当你检测到障碍物后，你就得让机器判断是否会与汽车相撞）
3.运动障碍物避障：通过智能决策和路径规划,使无人驾驶车辆安全避障,由车辆路径决策系统执行。（判断了可能会与汽车发生碰撞的障碍物后，你就得去让机器做出决策来避障了）
运动障碍物检测方法
运动障碍物检测根据他们的sensor主要分成两类：
一种是基于激光雷达和毫米波雷达的
一种是基于立体视觉的
运动障碍物碰撞轨迹预测
这一部分与障碍物的检测识别分不开的。无人车的感知系统需要实时识别和追踪多个运动目标（Multi-ObjectTracking，MOT），例如车辆和行人。
物体识别是计算机视觉的核心问题之一，最近几年由于深度学习的革命性发展，计算机视觉领域大量使用CNN，物体识别的准确率和速度得到了很大提升，但总的来说物体识别算法的输出一般是有噪音的：物体的识别有可能不稳定，物体可能被遮挡，可能有短暂误识别等。自然地，MOT问题中流行的Tracking-by-detection方法就要解决这样一个难点：如何基于有噪音的识别结果获得鲁棒的物体运动轨迹。
运动障碍物的避障本质上它是一个路径规划的过程：在路段上有未知障碍物的情况下,按照一定的评价标准,寻找一条从起始状态到目标状态的无碰撞路径。
预测
预测模块的作用是对感知所探测到的物体进行行为预测，并且将预测的结果具体化为时间空间维度的轨迹传递给下游模块：行为决策模块。然后行为决策模块结合路由寻径模块从而进行行为决策。
这些选择就是结合高精地图的全局规划，然后再通过汽车周边传感器感知的信息进行局部规划，从而判断汽车是否右转、直行or并道。
路径规划
先简单理解一下自动驾驶汽车的功能层，因为路径规划需要自动驾驶汽车不同功能层之间的合作、协调。
动作控制层：负责控制汽车，使其尽可能的按照“设定的”轨迹形式。该层需要最快的反应速度；
传感器融合层：负责合并个传感器的输出（如雷达和激光雷达）
定位层：负责尽可能准确的在地图上定位车辆的位置，并计算其他物体相对于车辆的位置
预测层：负责识别传感器检测到的物体的性质(又名感知)，并根据汽车当前的轨迹、其他车辆的轨迹和场景中的各种元素(如交通灯)预测场景中近未来的变化。这个层的一个重要任务是预测冲突。
行为层：该层的主要作用是协调。根据底层的输入信息来决定如何调整行车轨迹
轨迹层：负责计算既定条件（速度、距离、车道、jerk等等）下的行车轨迹
对于不同的环境，我们创造了环境模型，再加上路径搜索就构成了路径规划。通常，环境模型有三大类，分别是栅格法、可视图法、自由空间法。路径搜索算法就多了，Dijkstra、Floyd-Warshall、A+算法、层次法、动作行为法、势场域法、栅格法、模糊逻辑法、拓扑法、惩罚函数法、遗传算法、模拟退火法、蚁群法和神经网络法等。大多数算法都是诞生于六十年代。
对于环境建模来说，栅格法是公认最成熟的算法，栅格法应该也是安全系数最高的算法，也是最耗运算资源的算法。不过无人车要考虑安全，安全是第一位，成本是第二位，同时有英伟达和英特尔这样的半导体巨人在不断提高运算性能，运算资源不用过多考虑。
栅格法与激光雷达很搭
可视图法和自由空间法和栅格法相比的优点是比较灵活，对运算资源消耗少。缺点很明显，障碍物多少与算法复杂程度成正比，算法太复杂时可靠性就降低，同时不太适合动态环境，要求运动速度变化尽量小。栅格法的缺点是如果分辨率高，对运算资源和内存需求较高。显然，可视图法和自由空间发适合机器人，栅格法更适合无人车，这在业内差不多已经是定论。这和传感器也有部分关系，视觉系统难以适应太精细的格栅法，因为视觉系统的要做精细的定量边界分割是不可能的，而激光雷达非常适合栅格法。
Dijkstra（迪杰斯特拉）——最短路算法的经典算法
路径算法的种类如此之多，可以看出他一直是一个热门话题，也采用了许多技术。这些路径规划方法大致可以分为三种：
1.基于图搜索的规划器
2.基于采样的方法
3.内插曲线规划器
在基于图形搜索的规划器的范围内，Dijkstra算法是一种基于图形搜索的算法，给定一个起点，使用Dijkstra算法可以得到起点到其它所有节点的最短路径。Dijkstra算法要求图(Graph)中所有边的权重都为非负值，只有保证了这个条件才能该算法的适用性和正确性。
在《自动驾驶路径规划-GraphBased的BFS最短路径规划》中介绍，将地图抽象为Graph的数据结构，然后利用Graph广度优先遍历算法(Breadth-FirstSearch,BFS)解决无权重的High-Level的地图级别的规划。但是实际应用场景中，地图中各个路径所代表的Graph的边的权重都是不同的，比如距离长的Edge权重就应该比较低；交通拥堵的Edge权重就应该低等等。对于有权重的Graph如何进行最短路径规划呢，Dijkstra算法可以解决这个问题。
它的基本思路是：
考虑一个图，该图由两部分组成：节点和连接结点的边。其中每条边还被指定了一个数值，表示从该边的一个端点移动到另一端点的代价，通常指距离。
让我们把图中的开始节点称为初始节点。让节点Y的距离是从初始节点到Y的距离。Dijkstra的算法将分配一些初始距离值，并尝试逐步改进。
1.为每个节点分配一个暂时的距离值：为我们的初始节点设置为零，对所有其他节点设置为无穷大。
2.将初始节点设置为当前节点。标记所有其他节点为未访问节点，创建一组称为未访问集的未访问节点。
3.对于当前节点，考虑其所有邻居并计算其临时距离。将新计算的临时距离与当前分配的值进行比较，并分配较小的值。例如，如果当前节点A的距离为6，并且与邻居B连接的边的长度为2，则到B（途径A）的距离将为6+2=8，如果B先前标记的距离大于8，然后将其更改为8。否则，保持当前值。
4.当我们完成考虑当前节点的所有邻居时，将当前节点标记为已访问，并将其从未访问集中移除，以后将不会再次检查被访问的节点。
5.如果目标节点已被标记为访问（在两个特定节点之间规划路由时），或者未访问集合中的节点之间的最小暂定距离都是无穷远（当完整遍历时；当初始节点和剩余的未访问节点之间没有连接时），算法结束。
6.否则，选择标有最小暂定距离的未访问节点，将其设置为新的“当前节点”，然后返回到步骤3。
作为运动规划领域最著名的算法之一，Dijkstra算法可以解决带权重有向图的最短路径规划问题，在实际的路径规划中也有大规模的实际应用。但是Dijkstra算法的搜索没有方向性，会有大量冗余的搜索操作。我们可以给Dijkstra加上一些启发性的信息，引导搜索算法快速的搜索到目标，这就是A*算法。由于加入引导信息，A*算法在大多数情况下会比Dijkstra算法要快。
对于移动机器人来说，轨迹生成问题主要研究如何生成一系列动作，使得机器人由初始状态到达目标状态。对于无人车来说，其初始状态包括其二维坐标(x,y)、航向角ψ以及曲率κ。
实际情况远比这复杂，还需要建立大量的数学方程。良好的规划必须建立对周边环境，尤其是动态环境的深刻理解。
参考资料：
1.智车科技：自动驾驶之——避障方法研究
2.智车科技：自动驾驶核心技术之路径规划
3.算法集锦之路径规划算法：Dijkstra算法
4.自动驾驶基础（十八)--路径规划
5.自动驾驶高速路上的路径规划算法