自DARPA挑战赛以来，自动驾驶的规划算法大量涌现，但是依据其特征，大体可以分为两个方向，第一个派别是采样一派，这个采样派讲究采样的有效性、离散度，是否能增加算法的相对完备性，根据这个采样的不同，又有随机性采样和确定性采样，其实采样的目的，就是为了提高搜索效率，但是与此同时也使算法的完备性丢失。本文对各种采样方式也梳理了一下，甭管什么采样方式，总之都是为了生成有效轨迹，然后这个轨迹生成的算法，又有很多派别，比如直接派和解耦派，最优化派和最优控制派等等，但这不是本文的重点，我们下一篇文章更新轨迹生成算法的解说。第二个派别是最优化一派，最优化一派如果做的是路径优化，就离散x，优化y；如果做的是轨迹优化，即[x,y,t]，就离散t，去优化[x,y]，建立凸目标函数，建立凸可行域，KIT，汉阳大学，Berkeley分别发了好几篇文章，并且也搭建有实验平台来说明最优化的有效性，但是关于最优化这一派，本文也不讲，留到下下篇文章再专门说。

一个运动规划算法，各位大佬先先后后不厌其烦地开发了这么多种类，是吃饱了撑的吗？当然不是！要知道，这个世界上没有最好的算法，只有最适合的算法，适合自己的才是最好的，妄想一招吃遍天下那是不可能的。高速场景，低速场景，自动泊车场景，复杂动态的非结构化道路场景，交通参与者密集场景等等，目前想用一种算法覆盖所有情景有点困难，也许将来end to end类的算法可以处理这个问题吧。

1 随机性采样

顾名思义，随机采样就是用随机函数生成的位置坐标，并用碰撞检测算法去除有碰撞风险的采样点。

1.1 PRM

1.2 RRT家族

随机采样在自动驾驶里面，用的车辆平台并不是很多，早期MIT用过，而且可以玩的花样并不多，如今在特定的空间里面进行确定性采样并用代价函数来评价的规划算法已经盖过了随机采样算法的风头。所以呢，因为随机采样的性能并不如下面要说的，并且也比较简单，在此不多介绍。

2 确定性采样

确定性采样说白了就是人为地设置某种采样规则来进行采样，比如在行车道里面可以沿着道路中心线的法向量采样，采样点的航向角、曲率和道路中心线的切向量有关。

2.1 控制空间采样

控制空间采样说白了，就是基于车辆的运动学模型，已知了车辆位姿、速度和横摆角速度，然后根据车辆的性能约束在速度和角速度空间里面均匀采样然后前向模拟，然后程序给这些轨迹打分。所以一般可以提前构造离线的采样轨迹，等程序运行时调用即可。在十几年前计算机的计算性能跟不上的时候，这个算法还是比较流行的。

2.2 状态空间采样[2]

后来呢，因为控制空间采样难以对环境约束有较好地处理，很多采样是无效的，并且离散度问题和相对完备性问题不好处理，所以状态空间采样开始流行起来。状态空间采样和控制空间大体相似，不过它不是在速度空间里面采样，而是均匀采样目标点，采样目标点后，也就成了两点边值问题，为了从起点到达目标点，我们需要求逆解。那么大家怎么求逆解呢，我们知道求逆解是一个有点复杂的问题，各位大佬提出了很多算法，常见的贝塞尔曲线，回旋曲线，以及近年来大火的MPC等等。求出了单条轨迹后，再均匀采样目标点，那么也就有了多条轨迹，接下来用代价函数选择一个最优的就行了。

两个采样方式，一个是求逆解，一个求顺解。

2.3 state lattice采样[3]

lattice采样也比较简单，就是根据前面的状态空间采样，无限向前连接，也就相当于把连续的构型空间给离散化了成为lattice空间，然后再基于图搜索算法，对于这种带权有向无环图，使用动态规划。

参考文献

[1] Leonard J, How J, Teller S, et al. A perception-driven autonomous urban vehicle[J]. Journal of Field Robotics, 2008, 25(10):727-774.

[2] Howard T M, Green C J, Kelly A, et al. State space sampling of feasible motions for high‐performance mobile robot navigation in complex environments[J]. Journal of Field Robotics, 2008, 25(6-7):325-345.

[3] Knepper R A, Kelly A. High Performance State Lattice Planning Using Heuristic Look-Up Tables[C]// IEEE/RSJ International Conference on Intelligent Robots & Systems. 2007.

[4] Sc A E D, Arem B V, Amditis A, et al. 智能车辆手册[M]. 2012.