运动控制——强大的状态机工具

1.1 状态机的概念

      状态机&＃xff0c;通俗的讲可以理解为一种建模方法。当一个逻辑非常复杂的程序放在面前&＃xff0c;是非常令人头大的&＃xff0c;使用状态转移图&＃xff08;是一个有向图形&＃xff0c;包括各节点和状态转移条件&＃xff09;可以很好的梳理流程。以博主的理解&＃xff0c;实现状态转移图的模块我们便可以称之为状态机。

      在程序中&＃xff0c;一个状态机通常包括一个起始状态、一组状态集以及多个相应的状态转移条件。

      构建状态转移图时&＃xff0c;需要注意每个节点对应一个状态&＃xff0c;在这些节点中需要有至少一个终态&＃xff0c;当达到终态时状态机停止。一个好的状态机应该做到设计安全&＃xff08;不会进入未知状态或异常死循环&＃xff09;、清晰易懂、易维护。

      百度百科把状态机归纳为了4个要素&＃xff1a;即现态、条件、动作、次态。这样的归纳&＃xff0c;主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因&＃xff0c;“动作”和“次态”是果¹。

• 现态&＃xff1a;是指当前所处的状态。
• 条件&＃xff1a;又称为“事件”&＃xff0c;当一个条件被满足&＃xff0c;将会触发一个动作&＃xff0c;或者执行一次状态的迁移。
• 动作&＃xff1a;条件满足后执行的动作。动作执行完毕后&＃xff0c;可以迁移到新的状态&＃xff0c;也可以仍旧保持原状态。动作不是必需的&＃xff0c;当条件满足后&＃xff0c;也可以不执行任何动作&＃xff0c;直接迁移到新状态。
• 次态&＃xff1a;条件满足后要迁往的新状态。“次态”是相对于“现态”而言的&＃xff0c;“次态”一旦被激活&＃xff0c;就转变成新的“现态”了。

      以人的健康情况我们来举个例子&＃xff0c;人有三个状态&＃xff1a;健康、感冒、康复中。触发的条件有淋雨、吃药打针、好好休息、多喝热水和感觉良好。

      假设初始状态处于健康状态下&＃xff0c;当淋雨后人会感冒。这时候我们有三种途径解决感冒这个问题&＃xff1a;吃药打针、好好休息、多喝热水。无论哪一种方法&＃xff0c;都能使人的状态由感冒转移到康复中。当人感觉到状态良好时&＃xff0c;感冒好了&＃xff0c;人也就又处于了健康状态。

注意

1. 在进行状态机建模时&＃xff0c;要区分“动作”和“状态”&＃xff0c;前者一旦执行完就结束了&＃xff0c;而后者如果没有条件触发&＃xff0c;则状态会一直持续下去。

2. 状态划分要完整

对于更形象的说明&＃xff0c;可参考博文《设计模式&＃xff1a;一目了然的状态机图》

1.2 状态机的思想

      关于状态机的思想&＃xff0c;百度文库中有一个特别形象的例子²&＃xff1a;

      网络上经常报道特级象棋大师车和多人一起下象棋&＃xff0c;采用的方式是“车轮战”。车轮战有两种方式&＃xff1a;&＃xff08;1&＃xff09;象棋大师先和甲开始下象棋&＃xff0c;直到有了结果&＃xff0c;然后才轮到乙和象棋大师对阵&＃xff0c;下完了之后&＃xff0c;然后是丙…&＃xff0c;一直到和最后一个人下完。&＃xff08;2&＃xff09;象棋大师先和A下一步棋&＃xff0c;然后再和B下一步棋&＃xff0c;然后再和C&＃xff0c;和…&＃xff0c;和所有人下完一遍后&＃xff0c;再回头从A开始&＃xff0c;一个人接一个人。

      很显然“车轮战”的第1种方式效率不如第2种方式效率高&＃xff0c;报道上的“车轮战”也是指的第2种方式。原因在于象棋大师的水平远远高于其他人&＃xff0c;如果采用第一种方式&＃xff0c;象棋大师下一步棋很快&＃xff0c;甲需要考虑很长时间才能落子&＃xff0c;象棋大师在和甲下棋的过程中&＃xff0c;其他人只能等待。如果采用第二种方式&＃xff0c;象棋大师和甲只下一步棋&＃xff0c;然后再和乙也下一步棋&＃xff0c;和所有人下完一步棋之后&＃xff0c;再从甲开始&＃xff0c;这样看起来是所有人都在下象棋&＃xff0c;效率自然远高于第一种方式。

      “车轮战”的第2种方式&＃xff0c;实际上就是程序中状态机的基本原理。程序中的多个任务可以看成是其他棋手&＃xff0c;CPU是象棋大师&＃xff0c;CPU在执行多个任务时&＃xff0c;不再是先执行任务1&＃xff0c;执行完任务1后&＃xff0c;再执行任务2&＃xff0c;而是把每个任务又划分出多个小任务&＃xff08;小任务中没有时间等待&＃xff09;&＃xff0c;CPU每次只执行每个任务中的小任务&＃xff0c;执行完任务1中的一个小任务后&＃xff0c;然后快速转向任务2中的小任务&＃xff0c;按照这种模式轮询下去&＃xff0c;由于CPU很快&＃xff08;象棋大师&＃xff09;&＃xff0c;整个程序中的任务都得到了实时的执行。任务中的小任务是按照任务的状态来划分的&＃xff0c;故称为“状态机”。

      状态机可分为有限状态机&＃xff08;FSM&＃xff09;、分层状态机&＃xff08;HFSM&＃xff09;&＃xff0c;其中有限状态机又可分为Moore状态机&＃xff08;输出只和状态有关而与输入无关&＃xff09;、Mealy状态机&＃xff08;输出不仅和状态有关而且和输入有关系&＃xff09;

      在实践中状态机有一个致命的缺点&＃xff0c;当状态一旦多了之后&＃xff0c;它的跳转就会变的不可维护³&＃xff0c;这时我们可以把状态进行分类&＃xff0c;把同类型的状态作为一个状态机&＃xff0c;然后使用一个更大的状态机去维护这些自状态机&＃xff0c;&＃xff0c;这时用到的便是分层状态机&＃xff0c;可以理解为状态机的嵌套&＃xff0c;如下图所示。

      关于以上几者&＃xff0c;博文《FSM&＃xff08;状态机&＃xff09;、HFSM&＃xff08;分层状态机&＃xff09;、BT&＃xff08;行为树&＃xff09;的区别》有更生动的例子可以参考。

      维护庞大数量的知识条目是个噩梦&＃xff0c;如果使用有限状态机(FSM)、分层有限状态机(HFSM)、决策树(Decision Tree)还不能满足你的使用要求&＃xff0c;这时试试Next-Gen AI的行为树(Behavior Tree)吧。

      状态机的实现由常见的几种实现方法⁴&＃xff1a;

1. 我们可以 在无限循环for(;;)或者while(1)中使用switch-case或if-else来实现简单的状态机&＃xff1b;
2. 使用二维状态表state-event实现&＃xff0c;该方法逻辑清晰&＃xff0c;但矩阵通常比较稀疏且维护麻烦&＃xff1b;
3. 用状态转移表stateTransfer Table实现&＃xff0c;数组大小等于状体转移边个数&＃xff0c;易扩展&＃xff1b;

3.1 switch-case结构的状态机的实现

      在程序的写法上&＃xff0c;有横着写和竖着写两种⁴&＃xff1a;

• 横着写&＃xff1a;在事件中根据当前的状态&＃xff0c;执行相应的操作&＃xff0c;完成相应的状态转换。

  //声明&＃xff1a;本代码转自 https://blog.csdn.net/zzz1014440164/article/details/79814160
//横着写
void event0func(void)
{switch(cur_state){case State0:action0;cur_state &＃61; State1;break;case State1:action1;cur_state &＃61; State2;break;case State2:action1;cur_state &＃61; State0;break;default:break;}
}void event1func(void)
{switch(cur_state){case State0:action4;cur_state &＃61; State1;break;default:break;}
}void event2func(void)
{switch(cur_state){case State0:action5;cur_state &＃61; State2;break;case State1:action6;cur_state &＃61; State0;break;default:break;}
}


• 竖着写&＃xff1a;在状态中判断事件&＃xff0c;并执行相应的操作&＃xff0c;完成相应的状态转换。

  //声明&＃xff1a;本代码转自 https://blog.csdn.net/zzz1014440164/article/details/79814160
//竖着写
switch(cur_state)
{case State0:if(event1){action0;cur_state &＃61; State1;}else if(event2){action4;cur_state &＃61; State1;}else if(event3){action5;cur_state &＃61; State2;}break;case State1:if(event1){action1;cur_state &＃61; State2;}else if(event3){action6;cur_state &＃61; State0;}break;case State2:if(event1){action3;cur_state &＃61; State0;}break;default:break;
}


      通常我们使用横着写的结构写&＃xff01;&＃xff01;&＃xff01;
      这是由于竖着写使用了if -else结构&＃xff0c;其中if语句隐含了优先级&＃xff0c;破坏可事件间的原有关系&＃xff08;各个时间应该同优先级&＃xff09;&＃xff0c;而且竖着写在结构上是顺序查询方式&＃xff08;查询事件&＃xff09;&＃xff0c;浪费大量的时间&＃xff0c;而且时间不可估算。

      对于横着写的方式&＃xff0c;因为在某个时间点上状态是唯一确定的&＃xff0c;在时间处理函数中通过switch语句可直接定位到相同状态&＃xff0c;执行时间也可以估算。这种方式比较直观&＃xff0c;程序执行效率较高。

3.2 状态转移表联合函数指针数组实现⁵

声明&＃xff1a;本节内容转自 https://blog.csdn.net/thisinnocence/article/details/47060285

      用枚举来定义状态和事件&＃xff0c;操作数据节点转移到目的状态用函数实现。枚举本身默认是从0开始的int类型&＃xff0c;利用这个特点将状态转移函数放到函数指针数组中与状态对应起来&＃xff0c;方便操作。这种实现方法易于扩展&＃xff0c;增加状态和事件都比较容易。

状态&＃xff1a;枚举类型
事件&＃xff1a;枚举类型
状态转移结构体&＃xff1a;{当前状态、事件、下个状态}&＃xff0c;定义一个全局数组来使用
状态变更函数&＃xff1a;到下个状态(放到数组中与状态枚举对应起来)

#include
using namespace std;typedef enum{OPENED,CLOSED,LOCKED,
} State;typedef enum{OPEN,CLOSE,LOCK,UNLOCK
} Event;typedef struct{State currentState;Event event;State NextState;
} StateTransfer;typedef struct{State state;int transferTimes;
}Door;StateTransfer g_stateTransferTable[]{{OPENED, CLOSE, CLOSED},{CLOSED, OPEN, OPENED},{CLOSED, LOCK, LOCKED},{LOCKED, UNLOCK, CLOSED},
};void toOpen(Door& door);
void toClose(Door& door);
void toLock(Door& door);
typedef void (*pfToState)(Door& door);
pfToState g_pFun[] &＃61; {toOpen, toClose, toLock}; //状态枚举值对应下标void toOpen(Door& door){door.state &＃61; OPENED;cout << "open the door!\n";
}void toClose(Door& door){door.state &＃61; CLOSED;cout << "close the door!\n";
}void toLock(Door& door){door.state &＃61; LOCKED;cout << "lock the door!\n";
}void transfer(Door& door,const Event event){for (int i &＃61; 0; i < sizeof(g_stateTransferTable)/sizeof(StateTransfer); &＃43;&＃43;i) {if(door.state &＃61;&＃61; g_stateTransferTable[i].currentState &&event &＃61;&＃61; g_stateTransferTable[i].event){g_pFun[g_stateTransferTable[i].NextState](door);door.transferTimes&＃43;&＃43;;cout << "transfer ok!\n";return;}}cout << "This event cannot transfer current state!!\n";return;
}void printDoor(const Door& door){string stateNote[] &＃61; {"opened","closed","locked"}; // 下标正好对应状态枚举值cout << "the door&＃39;s state is: " << stateNote[door.state] << endl;cout << "the door transfer times is: " << door.transferTimes << endl;
}int main(){Door door &＃61; {CLOSED, 0};printDoor(door);transfer(door, OPEN);printDoor(door);transfer(door, LOCK);printDoor(door);transfer(door, CLOSE);printDoor(door);return 0;
}


3.3 其他