2021年01月05日 | 无人驾驶如何进行规划?无人驾驶如何自我控制?

举办的 DAPRA 城市挑战赛，在比赛中多数参赛队都将无人车的规划模块分为三层设计：任务规划，行为规划和动作规划，其中，任务规划通常也被称为路径规划或者路由规划(Route Planning)，其负责相对顶层的路径规划，例如起点到终点的路径选择。

我们可以把我们当前的道路系统处理成有向网络图(Directed Graph Network)，这个有向网络图能够表示道路和道路之间的连接情况，通行规则，道路的路宽等各种信息，其本质上就是我们前面的定位小节中提到的高精度地图的“语义”部分，这个有向网络图被称为路网图(Route Network Graph)，如下图所示：

这样的路网图中的每一个有向边都是带权重的，那么，无人车的路径规划问题，就变成了在路网图中，为了让车辆达到某个目标(通常来说是从 A 地到 B 地)，基于某种方法选取最优(即损失最小)的路径的过程，那么问题就变成了一个有向图搜索问题，传统的算法如迪科斯彻算法(Dijkstra’s Algorithm)和 A*算法(A* Algorithm)主要用于计算离散图的最优路径搜索，被用于搜索路网图中损失最小的路径。

2. 行为规划

行为规划有时也被称为决策制定(Decision Maker)，主要的任务是按照任务规划的目标和当前的局部情况(其他的车辆和行人的位置和行为，当前的交通规则等)，作出下一步无人车应该执行的决策，可以把这一层理解为车辆的副驾驶，他依据目标和当前的交通情况指挥驾驶员是跟车还是超车，是停车等行人通过还是绕过行人等等。

行为规划的一种方法是使用包含大量动作短语的复杂有限状态机(Finite State Machine，FSM)来实现，有限状态机从一个基础状态出发，将根据不同的驾驶场景跳转到不同的动作状态，将动作短语传递给下层的动作规划层，下图是一个简单的有限状态机：

如上图所示，每个状态都是对车辆动作的决策，状态和状态之间存在一定的跳转条件，某些状态可以自循环(比如上图中的循迹状态和等待状态)。虽然是目前无人车上采用的主流行为决策方法，有限状态机仍然存在着很大的局限性：首先，要实现复杂的行为决策，需要人工设计大量的状态;车辆有可能陷入有限状态机没有考虑过的状态;如果有限状态机没有设计死锁保护，车辆甚至可能陷入某种死锁。

3. 动作规划

通过规划一系列的动作以达到某种目的(比如说规避障碍物)的处理过程被称为动作规划。通常来说，考量动作规划算法的性能通常使用两个指标：计算效率(Computational Efficiency)和完整性(Completeness)，所谓计算效率，即完成一次动作规划的处理效率，动作规划算法的计算效率在很大程度上取决于配置空间(Configuration Space)，如果一个动作规划算法能够在问题有解的情况下在有限时间内返回一个解，并且能够在无解的情况下返回无解，那么我们称该动作规划算法是完整的。

配置空间：一个定义了机器人所有可能配置的集合，它定义了机器人所能够运动的维度，最简单的二维离散问题，那么配置空间就是[x， y]，无人车的配置空间可以非常复杂，这取决于所使用的运动规划算法。

在引入了配置空间的概念以后，那么无人车的动作规划就变成了：在给定一个初始配置(Start Configuration)，一个目标配置(Goal Configuration)以及若干的约束条件(Constraint)的情况下，在配置空间中找出一系列的动作到达目标配置，这些动作的执行结果就是将无人车从初始配置转移至目标配置，同时满足约束条件。

在无人车这个应用场景中，初始配置通常是无人车的当前状态(当前的位置，速度和角速度等)，目标配置则来源于动作规划的上一层——行为规划层，而约束条件则是车辆的运动限制(最大转角幅度，最大加速度等)。

显然，在高维度的配置空间来动作规划的计算量是非常巨大的，为了确保规划算法的完整性，我们不得不搜索几乎所有的可能路径，这就形成了连续动作规划中的“维度灾难”问题。目前动作规划中解决该问题的核心理念是将连续空间模型转换成离散模型，具体的方法可以归纳为两类：组合规划方法(Combinatorial Planning)和基于采样的规划方法(Sampling-Based Planning)。

运动规划的组合方法通过连续的配置空间找到路径，而无需借助近似值。由于这个属性，它们可以被称为精确算法。组合方法通过对规划问题建立离散表示来找到完整的解，如在 Darpa 城市挑战赛(Darpa Urban Challenge)中，CMU 的无人车 BOSS 所使用的动作规划算法，他们首先使用路径规划器生成备选的路径和目标点(这些路径和目标点事融合动力学可达的)，然后通过优化算法选择最优的路径。

另一种离散化的方法是网格分解方法(Grid Decomposition Approaches)，在将配置空间网格化以后我们通常能够使用离散图搜索算法(如 A*)找到一条优化路径。

基于采样的方法由于其概率完整性而被广泛使用，最常见的算法如 PRM(Probabilistic Roadmaps)，RRT(Rapidly-Exploring Random Tree)，FMT(Fast-Marching Trees)，在无人车的应用中，状态采样方法需要考虑两个状态的控制约束，同时还需要一个能够有效地查询采样状态和父状态是否可达的方法。后文我们将详细介绍 State-LatticePlanners，一种基于采样的运动规划算法。

二、控制

控制层作为无人车系统的最底层，其任务是将我们规划好的动作实现，所以控制模块的评价指标即为控制的精准度。控制系统内部会存在测量，控制器通过比较车辆的测量和我们预期的状态输出控制动作，这一过程被称为反馈控制(Feedback Control)。

反馈控制被广泛的应用于自动化控制领域，其中最典型的反馈控制器当属 PID 控制器(Proportional-Integral-Derivative Controller)，PID 控制器的控制原理是基于一个单纯的误差信号，这个误差信号由三项构成：误差的比例(Proportion)，误差的积分(Integral)和误差的微分(Derivative)。

PID 控制因其实现简单，性能稳定到目前仍然是工业界最广泛使用的控制器，但是作为纯反馈控制器，PID 控制器在无人车控制中却存在一定的问题：PID 控制器是单纯基于当前误差反馈的，由于制动机构的延迟性，会给我们的控制本身带来延迟，而 PID 由于内部不存在系统模型，故 PID 不能对延迟建模，为了解决这一问题，我们引入基于模型预测的控制方法。

预测模型：基于当前的状态和控制输入预测未来一段时间的状态的模型，在无人车系统中，通常是指车辆的运动学 / 动力学模型;

反馈校正：对模型施加了反馈校正的过程，使预测控制具有很强的抗扰动和克服系统不确定性的能力。

滚动优化：滚动地优化控制序列，以得到和参考轨迹最接近的预测序列。

参考轨迹：即设定的轨迹。

下图表示模型预测控制的基本结构，由于模型预测控制基于运动模型进行优化，在 PID 控制中面临的控制延时问题可以再建立模型考虑进去，所以模型预测控制在无人车控制中具有很高的应用价值。