如果说自动驾驶的当下是感知，那自动驾驶的未来就在于规划。
这其实就是一个“强感知、弱智能”还是“弱感知、强智能”的问题。我们都知道人类属于后者，虽然我不能看到车周围360°的场景，但是这不妨碍我开车。而当前的智能车往往周围环境看得是毫无死角，但是本身却是个“智障”。但凡碰到个没遇到过的场景就不知道怎么走了。差距在哪，就在决策规划上。规划本质上是一个搜索过程，搜索的是如何解决问题的最优解。谷歌、百度的搜索为你呈现的是你最想知道的回答，而在自动驾驶的语境下，搜索的就是从A点到B点的最优行驶路径。用数学语言表述就是
那什么是“最优”，如何去定义这个“最优”?“最优”就是通过函数去定义的，就是这儿的f(x)，它又被称为目标函数或损失函数。
整个规划过程就是在给定当前环境下，如何找到一个x使得目标函数最小(或最大)。因此，规划就是一个优化问题(optimization)。了解了规划的本质，那如何构建一个自动驾驶规划的问题?这是一个非常复杂的问题。
从上面的描述中我们知道，首先我们需要定义一个目标函数，来评判整个规划过程是好是坏，也就是说这个函数的选取将会决定你规划出来路径的好坏。因此如何确定这个f(x)就是一个大难题。同样复杂的还有前面那句话“给定当前环境下”。
自动驾驶汽车面临的周遭环境是非常复杂的，不仅有多变的障碍物，还有各种交通法规以及车辆运动学、动力学的限制。种种这些因素都需要考虑进去。既然复杂，既然不好解，那就想办法，把复杂的问题简单化，首先从最简单的问题切入。在机器人学中，为了教会机器人如何去走，研究者们抽象出了一类问题叫做路径规划(path finding)。
我们不需要去关心环境的变化，因为假设周围环境都是静止的，也不需要关心是否符合运动学和动力学，因为机器人被抽象成了一个点。我们只需要关心从A点到B点，什么样的路径是最优的，用什么算法能找到这样的路径。
路径规划算法你看，这样一简化，我们直接略去了所有的限制，而只专注于如何确定f(x)，问题就简单了很多。在这种情况下，最优的路径也就是最短的路径。
那最短路径搜索的算法我们都知道，用广度优先，从起点开始，由近及远的开始搜索，直到到达终点为止。ok，我们终于将问题分解到我们能轻而易举解决的地步。从广度优先开始，我们逐次增加难度，思考如何优化并一步步去逼近最终的答案。
采用广度优先算法得到的两点之间最短路径的算法示意图
这里穿插为大家推荐一个好用的可视化路径规划算法的网站http://qiao.github.io/PathFinding.js/visual/。他把几种常用的规划算法都可视化出来，并且可以根据自己需要选定起点终点及障碍物排布，同时还给出了运行时间。
从上面的示意图我们发现，广度优先这种算法只会无脑地搜最近的节点，但是它不知道终点的方向，就这么漫无目的的搜索，效率极低。那为了提升搜索到最快路径的速度，我们会想到给他一个初始搜索方向，给他一个启发，让他大概知道搜索的方向。从漫无目的的满屏搜索变成了定向搜索，大大提高了效率。这种算法就是A*算法。A*算法结合了Dijkstra 算法和Best-First-Search算法的优势。一方面，它能像Dijkstra 算法一样确保搜索到最短路径;另一方面，他又像贪心的Best-First-Search算法一样，始终以最快的速度到达终点。其表达式为
g(n) 表示从起点到任意顶点 n 的路径的确切成本，h(n) 表示从顶点 n 到目标的启发式估计成本。通过平衡这两者带来的损失(或者说是以此为目标)，A*算法最终给出了更优的解法。
A*算法示意图可以看到，在搜索范围和所花时间上，A*有了很大的提升。由此，A*算法使我们又站在了一个新的起点上。我们明白了通过结合带着已知信息的搜索和局部最优的贪心搜索能够得到一个最优的结果。
之后的所有路径规划算法都是以A*为基础的变形与优化。站在这个起点上，我们眺望我们的终点——自动驾驶中运用的规划模块，发现还差得很远。为什么?因为到目前为止，我们假设我们周围的环境都是静态的，并且我们对全局环境是知晓的，我们知道终点在什么方位、知道哪哪有障碍物。但是无人车实际在路上的环境可就没有这么友好。
由于感知系统距离限制，你不可能提前知晓到终点前的所有障碍物，你只能随着车往前开进的过程中部分知晓周围的环境。由于对全局环境不可知，A*算法就没法用。怎么办?这自然难不倒聪明的人类。在Anthony Stentz 1994年的经典论文《Optimal and efficient path planning for partially-known environments》中提出了D*算法，成功解决了环境部分可知这个问题。
回想一下我们一直以来找路径的思路，是不是都是从起点出发往终点去找。那我们可不可以换个思路，从终点出发去连起点呢?答案当然是可以的，并且由于障碍物的存在，在动态路径规划中，起点本就是不断变化的。
因此路径规划严格来讲应该是找寻一条从当前节点到终点的路径。显然这种情况下，考虑从终点到当前节点更为方便。算法同样保留了当前节点到目标之间路径的成本函数，同时新增Modify函数来调整因探测到障碍物而改变的成本。最终不断循环，完成路径的构建。
D*
随着算法能力的增强，我们对条件的限制也在减少。到目前为止，搜索路线都是折线段，回看上面A*给出的路线图，还有走障碍物角点穿过的路径。我们都知道显然没有人开车会走折线，拐弯拐90°，蹭着障碍物的边开车的，因此算法还得再升级。
这里面我们少考虑了一点，就是车辆的运动学模型和动力学模型。当然这部分主要是控制模块应该考虑的事情，但是在规划模块，他们提出的要求就是你的路径应当是平滑的，而非一条条折线。因此，就需要在原算法中融入平滑性处理的算法，用平滑的轨迹去连接。这就够了吗?不不不，还不够。
我在之前的文章里说过，碰撞的物理学描述是两个物体在同一时刻到达了空间中的同一个点，因此，规划出了路径是不够的，这个路径里还需要增加时间这一维度，成为三维空间中的轨迹规划问题。车在路上开还需要遵守交通法规，如何把最优路径与驾驶安全结合起来同样也是需要考虑的问题。
无人车的高速行驶环境要求我们的算法必须实时计算，以确保及时采取措施规避风险。只有以上的这些限制都能满足了，才能称得上是一个合格的规控模块。
在真实的自动驾驶系统中，预测控制模块是如何工作的呢?欢迎大家去学习深蓝学院的这门专业课——自动驾驶控制与规划。你可以了解该模块在自动驾驶系统中的应用，学会设计多种控制器去控制车辆运动，最终完成一个实践项目，达到融会贯通的作用。