2 有限状态机 | 自动驾驶小白说

2.1 概述

有限状态机（Finite State Machine, FSM）是一种计算模型，它包含一组有限个状态及其之间的转移规则，可以被用来描述不同对象或者系统在不同状态下的行为和变化（如下图所示）。其在自动驾驶行为决策中应用颇为广泛，车辆根据当前环境选择合适的驾驶行为，如停车、换道、超车、避让、缓慢行驶等模式，状态机模型通过构建有限的有向连通图来描述不同的驾驶状态以及状态之间的转移关系，从而根据驾驶状态的迁移反应式地生成驾驶动作。

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

2.2 算法详解

2.2.1 特性

有限状态机是一个非常有用的模型，可以模拟世界上大部分事物，简单说，它有三个特征：

状态（state）的总数是有限的

在任一时刻，只处在一种状态之中

某种条件下，会从一种状态转移（transition）到另一个状态

2.2.2 核心概念

状态机有四个核心概念：

状态（State）：一个状态机至少要包含两个状态

事件（Event）：执行某个动作/操作的触发条件或者口令

动作（Action）：事件发生后要执行的动作

转移（Transition）：从一个状态转移到另一个状态

2.2.3 分层有限状态机

分层有限状态机是早期DARPA挑战赛中被许多队伍采用的行为规划方法，而有限状态机是分层有限状态机的基础。

当存在大量状态时，有限状态机体系就有可能变得非常庞大，状态机的结构也会变得更加复杂，此外，有限状态机还存在如下几个问题：

可维护性差：当新增或者删除一个状态的时候，需要改变所有与之相关联的状态，所以对状态机的大幅度的修改很容易出问题

可扩展性差：当FSM包含大量状态时，有向图可读性很差，扩展性较差

复用性差：几乎不可能在多个项目中使用相同的FSM

这时候就需要使用分层状态机(Hierarchical Finite-State Machine)了，把那些同一类型的状态作为一个小状态机，然后再做一个大的状态机，来维护这些子状态机，如下图所示：

相比于FSM，HFSM增加了一个超级状态（Super-state）：本质上就是将同一类型的一组状态组合为一个集合（即上图中的方框），超级状态之间也有转移逻辑。这也就意味着HFSM不需要为每一个状态和其他状态建立转移逻辑，由于状态被归类，类和类之间存在转移逻辑，那么类和类之间的状态转移可以通过继承这个转移逻辑来实现，这里的转移继承就像面向对象编程中通过多态性让子类继承父类一样。

2.2.4 优缺点

优点

结构清晰，易于理解和维护，可扩展性很强
与if-else语句相比，避免了复杂的嵌套，提高代码可读性和可维护性

缺点

当驾驶场景特征较多时，状态的划分和管理比较繁琐，导致状态机过于庞大

2.3 算法实例

在低级别自动驾驶和简单高速场景中，我们可以使用一个简单的状态机来维护变道过程，其中：

状态：车道保持，变道等待，变道执行和变道取消

事件：变道请求，变道安全，变道危险

动作：无

转移：

在车道保持状态下，收到变道请求，状态转移到变道等待中。变道请求可能来自于驾驶员指示、或是导航的要求，也可能来自车辆主动提速的需求。比如说前面的车特别慢，我们想超过他，就会主动发起变道请求。
在变道等待状态下，检查当前车道和目标车道状态是否安全可允许变道，若检查通过，则发出变道安全指令，并且状态转移到变道执行状态，若变道不安全，则一直处于变道等待状态。
在变道执行状态下，持续检查目标车道是否满足继续变道条件，比如变道时如果后方车辆突然加速，此时发出变道危险指令，并且状态转移到变道取消状态，回到原车道。

🌟Note: 在此例子下，做变道安全检查时一般都是用比较简单的规则。如下图所示，一般会检查自车跟前车的距离，或跟目标车道前车和后车的距离与相对速度是否满足安全的变道条件，以此也可以看出，整个状态机比较简单，为考虑过于复杂的交互场景，因此不太适合复杂的城市道路场景，更适用于结构化高速公路场景。