作者： 牧民
本文将介绍特斯拉 Tesla 在 AI Day 上提到的决策规划模块 Planner。
同人类驾驶员一样，Planner 在接收到经过视觉神经网络处理过的 3D Vector Space 后，将会在该 Space 进行搜索判断，从而找到一条轨迹可以最大限度地提高汽车的安全性、舒适性和效率，将车辆规划至目的地。
作为最早布局自动驾驶的厂商，Tesla 早期的 Planner 已经可以很好的在高速公路或者是城市快速路段进行规划，包括单车道的车道保持、导航变道、主动超车、自动上下闸道也都经受了量产的考验。
随着自动驾驶的发展，Tesla Autopilot 的使用场景需要从高速扩展到城市道路，特斯拉 Autopilot 要求 Planner 在城市街道自动驾驶中同样表现出色。
在城市自动驾驶系统要复杂更多，决策规划中需要解决的关键问题是解空间既是非凸问题又是高维问题。
非凸问题优化
什么是「非凸问题」？
这是一个很重要的数据概念，先看一下学术上的解释：
凸函数的概念是局部最优解就是全局最优解，在数学中的一个非凸的最优化问题也就意味着局部最优解并不是全局最优解，比如一个复杂的多峰函数，有多个峰值其实都是局部的最优解，但是从整个函数来看并非每个局部最优解就是全局最优，所以非凸函数寻最优是更难的事情。
那就有了一个新问题：这和自动驾驶有什么关系？
我们要知道，自动驾驶的规划目标是：算出一条满足约束的最优路径。
简单理解就是，自动驾驶的算法本身就是数学求解的过程，而自动驾驶的规划问题是一个「凸优化问题」、自动驾驶的避障约束也不是凸空间。同时，自动驾驶安全不可只做局部安全，它一定是一个具有约束性质的「全局安全」。
一句话总结：自动驾驶的「静态 + 动态」的约束空间都是非凸问题。
为什么要讲凸优化？
-
凸优化是目前最简单的非线性的规划方法，或者这么说，凸优化是目前人类唯一研究明白的非线性的优化方法。
-
凸优化是复杂优化方法的基石，大多数问题都是转化为凸优化问题解决。
非凸问题可以有多种可能的解决方案，并且它们又比较独立，但是在搜索时要获得一个全局最优解较难，Planner 在搜索时很容易进入到局部最优。
高维度：
轨迹规划高维度的出现是因为汽车需要规划接下来的 10 到 15 秒，并且需要生成整个规划窗口内自车的位置、速度和加速度，这在运行时需要生成的大量参数。
解决上述问题的常用方法有两种：离散搜索方法和连续函数优化。
离散搜索方法非常适合解决非凸问题，因为它们不会陷入局部最小值。但它在解决高维问题时表现不佳，因为它是离散的。它不使用任何梯度信息。所以实际上必须去探索每个点才能知道它的 Cost，这是非常低效的。
连续函数优化擅长解决高维问题，因为它们使用基于梯度的方法可以非常快速地找到一个好的解决方案。但是对于非凸问题，它们很容易陷入局部最小值并产生较差的解决方案。
Tesla 规控团队的解决方案是分层分解，思路与 Apollo 的规划算法相似。
首先，使用粗搜索的方法将非凸性分解，将问题转化为凸空间的优化，然后使用优化算法得到最终的平滑轨迹。
下面两个经典场景介绍特斯拉规划模块的处理流程：
Lane Change 规划
在上面这个案例中，导航节点 Routing 模块的请求是自车需要在前方第二个路口处进行左转。
因此，自车需要连续向左变道两次，才可以在第二个路口处执行左转操作。通过上图可以看到在解决该问题时，Planner 首先搜索到了两种可行的决策。
- 第一种决策是较早变道，但是由于前方障碍物的影响，自车会进行较重的制动，会造成体感的不舒适；
- 第二种决策是在较远的地方进行变道，速度规划的结果是首先进行驾驶通过第一个路口，之后在进行变道。
Planner 会在很短的时间内进行了数千次这样的搜索。这个案例中 1.5 ms 内会进行 2500 次搜索，这个搜索速度非常快。
如果当前车速是 60 km/h，1.5 ms 自车只会前进 2.5 cm，但是 Planner 已经对 2500 条行车路线进行了判断。
最后，Planner 根据安全、舒适和容易转弯的最优条件选择一条最优轨迹。通过上面的视频可以看到，最终 Planner 选择的轨迹是流畅而且符合驾驶员判断的。
城市道路规划算法
上面介绍了 Tesla 的规划算法在结构化道路上的表现，下面讲讲 Tesla 规划算法在城市道路上的表现。
与结构化道路相比，城市道路往往更复杂，不仅道路结构更复杂，而且往往伴随车道线被遮挡，或者障碍物（obstacle）的行为更复杂。
在这种场景下，不仅要求感知节点能准确识别障碍物，对于规划算法要求也更高，不仅要处理对象来车，还要处理横穿的行人等多种复杂场景，对算法的优化以及鲁棒性，要求都很高。
下面以一个示例来阐述 Tesla 的规划算法面对城市工况的处理：
在城市的街道（狭窄道路）上进行自动驾驶时，不仅要根据当前的场景规划自车的行驶轨迹，更重要的是对于与自己产生交互的障碍物进行预测，并且根据预测的轨迹来实时调整自车的决策行为。
为了做到这一点，特斯拉的 Planning 算法提出对于每个产生交互的障碍物进行独立规划的概念。
在上面场景中：
一，迎面而来的 1 号车先到，Autopilot 稍微放慢了速度。但随后，它意识到它无法主动避开迎面而来的汽车，因为它的一侧没有空间。但是 1 号车可以代替我们让步。
此时，Autopilot 并没有在这里盲目地刹车，而是认为 1 号汽车的速度足够低，可以靠边停车，应该对我们让步。
因此，Autopilot 果断地规划了前进路线。
二，第二辆迎面而来的汽车 #2 现在到达，这辆车的速度更高。在这个场景中，特斯拉决策规划算法为另一个对象运行轨迹规划。
迎面而来的汽车的预测结果：
- 高概率：绕过其他停放的汽车（红色路径）
- 低概率：收益率（绿色路径）
根据对迎面而来的 2 号车辆的预测，自动驾驶算法决定靠边停车。
因此，当自动驾驶汽车靠边时，我们注意到当根据目标障碍物的横摆角速度和加速度判断目标选择了让步，自动驾驶算法立即改变主意，并继续向前行驶。
遥控泊车问题
讨论特斯拉的自动驾驶规划算法，其实可以从特斯拉的智能泊车聊起，很多时候大部分都以为解决公开道路的自动驾驶要比解决一个限定场景内的自动驾驶要更难。
显然这个观点并不成立，特斯拉做最后一公里的泊车并不是这么简单的，相比之下这个场景需要解决的问题一点不比公开道路少。
对于特斯拉而言，泊车场景其实和公开道路的目标是一致的，都是要让车辆实现高水平自动化，泊车场景的目标是，自我车 (蓝色) 需要停在绿色的停车位上，绕过路边、停着的车和圆锥体 (橙色)。
Baseline
简单基线采用 A 算法。
A 的启发式函数是欧几里德距离，正如你从上面的图片中看到的那样，它很快就陷入了局部极小值。
最终，它取得进展并到达本地，但最终使用了近 400,000 个节点来完成此操作。
使用导航
如果在基线上添加了一个导航路线，它会立即帮助。但当遇到障碍时，它基本上会做和之前一样的事情，回溯，然后搜索全新的路径，最终，它仍然需要 22000 个节点。
蒙特卡洛树搜索
有没有更有效的解决办法？
又到了「第一原理思考」的时候了。目前，决策过程的最佳实践是使用启发式搜索算法，而启发式搜索算法的最佳实践是蒙特卡罗搜索树（MCTS）。
到 2021 年为止，基于 MCTS 的最好、最新的算法是 DeepMind 公司的 MuZero。
而 DeepMind 是什么？
看看百度百科的介绍：
DeepMind 位于英国伦敦，是由人工智能程序师兼神经科学家戴密斯・哈萨比斯（Demis Hassabis）等人联合创立的 Google 旗下 前沿人工智能企业。
其将机器学习和系统神经科学的最先进技术结合起来，建立强大的通用学习算法。
有趣的是，安德烈・卡帕西（AndrejKarpathy）曾在这里实习。
MuZero 在无需告知规则的情况下就精通围棋、国际象棋 Shogi 和 Atari。
它有能力在未知的环境中制定制胜策略，这似乎是解决特斯拉停车问题的完美模式，把自动驾驶的规划问题变成「停车游戏」就行了。
MuZero 是一个基于模型的规划系统，也是一个基于模型的强化学习系统，旨在通过学习环境动态的精确模型，然后使用它来进行规划来解决这个问题。
因此，特斯拉人工智能团队正在研究可以产生状态和行动分布的神经网络，然后可以插入蒙特卡罗树搜索与各种成本函数。这些成本函数可以是明确的成本函数，如距离、碰撞、舒适度、穿越时间和实际手动驾驶事件的干预。
结果就是，规划器基本上能够一次朝着目标前进，注意到这甚至没有使用导航启发式，只是给定场景，规划器能够直接朝着目标前进。
神经网络能够吸收场景的全局上下文，然后产生一个值函数，有效地引导它走向全局最小值，而不是陷入任何局部最小值，结果是只需要 288 个节点。
所以不得不佩服特斯拉的工程能力，当更多人还在讨论还在讨论 AlphoZero 和 MuZero 除了玩游戏还能做什么的时候，特斯拉已经将其应用到自动驾驶系统中。
写在最后
通过 Tesla 的介绍可以发现，决策规划算法的执行逻辑与人类驾驶员很相似，不仅是简单的优化求解，更多时候在求解轨迹时，有对目标障碍物进行预测，并根据预测的结果进行博弈的过程，这样可以使同行效率更高，整个自动驾驶的运行过程更加智能。
特斯拉的算法确实有可取之处，但是目前国内的很多新势力、自动驾驶公司在城市工况的自动驾驶算法领域，也有深入的实践与技术积累，在一些公开测试中也取得了不错的表现，大家也要对我们的国产自动驾驶技术报以信心。
