有限状态机（finite-state machine，FSM），又称有限状态自动机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型，是自动机理论的研究对象，在处理问题时具有类似于图灵机、马尔科夫算法的思考方式。一个有限状态机可以定义为五元组M＝｛Q，Σ，T，q0，F｝，其组成为：

①状态的有限集合Q；

②输入符号的有限集合Σ；

③转移函数T：Q×Σ→P（Q）；

④起始状态q0，并且q0∈Q；

⑤终止状态的集合F，并且F⊆Q。

FSM根据给定符号的输入，依据转移函数“跳转”过一系列状态，最终达到一个终止状态。其运行过程是一个由自动机步骤形成的循环，具有以下特征：

①程序运行的时间中可以清楚划分成数个自动机的步骤，每个步骤即为一个程序区段，有单一的进入点，可以是一个函数或其他程序；

②不同步骤的程序区段只能通过一组清楚标示的变量交换信息，这些变量称为状

FSM的转移函数可以用状态转移表实现，例如图9-26中所示的状态转移过程，能够使用表9-2的状态转移表描述。态。一个FSM在两个不同时刻之间仅有状态数值的不同，其余都相同。

图9-26　有限状态自动机的状态转移图

表9-2　有限状态自动机状态转移表

注：×表示在该状态下不会出现此事件。

注意到状态转移图与数据结构中的有向图类似，因此我们选择使用有向图的结构实现FSM。其中，有向图的节点作为自动机中的状态，有向图的弧表示自动机中的状态转移，有向图的常用存储方式是邻接表。具体而言，使用邻接表存储的有向图的节点具有以下元素：

①节点名称字符串，用来唯一标识此节点；

②节点数据，即此状态的状态转移程序，存储了相关的函数指针；

③弧向量，存储了所有以该节点为弧尾的弧。

接着，定义邻接表存储的有向图的弧，它具有以下元素：

①有向弧名称字符串，用来唯一标识此有向弧；

②弧头索引，即这条弧的弧头对应的节点在有向图的节点向量中的索引；

③可选的弧的附加信息。

使用邻接表存储的有向图本身则具有以下元素：(www.daowen.com)

①节点向量，存储了图中所有的节点；

②访问节点的方法，提供了访问某个特定节点的手段。

注意到在有向图中没有显式地存储有向弧，这是由于弧的存储是由弧尾节点负责的，每个节点仅负责维护从自身出发的那些弧。构造有向图时，首先向有向图的节点向量中添加相应的节点元素，每个被添加的节点都会具有一个对应的索引编号。节点添加完毕后，对每个节点的弧向量添加相应的弧。在添加时，指定所添加的弧的弧头索引，即可连接此节点和有向图的节点向量中弧头索引对应的节点。FSM对应有向图的邻接表如表9-3所示。

表9-3　FSM对应有向图的邻接表

通过定时器实现FSM的运行。在FSM开始运行前，一个索引值Α被初始化为a，代表初始状态对应图的节点的编号。此后，周期地执行以下操作：访问有向图中节点向量索引为Α的节点，获取节点的数据并执行对应的程序；程序的返回值Υ表示在经过的弧在邻接表中的索引；然后根据Υ对应的弧，确定下一个周期应该访问的节点在节点向量中的索引值。

通过FSM模型可以对协同运动策略进行描述，FSM在协同运动的执行过程中负责任务的上层逻辑，即当前任务处于什么阶段、应当执行什么动作的问题。

对于9．3中所述的协同运动策略，概括地说，其FSM模型包括以下几个主要状态：

①下潜Sd：AUV正在原地调整深度，在此过程中不断尝试识别目标。到达预定深度后即开始搜索；

②寻找目标Ss：AUV正在原地转向，尝试在当前深度层寻找目标；

③光信标引导：AUV正在由光信标引导进近；

④惯性引导：AUV在光信标引导过程中丢失目标；

⑤二维码追踪：AUV正在由AR Marker引导跟踪；

⑥惯性追踪：AUV在AR Marker引导过程中丢失目标。

相应地，FSM的事件包括：识别到光信标E1、识别到二维码E2、到达搜索深度层E3、丢失光信标阵列E4、丢失二维码E5、已经稳定识别二维码E6、惯性控制超时E7、当前深度层已搜索完成E8。

FSM的状态转移函数用状态转移表的形式表示，如表9-4所示。

表9-4　协同运动策略的状态转移表

注：×表示在该状态下不会出现此事件。

为了便于程序实现，在上述FSM中的部分状态前添加辅助状态，主要目的是在FSM程序转换到这些状态之前，先对其中的变量等进行初始化操作，将其转换为有向图的结构，如图9-27所示。

图9-27　协同策略状态机有向图

图9-27中，协同运动策略分解成若干任务目标作为有向图的节点，即FSM中的状态，其中包括视觉信息处理程序、控制程序和状态转移程序。节点之间使用有向弧连接，表示状态的单向转移。

FSM运行定时器的周期设定为控制周期。当定时器定时时间到，应先检查安保条件是否满足，如果发现当前状态超深或超时，则停止定时器的运行，自动机到达“终止”状态，任务随之结束。如果当前在安全范围内，则根据上面的描述运行FSM：访问一个状态，根据其函数返回值确定状态转移方向，在下一次循环时访问新的状态，并重复上述过程，直到到达结束状态。