这是一篇2015年的老论文了，但其中提到的很多技术至今仍在使用，在这里做一个简单的梳理。文章主要对用于自动驾驶的运动规划技术进行了梳理。
在讲解具体的算法之前，有必要对自动驾驶的规划控制整体有一个了解。
规划控制的整体流程如图所示，我们用一个例子来解释上图。假设你现在准备进行一次从北京到上海的自驾游。首先你会打开地图软件，设置起点，终点，这样你就得到了一条从北京到上海的路径，这条路径会包含你应该上那条高架、走那个高速等信息。这个过程就是Route Planning。Route Planning的任务是从地图上找到一条到达目的地的可行路径。接下了，你开车沿着Route Planning给的路径出发了，现在，前方出现了一个行人，这时你要决定是绕行，还是停车等待，这个过程就是Behavior Planner或者说叫决策，真实的路况是复杂的，你需要知道什么时候躲避行人，什么变道，什么时候超车，Behavior Planner解决的就是这个问题。躲过行人之后，你准备变道超车了，这时，你要怎么变道，是往左还是往右，是猛打方向盘迅速变道还是慢慢的变过去？这个过程就是运动规划，也叫局部规划。当年决定从左边变道时，你需要控制油门和方向盘来完成变道，这就是Motion Control。车辆根据油门的大小和方向盘的转动角度给车施加加速度和转动角度，这就是最后的Vehicle Control。
这篇文章的重点是Motion Planning。在这里我们不讨论端到端的Motion Planning。传统的Motion Planning由以下两部分组成
Path Finding的主要任务是找到可行性的路径，确保路径是上是没有障碍物的，且满足车辆的动力学约束。Trajectory Optimization（轨迹优化）的主要任务是对找到的路径，再次进行优化。在实际驾驶场景中，我们希望打方向盘的角度相对较小，这样乘客的体验比较好，这就要求轨迹尽可能的平滑。总的来说Path Finding的任务是找到能走的路，轨迹优化的任务是找到好走的路。
了解了这些之后，我们再来看这篇论文。论文总体上来说分为：背景介绍、研究挑战、运动规划技术、未来研究方向和研究团队。在这篇博客中，我主要对运动规划技术进行一个简单的梳理，简单讲解每种方法在整个规划过程中的位置。
论文将路径规划算法分为了4类：基于图搜索、基于采样、基于插值、和基于数值优化。前两种用于path Finding，后两种方法用于轨迹优化。
规划方法
根据规划的方式将路径规划算法分为基于图搜索的规划算法和基于采样的路径规划方法。基于图搜索的算法可以保证一定可以找到最短路径；而基于采样的方法则是概率完备的：经过若干次采样之后，一定可以找到一条最短路径，但这条路径并不能保证是全局最优（最短的）的。
基于图搜索的规划方法
基于图搜索的路径规划方法是建立在已经获得了地图数据的基础上的，包括全局地图（全局规划）和局部地图（局部规划）。简单来说，无人车已经根据高精地图抽象出了图结构，接下来，我们要在图结构上寻找最短路径。
代表算法：Dijkstra算法、A*算法和state Lattices
基于采样的规划方法
基于采样的规划方法一般是指PRM（概率路图）和RRT（快速搜索随机树)。下图展示的PRM的过程
PRM分为两步：1、在地图空间内进行随机采样，将相邻最近的采样点连接，得到图结构。
2、根据得到的图结构，使用Dijkstra或者A*等算法对路径进行搜索。
RRT算法则是将建图的过程和搜索的过程相结合，在采样的同时建立搜索树，当采样结束时，最短路径也就找到了。
轨迹优化方法
无人车使用上文提到的规划方法之后，就会输出一条路径，如果使用简单的A*或者RRT，得到的路径并不一定是符合车辆的运动学与动力学约束的，比如，无人车是不可能进行左右平移的。如图所示，在使用RRT算法之后，我们得到了一条通往目标点的路径，但这条路径并不平滑，存在一些拐角，这种路径后端的控制器是很难进行追踪的。考虑到车辆的运动学与动力学约束，我们可以对已有的路径进行优化，使路径平滑并且满足车辆的动力学约束。
轨迹优化的方法有2种，基于插值曲线和基于优化的方法。
基于插值的轨迹优化方法
简单来说，对于规划得到的路径，我们不直接对路径优化，我们把路径上的节点拿出来。设计一条平滑的曲线穿过所有的节点，这样就可以得到平滑的路径。根据选择的曲线的不同，可以有不同的轨迹优化方法。
基于优化的轨迹优化方法
建立运动学方程，通过最小化目标函数（速度、加速度、加加速度）来获得获得一条轨迹，这样得到的轨迹每个参数都具有实际的物理意义，比较容易进行优化，借助现有的凸优化工具包快速的对路径进行优化。
