前言：
本文将介绍特斯拉Tesla 在AI Day 上提到的决策规划模块Planner。
同人类驾驶员一样，Planner在接收到经过视觉神经网络处理过的3D Vector Space后，将会在该Space进行搜索判断，从而找到一条轨迹可以最大限度地提高汽车的安全性、舒适性和效率，将车辆规划至目的地。
作为最早布局自动驾驶的厂商，Tesla早期的Planner已经可以很好的在高速公路或者是城市快速路段进行规划，包括单车道的车道保持、导航变道、主动超车、自动上下闸道也都经受了量产的考验；随着自动驾驶的发展，Tesla Autopilot 的使用场景需要从高速扩展到城市道路。
特斯拉Autopilot要求Planner在城市街道自动驾驶中同样表现出色。在城市自动驾驶要复杂更多，决策规划中需要解决的关键问题是解空间既是非凸问题又是高维问题。
非凸问题：
非凸问题可以有多种可能的解决方案，并且它们又比较独立。但是在搜索时要获得一个全局最优解较难，Planner在搜索时很容易进入到局部最优。
高维度：
轨迹规划高维度的出现是因为汽车需要规划接下来的 10 到 15 秒，并且需要生成整个规划窗口内自车的位置、速度和加速度，这在运行时需要生成的大量参数。
解决上述问题的常用方法有两种：离散搜索方法和连续函数优化。
离散搜索方法非常适合解决非凸问题，因为它们不会陷入局部最小值。但它在解决高维问题时表现不佳，因为它是离散的。它不使用任何梯度信息。所以实际上必须去探索每个点才能知道它的cost，这是非常低效的。
连续函数优化擅长解决高维问题，因为它们使用基于梯度的方法可以非常快速地找到一个好的解决方案。但是对于非凸问题，它们很容易陷入局部最小值并产生较差的解决方案。
Tesla 规控团队的解决方案是分层分解，思路与Apollo 的规划算法相似。首先，使用粗搜索的方法将非凸性分解，将问题转化为凸空间的优化，然后使用优化算法得到最终的平滑轨迹。
下面两个经典场景介绍特斯拉Planning模块的处理流程：
Lane Change规划：
特斯拉规划算法路口左转1
在上面这个案例中，导航节点Routing模块的请求是自车需要在前方第二个路口处进行左转。因此自车需要连续向左变道两次，才可以在第二个路口处执行左转操作。
通过上面视频可以看到在求解该问题时，Planner首先搜索到了两种可行的决策，第一种决策是较早变道，但是由于前方障碍物的影响，自车会进行较重的制动，会造成体感的不舒适；第二种决策是在较远的地方进行变道，速度规划的结果是首先进行驾驶通过第一个路口，之后在进行变道。
Planner会在很短的时间内进行了数千次这样的搜索。这个案例中1.5ms内会进行2500次搜索，这个搜索速度非常快。如果当前车速是60km/h,1.5ms自车只会前进2.5cm，但是Planner已经对2500条行车路线进行了判断。
最后，Planner根据安全、舒适和容易转弯的最优条件选择一条最优轨迹。
特斯拉规划算法路口左转2
通过上面的视频可以看到，最终Planner 选择的轨迹是流畅而且符合驾驶员判断的。
参考：