(Finite State Machine) par AngelStreet

Les machines à états finis aussi appelés machines à nombre fini d'états, machines d'états ou automates finis, sont des outils abstraits de conceptualisation (aussi appelé modèle de conception ou design pattern) mathématique et informatique. Ils sont utilisés dans divers domaines dont l’électronique, la robotique et la programmation. Les automates sont souvent utilisés afin de modéliser des problèmes complexes où il existe un nombre fini de possibilités.

“Une machine à état est un comportement qui spécifie une séquence d'états qu'un objet traverse pendant sa durée de vie, en réponse aux événements et aux réponses qu’un objet donné donne à ces événements.”,
Kendall Scott. 2006. http://dico.developpez.com/html/2799-Conception-machine-a-etat.php

Une machine d’état est une structure logique qui permet de spécifier des états et d’établir les conditions et les actions à effectuer pour passer d’un état à un autre. (http://fr.wikipedia.org/wiki/Diagramme_%C3%A9tats-transitions)

Une machine d’état se compose essentiellement des éléments suivants:

• • États (Un élément de départ et un nombre quelconque d’éléments d’arrivé)
• • Actions (ou fonctions)
• • Évènements
• • Transition

• • Les états déterminent le contexte dans lequel sont exécutes les actions. On ne peut être que dans un seul état à la fois.
• • Les actions représentent le travail à réaliser selon les états.
• • Les évènements déterminent lorsqu’il faut réaliser les actions.
• • Les transitions déterminent comment passer d’un état à un autre

(http://lamsonproject.org/docs/introduction_to_finite_state_machines.html)

Une machine d'état est un concept théorique. On appellera machine d'état, la modélisation d'une situation concrète, d'un problème, d'une structure, d'un système électronique ou informatique sous la forme d'états, d'actions, d'évènements et de transitions. Une machine d'état est généralement représentée sous la forme d'un diagramme de transition.

Pour une définition plus complète visiter le lien ci-dessous :
http://laurent-audibert.developpez.com/Cours-UML/html/Cours-UML029.html

(extrait de l'article Automates finis par Jean-Eric Pin)
“Un passeur doit faire passer d’une rive a l’autre un loup, une chevre et une salade. Toutefois, son bateau ne peut transporter qu’un seul passager en dehors de lui-meme. Bien entendu, il ne peut laisser le loup et la chevre seuls sans surveillance, sinon le loup mangera la chevre. Meme chose pour le couple chevre-salade, car la chevre reve de manger la salade. Pouvez-vous aider le passeur ?” (Exemple aussi présent dans le jeu Professeur Layton sur Nintendo DS)

Pour résoudre cette énigme il est possible d'utiliser une machine d'état.

• • On peut définir les états par la présence des protagonistes sur la rive opposée( ou similairement la rive d'origine). Les états possibles sont donc les suivants:
• • N/A: aucun protagoniste sur la rive opposée
• • S: Salade sur la rive opposée
• • C: Chèvre sur la rive opposée
• • L: Loup sur la rive opposée
• • P: Passeur sur la rive opposée
• • Et toutes les combinaisons SC, SL, SP, CL, CP, SCL, SCP, CLP, SCLP

Nous avons donc 14 états

• • Les actions possibles sont les suivantes:
• • Traverser seul P
• • Traverser avec le loup L
• • Traverser avec la chèvre C
• • Traverser avec la salade S

• • Les évènements sont déclenchés par la personne qui tente de réaliser l'énigme. Elle déclenche l'action a effectuée.

• • Les transitions sont les passages d'une rive à un autre (0/P, 0/SP, 0/CP, 0/LP, P/SP, P/0, SP/0 etc…)

Une machine d'état peut être représentée par un diagramme de transition. Les deux solutions possibles sont représentés par le diagramme de transition ci-dessous:

Généralement une machine d'état est programmée intuitivement de manière conditionnelle dans une seule et même classe. Il est cependant essentiel pour des systèmes complexes de séparer les états dans des classes différentes afin faciliter l'évolution et la maintenance du code.

Deux états: Allumée ou Éteinte (lightIsOn / lightIsOff) Deux actions: Allumer ou Éteindre la lumière (switchOn ,switchOff) Un évènement: Appuyer sur l’interrupteur (key.isDown) Deux transitions: Allumée/Éteindre et Éteinte→Allumée

if (key.isDown && lightIsOn )      switchOff() ;
else if (key.isDown && lightIsOff) switchOn() ;

Lorsqu'une machine est composée d'un nombre important d'états, utiliser des if et/ou des switch pour coder une machine d'états n'est pas suffisant. Afin d'éviter les classes surchargées de milliers de lignes de codes, il devient nécessaire d'organiser le code en plusieurs classes.

(extrait du cours Informatique industrielle : Les automates par Jacques Weber / Souhil Megherbi)

“Un digicode est constitué d’un clavier à 16 touches qui constitue l’organe d’entrée d’un automate dont l’unique sortie commande l’ouverture d’une porte. Nous nous restreindrons à un digicode rudimentaire dans lequel le code secret est fixé une fois pour toutes, sans modification possible. Imaginons, par exemple, que l’ouverture de la porte soit obtenue en fournissant le code C94 (comme cachan + département). Évidemment l’automate doit être informé du fait que l’utilisateur a ouvert la porte, c’est le rôle du signal « ouverte ». ”

Le travail de l’automate peut être résumé par le diagramme suivant :

Dans l'exemple du digicode à trois chiffres, utiliser des if imbriqués reste raisonnable mais on peut déjà réaliser à quel point le code va se complexifier si on choisit de créer un digicode à 5 ou 6 chiffres.

var etat:int=0;

if (key.isDown){
 if (etat==0){
   if(key.keyCode == C){
     etat=1;
   }else{
     etat = 0;
   }
  }else if (etat==1){
   if(key.keyCode == 9){
     etat=2;
   }else{
     etat = 0;
   }
  }else if (etat==2){
   if(key.keyCode == 4){
     ouverte();
   }else{
     etat = 0;
   }
  }
}

Voici un exemple de structure utilisé pour programmer une machine d’état en POO (inspiré de RichardLord) :

• - Une classe FiniteMachineState qui stocke les états et définit les transitions d’un état à un autre.
• - Une interface IEtat qui défini les methodes Enter, Update et Exit qui sont les actions à effectuer.
• - Une classe State implémentant l’interface IEtat.
• - Plusieurs classes Etats qui hérite de la classe State.

Chaque état est indépendant.
Les évènements(appui sur une touche) peuvent déclencher des actions(ouvrir la porte) dans certaines conditions et/ou peuvent entraîner des transitions(State1/State2, State1/State3, State2/State1, State2,State3,State3/State1).

MachinesEtats est la classe principale définit comme application par défault (DocumentClass) Elle instancie la classe FiniteStateMachine qui stocke les états, définit l'état initial et l'état actuel, et enfin gère les transitions. Dans notre exemple du digicode on se doit de définir les 3 états avec l'Etat1 comme état initial. Puis on ajoute un écouteur clavier pour gérer les évènements.

private function _start():void {

//-- Instanciation de la machine d'états
  _fsm = new FiniteStateMachine();		

//-- On ajoute les 3 états à la machine  ---------------
  _fsm.addState("State1", new State1(_fsm));
  _fsm.addState("State2", new State2(_fsm));
  _fsm.addState("State3", new State3(_fsm));

//On ajoute un écouteur d'évènements clavier
  addEventListener(KeyboardEvent.KEY_DOWN,_onKeyDown,false,0,true);
}
//Lors de l'appui sur une touche du clavier on appel la fonction onKeyDown de l'état en cours
private function _onKeyDown($evt:KeyboardEvent):void {
  _fsm.currentState.onKeyDown($evt);
  _dynamicTF.text = $evt.keyCode.toString(); //Affiche dans un textField la touche appuyée
}

IState est l' interface de base

public interface IState{
  function enter($previousState:State):void; 	// called on entering the state
  function exit($nextState:State):void; 	// called on leaving the state
  function update():void;	// called while in the state
  function get finiteStateMachine():FiniteStateMachine;
  function set finiteStateMachine($finiteStateMachine:FiniteStateMachine):void;
}

IDigiCodeState est l'interface spécialement crée pour le tutoriel. Elle définit l'action suite à l'évènement keyDown

import flash.events.KeyboardEvent;
public interface IDigiCodeState{
  function onKeyDown($evt:KeyboardEvent):void; 	// called on keydown event
}

State est la classe abstraite implémentant les deux interfaces

import flash.events.KeyboardEvent;
	
	public class State implements IState, IDigiCodeState{
		protected var _finiteStateMachine:FiniteStateMachine = null;
		
		public function State(fms:FiniteStateMachine=null):void{
			_initVar(fms)
		}
		//------ Init Var ------------------------------------
		private function _initVar(fms:FiniteStateMachine=null):void {
			_finiteStateMachine = fms;
		}
		//------ Set FSM ------------------------------------
		public function set finiteStateMachine($finiteStateMachine:FiniteStateMachine):void{
			_finiteStateMachine=$finiteStateMachine;
		}
		//------ Get FSM ------------------------------------
		public function get finiteStateMachine():FiniteStateMachine{
			return _finiteStateMachine;
		}
		//------ On Key Down ------------------------------------
		public function onKeyDown($evt:KeyboardEvent):void {
		}
		//------ Enter ------------------------------------
		public function enter($previousState:State):void {
		}
		//------ Enter ------------------------------------
		public function update():void {
		}
		//------ Exit ------------------------------------
		public function exit($nextState:State):void {
		}
	}

State1 est l'état initial: Aucun chiffre entré

import flash.events.KeyboardEvent;
  public class State1 extends State{  //hérite de la classe State		
    public function State1($fms:FiniteStateMachine=null){
      super($fms);
    }
    //------ On Key Down ------------------------------------
    public override function onKeyDown($evt:KeyboardEvent):void {
      if($evt.keyCode == 67){ //67 is the keycode for  C
        trace("Transition de State1 à State2");
	_finiteStateMachine.changeStateByName("State2");
      }else{
	trace("Rester en State1");
      }
    }
  }

State2: est le second état: Un chiffre entré

import flash.events.KeyboardEvent;
  public class State2 extends State{//hérite de la classe State	
    public function State2($fms:FiniteStateMachine=null){
      super($fms);
    }
    //------ On Key Down ------------------------------------
    public override function onKeyDown($evt:KeyboardEvent):void {
      if($evt.keyCode == 57){  //57 is the keycode for  9
	trace("Transition de State2 à State3");
	  _finiteStateMachine.changeStateByName("State3");
	}else{
	  trace("Retour en State1");
	  _finiteStateMachine.changeStateByName("State1");
	}
      }
   }

State3 est le dernier état: Deux chiffres entrés

import flash.events.KeyboardEvent;
  public class State3 extends State{  //hérite de la classe State	
    public function State3($fms:FiniteStateMachine=null){
      super($fms);
    }
    //------ On Key Down ------------------------------------
    public override function onKeyDown($evt:KeyboardEvent):void {
      if($evt.keyCode == 52){  //52 is the keycode for  4
        _open()
      }else{
         trace("Return to State1");
      }
      _finiteStateMachine.changeStateByName("State1");
    }
    //------ Action Open ------------------------------------
    private function _open():void {
      trace("Porte Ouverte"); 	//Trace Door Open
      trace("Retour en State1");
      _finiteStateMachine.changeStateByName("State1"); //Go back to initial state
    }
}

Une machine d'état est la conceptualisation d'une situation, d'un système ou d'un problème sous la forme d'états, d'actions, de transitions et d'évènements.
On peut ainsi dire que si il est possible de représenter une structure sous la forme d'états, d'actions, de transitions et d'évènements, alors cette représentation ou conceptualisation est une machine d'état.

Pour aller plus loin, le site active.tutplus présente de manière graphique le cas plus complexe d’une voiture. Dans cet exemple, les machines d’états sont très utiles pour organiser le code et ainsi faciliter la maintenance.

- Richard Lord: Blog
- ActiveTutsPLus: Tutorial