有限状态机FSM1 组合逻辑和时序逻辑组合逻辑和时序逻辑是数字电路设计中的两个非常重要的概念。数字电路通过实现这两个概念搭建了冯诺依曼体系结构布尔代数数字逻辑电路进而模拟了几乎整个物理世界的运行规律。组合逻辑组合逻辑不涉及时序只涉及“瞬时的”布尔运算——当前时刻的逻辑运算不依赖任何历史状态——对应冯诺依曼体系结构中单个tick的逻辑计算。时序逻辑时序逻辑是组合逻辑的扩展具备记忆能力使得当前时刻或tick的逻辑运算可以依赖历史状态。有限状态机就是一种描述时序逻辑的建模语言。2 四要素四元组2.1 状态和迁移状态机最重要的两个概念是状态和状态迁移。状态用于描述某个时刻系统的特性可以是标量或者向量在状态迁移图中用节点Node表示。状态迁移用于描述各个状态之间的转换关系在状态迁移图中用边Edge表示。示意图如下[1]Tips: 状态迁移图是一个网状拓扑结构。2.2 事件和动作光有状态和状态迁移是不够的构建状态机的最终目的是和外界进行交互因此状态机必须设计输入和输出。输入对应事件的概念输出对应动作的概念。事件对应观测是被动的动作对应控制是主动的。为了提升状态机的应激能力和减少状态数量降低FSM的复杂性一般建模时选择Mealy Machine(即输出既和当前的状态相关也和当前的输入相关)Tips: 和Mealy Machine相对的是Moore Machine可自行查阅相关资料。为了进一步减少状态数量从是否会触发状态迁移划分可以将事件分为导致状态迁移的事件和常规事件不会导致状态转移。常规事件的作用是使得FSM在当前状态下不进行状态切换时仍具备对事件的响应能力。严格来讲常规事件的响应不属于状态机研究的范畴但是从实用角度来讲却是必要的见最佳实践章节说明。这里为什么称作事件而没有称作条件大部分状态机中状态跳转使用是Condition这个概念即满足一定的条件后进行跳转呢因为状态 事件 条件。用概率建模状态机的迁移过程就很容易看到这点状态机的迁移概率可以表示为P ( s t 1 ∣ s t , e t ) (2.1) P(s_{t1} \mid s_t, e_t) \tag{2.1}P(st1​∣st​,et​)(2.1)其中s t s_tst​是当前状态e t e_tet​是当前事件在条件概率中这两者都属于条件。3 优缺点3.1 优点建模直观易懂易实施。3.2 缺点维护和扩展性差由于是网状拓扑结构当状态增多时不好维护复用性由于状态间可见因此单个状态并不是完全独立的模块因此很难复用。3.3 使用条件一个阶段/任务可能会持续比较长时间不能在一个周期/tick内完成比如该阶段内需要等待与协调工作当需要明确当前所处的状态时比如人机交互场景需要让用户知道当前所处的状态。4 最佳实践状态机最大的问题就是拓扑结构复杂加入和删除一个节点都比较困难。为了缓解这个问题从以下多个途径进行解决。最终实现对FSM的扬长避短。4.1 配置工厂用配置文件对FSM进行管理各个状态以及状态间的迁移一目了然。在配置文件中配置需要实例化的类/子类是工厂设计模式的最佳实现方案。下面的json配置文件是一个不完整示例详细解释见注释。{NOA_STATES:# 根Key,用于校验加载的该配置文件是否是目标配置文件[{StateName:Start,# 初始状态类名该名称需要和C代码中的类名保持一致否则实例化时报错Parent:*,# 这里的*代表该状态没有父状态Transition:[# 描述状态迁移定义{Event:noa_start,# 事件名称导致状态迁移的事件注意事件名称需要和代码中保持一致Priority:0,# 事件优先级提升对重要事件的响应能力同时防止歧义切换导致的状态冲突Key:-Pending,Target:Pending# 目标状态}]},...{StateName:Driving,# 状态名和C代码中的类名保持一致Parent:*,Transition:[# 一个状态下可以有多个迁移路径{Event:cancel_button_pressed,Priority:100,Key:-Failed_CauseByUser,Target:Failed_CauseByUser},{Event:moving_with_brake_pedal_pressed,Priority:100,Key:-Failed_CauseByEvent,Target:Failed_CauseByEvent},{Event:steering_torque_exceeds_limit,Priority:100,Key:-Failed_CauseByEvent,Target:Failed_CauseByEvent# 即使是迁移到同一个状态也可以是因为不同的事件},{Event:steering_angle_exceeds_limit,Priority:100,Key:-Failed_CauseByEvent,Target:Failed_CauseByEvent}]},{StateName:Driving_Active,# Driving状态下的子状态ActiveParent:Driving,# 父状态是DrivingTransition:[{Event:guardian,Priority:1,Key:-Failed_CauseByEvent,# 任意子状态间也可以直接迁移Target:Failed_CauseByEvent},{Event:radar_data_lost,Priority:1,Key:-Failed_CauseByEvent,Target:Failed_CauseByEvent}]}]}4.2 状态机的分离和分层状态粒度的把控和功能模块划分需要遵循的原则是一致的需要进行权衡。状态数目太少每个状态内的逻辑就会变得复杂状态数目太多状态间的迁移和通信又会变得十分复杂。最佳实践是先采用状态的分离和分层策略。4.2.1 状态机的分离虽然大家都在这么做但很少提到这个概念。状态机的分离就是把两个业务模块完全拆开各自用状态机进行建模两个模块间的状态不涉及相互迁移完全分离。比如决策模块的状态机和控制模块的状态机之间的关系。4.2.2 状态机的分层分层有限状态机HFSM也称为状态图是为弥补有限状态机FSM的缺点而建立的。在HFSM中状态可以包含一个或多个子状态。包含两个或两个以上子状态的父状态成为超状态。在HFSM中一种设计是不允许跨超状态的子状态之间的直接跳转另外一种则允许——这两种设计有利有弊需要根据应用场景进行权衡——如果对系统的“应激性”要求较高则选择支持跨超状态的子状态之间的直接跳转在一个tick内就可以完成 子状态A-父状态A-父状态B-子状态B 的跳转以及相关的处理否则选择另一种以降低连接的复杂性。4.3 状态模式与事件驱动最简单也最容易想到的一种FSM实现方式就是定义一个state_flag,然后用if-else进行状态的判断与切换。但是这种方式的可读性和扩展性会很差会凸显加重FSM的缺点。设计模式中的状态模式将面向状态此时状态为对象编程进行了完美诠释。下图为状态模式的UML图[2]每个状态用一个类进行实现每个类覆写父类中的方法在不同的状态下有不同的响应。State虚类的定义示例如下classState{public:/** * brief State 类的构造函数 * * 初始化 State 对象设置状态名称、状态 ID 和父状态。 * * param [in]state_name 状态名称 * param [in]state_id 状态 ID * param [in/out]node_config 节点配置信息用于在状态之间传递数据 * param [in]parent_state 父状态对象的共享指针 */State(conststd::stringstate_name,uint64_tstate_id,NodeConfigurationnode_config,std::shared_ptrStateparent_statenullptr);~State()overridedefault;/** * brief 更新状态 * * 在状态机中更新当前状态并处理传入的事件。 * 如果有子状态则更新子状态。 * 会被周期性执行。每次被周期性执行时event有可能会不同。 * * param [in]event 事件对象 * * return 如果状态更新成功则返回 true否则返回 false */boolonUpdate(constevent_pulse::Eventevent);/** * brief 状态进入时的处理函数 * * 当状态机进入当前状态时调用该函数进行状态进入时的处理。 * 如果有子状态则进入子状态。 * param [in]event 事件对象 */voidonEntry(constevent_pulse::Eventevent);/** * brief 状态退出时的处理函数 * * 当状态机退出当前状态时调用该函数进行状态退出时的处理。 * * param [in]event 事件对象 */voidonExit(constevent_pulse::Eventevent);/** * brief 更新状态 * * 根据传入的事件更新当前状态。会被周期性的执行。每次被周期性执行时event有可能会不同。 * * param [in]event 事件对象 * * return 如果状态更新成功则返回true否则返回false在此示例中始终返回true */virtualboolstateUpdate(constevent_pulse::Eventevent);/** * brief 进入状态 * * 当状态机进入当前状态时会调用此方法。进入状态时只被执行一次。 * * param [in]event 事件对象 * * return 如果状态进入成功则返回true否则返回false在此示例中始终返回true */virtualboolstateEntry(constevent_pulse::Eventevent);/** * brief 退出状态 * * 当状态机从当前状态退出时会调用此方法。退出状态时只被执行一次。 * * param [in]event 事件对象 * * return 如果状态退出成功则返回true否则返回false在此示例中始终返回true */virtualboolstateExit(constevent_pulse::Eventevent);...}状态模式表现出的“多态”在不同状态下对同一事件会产生不同的响应。也就是说事件的生成和处理是可以分离的类似生产者-消费者模式。如下图所示在状态模式的基础上引入事件驱动的编程范式。在每个状态内会对相应的事件做对应的处理。处理分为两层含义对于任意事件可以在状态内部写一个Process方法对接收的事件进行处理对于导致状态迁移的事件除了Process处理还会进行状态迁移。需要注意的是为了防止状态死锁的产生不允许状态处理自己产生的事件。4.4 状态机的迁移4.4.1 事件优先级(1)导致状态迁移事件的优先级为了防止状态冲突产生需要对导致状态迁移的事件设置优先级并放入优先级队列。每个周期内选取优先级队列中最高优先级的事件并触发状态切换,然后清空该队列这个操作体现了马尔科夫性。(2)常规事件的优先级在每个状态内需要响应产生的所有事件而且必须在一个周期内完成如果完不成就需要把Process拆分成异步任务类似PCIe中的Split总线传输方式。一般来说一个周期tick是非常短的例如100ms但是为了更快速的响应高优事件比如刹车事件能提前10ms也是值得的因此需要对所有事件设置优先级,以便优先处理高优事件。Tips:导致状态迁移的事件其实是同时有两个“身份”的会被同时进入状态迁移事件的优先级队列和常规事件的优先级队列。4.4.2 一个周期两次迁移从事件产生的来源划分可以将事件划分为外部事件和内部事件。这样定义不光是为了清晰而是可以更方便实现“状态不可以处理自己产生的内部事件”约束以防止状态死锁的产生。因为有了上述约束内部产生的事件必须放在下一个状态中进行处理。例如下述的事件处理代码中步骤3一定要排在步骤2后面进行。至于步骤4可以省略省略之后的效果就是3步骤产生的状态切换事件导致的状态切换发生在下一个周期添加步骤4则可保证更优的更及时的状态切换。此外探讨步骤1和2步骤3和4之间顺序是否可以颠倒的问题——先进行事件处理Action再进行状态切换Transition更符合思维习惯防止出现目标状态中未定义对事件的处理该顺序不是强制性的。bool EventManager::ProcessEvents(const std::shared_ptrStateContext stateContext) { //0.process abnormal events ProcessAbNormalEvent(stateContext); //对异常事件的特殊处理和状态机不相关 //1.process normal event (outer) ProcessNormalEvent(stateContext, normal_outer_event_queue_); // 在当前状态处理外部事件 //2.process state-switch event (outer inner events) SwitchState(stateContext); // 根据外部事件和步骤1产生的内部事件进行状态切换切换时会执行当前状态的Exit函数和目标状态的Entry函数 //3.process normal event (inner events) ProcessNormalEvent(stateContext, normal_inner_event_queue_); // 在当前状态有可能已经切换过一次状态处理步骤2产生的内部事件 //4.process state-switch event (inner events) SwitchState(stateContext); // 根据第3步产生的内部事件进行状态切换 return true; }4.4.3 支持子状态间跳转示例代码如下。bool StateContext::DoStateSwitch(const std::shared_ptrState target_state, const event_pulse::Event event) { std::shared_ptrState state root_state_; if (target_state-getParent()) {// 处理目标状态有父状态的情况 // switch in current state branch(处理目标状态与当前状态同属一个父状态的情况需要注意的是目前不支持目标状态与当前状态同属一个族系但是父状态不同的情况——例如“叔叔状态”切换到“侄子状态”暂不支持。因为设置超过2层的HFSM逻辑会异常复杂不建议这么使用。) std::shared_ptrState in_state root_state_; do { if (in_state target_state-getParent()) { if (in_state-getChild()) { in_state-getChild()-onExit(event); } in_state-setChild(target_state); target_state-onEntry(event); return true; } in_state in_state-getChild(); } while (in_state); // switch skipping state branch处理目标状态与当前状态不同属于一个族系的情况 std::shared_ptrState tar_child target_state; std::shared_ptrState tar_parent tar_child-getParent(); //tar_parent-setChild(tar_child); while (true) { if (tar_parent) { tar_parent-setChild(tar_child); } else { root_state_-onExit(event); root_state_ tar_child; root_state_-onEntry(event); return true; } tar_child tar_parent; tar_parent tar_child-getParent(); } } else { //处理目标状态没有父状态的情况 state-onExit(event); root_state_ target_state; root_state_-setChild(nullptr); root_state_-setParent(nullptr); root_state_-onEntry(event); } return true; }4.4.4 子状态继承父状态的动作如下述代码所示HFSM中的父子关系和C中的继承有一点点区别——C中的子类可以“单独行动”但是HFSM中的子状态必须和父状态一起行动。void State::onEntry(const event_pulse::Event event) { if (!stateEntry(event)) { //进入状态时先执行父状态的动作 //std::cerr State entry failed!; GT-s20587 } if (child_state_) {// 再执行子状态的动作。这里有一个隐含的技巧父状态执行过的动作子状态不用再重复实现——相当于继承了父状态的动作因此对于所有的子状态来说公共动作可以抽取出来放到父状态中实现 child_state_-onEntry(event); } } bool State::onUpdate(const event_pulse::Event event) { stateUpdate(event); if (child_state_) { if (!child_state_-onUpdate(event)) { AWARN child state onUpdate Failed!; return false; } } return true; } void State::onExit(const event_pulse::Event event) { if (child_state_) { child_state_-onExit(event); } setChild(nullptr); if (!stateExit(event)) { //std::cerr State exit failed!; GT-s20587 } }参考文献Behavior Trees in Robotics and AI.大话设计模式。