摘要

实时进行路径规划是车辆能够实现自动驾驶的重要功能之一，自动驾驶车辆面对的交通场景多而复杂，因此如何根据感知层得到的车辆周边的障碍物、车流、人流信息规划出一条安全、驾乘舒适、平滑的路径是自动驾驶领域的经典难题，而服务于自动驾驶的决策规划也在近年来受到了学术界和工业界越来越多的关注。本文对该领域主要研究进展进行了综述。首先，介绍自动驾驶决策规划模块的重要作用。其次介绍规划与决策分层次的结构，以及每个层次的重要算法。最后总结实际自动驾驶的决策规划模块的典型问题，并展望这个方向的研究趋势。
关键词：自动驾驶；感知决策；路径规划；层次结构

一、自动驾驶决策感知的介绍和重要意义

决策规划是自动驾驶的核心技术，决策感知的主要任务就是要基于感知模块感知到的车辆周边状态，找到一条安全的，乘客乘坐体验舒适的，平滑的的路径，交给控制模块执行。形象的讲，决策规划就是自动驾驶的大脑。大脑在接收到传感器的各种感知信息之后，对当前环境作出分析，然后对底层控制模块下达指令。
在现有的决策和规划框架中，有两种主要系统：基于规则的决策和基于学习的决策和计划方案。基于规则的决策利用驱动规则和专家知识来确定最优逻辑行为，其代表性方法是有限状态机(FSM)[6]和马尔可夫决策过程(MDP)[8]，[9]。基于学习的方法利用不同的网络结构，根据环境生成具有最佳回报的最优策略。各种基于学习的方法，如强化学习都很受欢迎。

二、自动驾驶感知决策的层次结构

一般来说，决策规划模块可以分为三个层次结构：全局路径规划，行为决策，运动规划

1全局路径规划

全局路径规划(Route Planning)在接收到一个给定的行驶目的地之后，结合地图信息，生成一条全局的路径，作为为后续具体路径规划的参考；全局规划需要我们知道目的地，是一种长期的规划，更关心高层的信息，不太关心很细枝末节上的决策。全局规划的本质是一种搜索，在优化领域就是给定约束下的最小化问题。
全局路径规划是指在给定车辆当前位置与终点目标后，通过搜索选择一条最优的路径，这里的“最优”包括路径最短，或者到达时间最快等条件。这一过程类似于我们生活中经常用到的“导航”功能，区别在于自动驾驶中使用的高精地图与我们常见的地图不太一样，在高精地图中包含了每条车道在内的更多信息。常见的全局路径规划算法包括Dijkstra和A算法，以及在这两种算法基础上的多种改进。Dijkstra算法[3]和A算法[4]也是在许多规划问题中应用最为广泛的两种搜索算法。
解决全局优化常见的代表算法有：Dijkstra、A、MDP。Dijkstra是一种广度优先搜索，因为每个节点都要探寻，所以搜索会慢；而A*及其各种衍生算法是一种启发式算法，搜索过程会朝着目的点前进，避免了一些无谓的搜索；MDP是强化学习的思路，构建环境和奖励系统，让运动对象吃亏上当后，学会精致利己，沿着目标点前进。

2行为决策（行为预测）

在确定全局路径之后，自动驾驶车辆需要根据具体的道路状况、交通规则、其他车辆与行人等情况作出合适的行为决策。
自动驾驶的场景是成千上万的，并且会受到周边车主的影响，不同的驾驶者相互影响，而为了进行路径规划就需要对环境中的其它参与者的行为进行预测；而且感知模块难以做到对周边环境的完全感知，所以对自动驾驶车辆周边环境进行预测是十分有必要的。
而行为决策（行为预测）的模型分为四类：

2.1有限状态机模型

自动驾驶车辆最开始的决策模型为有限状态机模型，车辆根据当前环境选择合适的驾驶行为，如停车、换道、超车、避让、缓慢行驶等模式，状态机模型通过构建有限的有向连通图来描述不同的驾驶状态以及状态之间的转移关系，从而根据驾驶状态的迁移反应式地生成驾驶动作。

有限状态机模型因为简单、易行，是无人驾驶领域目前最广泛的行为决策模型，但该类模型忽略了环境的动态性和不确定性，此外，当驾驶场景特征较多时，状态的划分和管理比较繁琐，多适用于简单场景下，很难胜任具有丰富结构化特征的城区道路环境下的行为决策任务。

2.2 决策树

决策/行为树模型和状态机模型类似，也是通过当前驾驶状态的属性值反应式地选择不同的驾驶动作，但不同的是该类模型将驾驶状态和控制逻辑固化到了树形结构中，通过自顶向下的“轮询”机制进行驾驶策略搜索。这类决策模型具备可视化的控制逻辑，并且控制节点可复用，但需要针对每个驾驶场景离线定义决策网路，当状态空间、行为空间较大时，控制逻辑将比较复杂。另外，该类模型同样无法考虑交通环境中存在的不确定性因素。

2.3基于知识的推理决策

基于知识的推理决策模型由“场景特征－驾驶动作”的映射关系来模仿人类驾驶员的行为决策过程，该类模型将驾驶知识存储在知识库或者神经网络中，这里的驾驶知识主要表现为规则、案例或场景特征到驾驶动作的映射关系。进而，通过“查询”机制从知识库或者训练过的网络结构中推理出驾驶动作。
该类模型主要包括：基于规则的推理系统、基于案例的推理系统和基于神经网络的映射模型。
该类模型对先验驾驶知识、训练数据的依赖性较大，需要对驾驶知识进行精心整理、管理和更新，虽然基于神经网络的映射模型可以省去数据标注和知识整合的过程，但是仍然存在以下缺点：
其“数据”驱动机制使得其对训练数据的依赖性较大，训练数据需要足够充分；
将映射关系固化到网络结构中，其解释性较差；
存在“黑箱”问题，透明性差，对于实际系统中出现的问题可追溯性较差，很难发现问题的根本原因。

2.4基于价值的决策模型

根据最大效用理论，基于效用／价值的决策模型的基本思想是依据选择准则在多个备选方案中选择出最优的驾驶策略/动作。

为了评估每个驾驶动作的好坏程度，该类模型定义了效用（utility）或价值（value）函数，根据某些准则属性定量地评估驾驶策略符合驾驶任务目标的程度，对于无人驾驶任务而言，这些准则属性可以是安全性、舒适度、行车效率等，效用和价值可以是由其中单个属性决定也可以是由多个属性决定。
澳大利亚格里菲斯大学的Furda和Vlacic提出了多准则决策方法从候选动作集中选择最优的驾驶动作；新加坡国立大学的Bandyopadhyay等人提出了基于POMDP的行为决策模型，用以解决存在感知不确定性的情况；卡内基梅隆大学的Wei J等人提出基于PCB（Prediction and-Cost-function Based）的行为决策模型，其侧重点在于如何构建恰当的代价函数来指导对环境的预测；为了解决在多智能体参与的复杂环境中的决策问题，许多基于博弈论的模型也被研究者用来推理车辆之间的交互行为，；此外，因为在特征提取方面的优势，深度强化学习技术也开始被广泛应用，以完成最优驾驶动作的生成。

3运动规划

在确定具体的驾驶行为之后，我们需要做的是将“行为”转化成一条更加具体的行驶“轨迹”，从而能够最终生成对车辆的一系列具体控制信号，实现车辆按照规划目标的行驶。这一过程称为运动规划(Motion Planning)，运动规划的概念在机器人领域已经有较长时间的研究历史，我们可以从数学的角度将它看做如下的一个优化问题
在以机器人为代表的许多场景中，我们可以认为周围的环境是确定的。在这种情况下，所谓的路径规划，是指在给定的一个状态空间Χ，寻找一个满足一定约束条件的映射σ:[0,1]➞Χ，这些约束包括：
确定的起始状态以及目标点所在的区域
避免碰撞
对路径的微分约束(例如在实际问题中路径曲率不能太小，对应于其二阶导数的约束)
该优化问题的目标泛函定义为J(σ)，其具体意义可以表示为路径长度、控制复杂度等衡量标准。
然而在自动驾驶问题中，车辆周围的环境是持续动态变化的，因此单纯的路径规划不能给出在行驶过程中一直有效的解，因此我们需要增加一个维度——时间T，相应的规划问题通常被称为轨迹规划。
时间维度的增加为规划问题带来了巨大的挑战。例如，对于一个在2D环境中移动一个抽象为单点的机器人，环境中的障碍物近似为多边形的问题。路径规划问题可以在多项式时间内求解，而加入时间维度的轨迹规划问题已经被证明是NP-hard问题。
在自动驾驶的实际场景中，无论是对车辆本身还是对周围环境，建立更为精确的模型意味着对优化问题更为复杂的约束，同时也意味着求解的更加困难。因此实际采用的算法都是建立在对实际场景的近似前提下，在模型精确性和求解效率二者之间寻求一个最佳的平衡点。
下文对自动驾驶领域目前常见的几类运动规划算法分别进行介绍，在实际中，往往是其中几类思想的结合才能最终达到比较好的规划结果，并满足更多的不同场景。
时间维度的增加为规划问题带来了巨大的挑战。例如，对于一个在2D环境中移动一个抽象为单点的机器人，环境中的障碍物近似为多边形的问题。路径规划问题可以在多项式时间内求解，而加入时间维度的轨迹规划问题已经被证明是NP-hard问题。
在自动驾驶的实际场景中，无论是对车辆本身还是对周围环境，建立更为精确的模型意味着对优化问题更为复杂的约束，同时也意味着求解的更加困难。因此实际采用的算法都是建立在对实际场景的近似前提下，在模型精确性和求解效率二者之间寻求一个最佳的平衡点。
下文对自动驾驶领域目前常见的几类运动规划算法分别进行介绍，在实际中，往往是其中几类思想的结合才能最终达到比较好的规划结果，并满足更多的不同场景。

3.1基于搜索的规划算法

解决运动规划问题的另一大类算法是启发性搜索算法，其基本思想是将状态空间通过确定的方式离散成一个图，然后利用各种启发式搜索算法搜索可行解甚至是最优解．这类算法具有解析完备性，甚至是解析最优性，该种类别算法现已比较成熟
基于搜索的算法的基础是状态格子，状态格子[21]是一种对状态空间离散化的手段，状态格子由结点（表示状态）和从该结点出发到达相邻结点的运动基元组成，一个状态结点可以通过其运动基元变换到另一个状态结点．这样，状态格子就将原来连续的状态空间转化为一个搜索图，运动规划问题就变成了在图中搜索出一系列将初始状态变换到目标状态的运动基元构建起状态格子后就可以使用图搜索算法来搜索最优轨迹	
在将状态空间栅格化之后，我们就可以使用前文已经介绍的Dijkstra、A*搜索算法，完成最终的规划。然而在实际复杂环境中，栅格数目众多，并且环境随时间动态变化，会导致搜索结点过多，因此发展出了多种改进算法，用以处理不同的具体场景：
Dijkstra算法遍历整个构型空间，找出每两个格子之间的距离，最后选择出发点到目标点的最短路径，其广度优先的性质导致效率很低，在该算法的基础上加入启发式函数，即所搜索结点到目标节点的距离，并以此为基础再次进行搜索可避免全局搜索带来的效率低下，这即为A*算法