无人驾驶中的规划算法

汽车学堂，www.auto-mooc.com

隶属清华大学苏州汽车研究院旗下清研车联

专注汽车新技术人才培养

对无人驾驶软件架构进行分层，大致分成三层：感知层、决策层与控制层。

感知是指无人驾驶系统从环境中收集信息并从中提取相关知识的能力。

规划是无人车为了某一目标而作出一些有目的性的决策的过程，对于无人驾驶车辆而言，这个目标通常是指从出发地到达目的地，同时避免障碍物，并且不断优化驾驶轨迹和行为以保证乘客的安全舒适。

控制则是无人车精准地执行规划好的动作的能力，这些动作来源于更高的层。

规划

任务、行为、动作

无人驾驶规划系统的分层结构设计源于2007年举办的DAPRA城市挑战赛，在比赛中多数参赛队都将无人车的规划模块分为三层设计：任务规划，行为规划和动作规划。

任务规划

任务规划通常也被称为路径规划或者路由规划（Route Planning），其负责相对顶层的路径规划，例如起点到终点的路径选择。

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

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

行为规划

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

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

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

动作规划

通过规划一系列的动作以达到某种目的（比如说规避障碍物）的处理过程被称为动作规划。通常来说，考量动作规划算法的性能通常使用两个指标：计算效率（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-Lattice Planners，一种基于采样的运动规划算法。

———— / END / ————