Comment implémenter un FSM – Machine à états finis en Java

Le cœur d’une machine à états est la table de transition, qui prend un état et un symbole (ce que vous appelez un événement) dans un nouvel état. C’est juste un tableau à deux index d’états. Pour des raisons de sécurité et de sécurité, déclarez les états et les symboles comme des énumérations. J’ajoute toujours un membre “length” (spécifique à la langue) pour vérifier les limites des tableaux. Lorsque j’ai codé des FSM à la main, je formate le code au format ligne et colonne avec un quadrillage blanc. Les autres éléments d’une machine d’état sont l’état initial et l’ensemble des états acceptants. L’implémentation la plus directe de l’ensemble des états acceptants est un tableau de booléens indexés par les états. En Java, cependant, les énumérations sont des classes et vous pouvez spécifier un argument “accepting” dans la déclaration pour chaque valeur énumérée et l’initialiser dans le constructeur pour l’énumération.

Pour le type de machine, vous pouvez l’écrire en tant que classe générique. Il faudrait deux arguments de type, un pour les états et un pour les symboles, un argument de tableau pour la table de transition, un seul état pour l’initiale. Le seul autre détail (bien qu’il soit critique) est que vous devez appeler Enum.ordinal () pour obtenir un entier adapté à l’indexation du tableau de transition, car il n’existe pas de syntaxe permettant de déclarer directement un tableau avec un index d’énumération être).

Pour préempter un problème, EnumMap ne fonctionnera pas pour la table de transition, car la clé requirejse est une paire de valeurs d’énumération, pas une seule.

 enum State { Initial( false ), Final( true ), Error( false ); static public final Integer length = 1 + Error.ordinal(); final boolean accepting; State( boolean accepting ) { this.accepting = accepting; } } enum Symbol { A, B, C; static public final Integer length = 1 + C.ordinal(); } State transition[][] = { // ABC { State.Initial, State.Final, State.Error }, { State.Final, State.Initial, State.Error } }; 

Hmm, je suggère que vous utilisiez Flyweight pour implémenter les états. Objectif: éviter la surcharge de mémoire d’un grand nombre de petits objects. Les machines d’état peuvent devenir très, très grandes.

http://en.wikipedia.org/wiki/Flyweight_pattern

Je ne suis pas sûr de voir la nécessité d’utiliser l’état du modèle de conception pour implémenter les nœuds. Les nœuds d’une machine d’état sont sans état. Ils correspondent simplement au symbole d’entrée actuel aux transitions disponibles de l’état actuel. C’est-à-dire, à moins d’avoir complètement oublié comment ils fonctionnent (ce qui est une possibilité certaine).

Si je le codais, je ferais quelque chose comme ceci:

 interface FsmNode { public boolean canConsume(Symbol sym); public FsmNode consume(Symbol sym); // Other methods here to identify the state we are in } List input = getSymbols(); FsmNode current = getStartState(); for (final Symbol sym : input) { if (!current.canConsume(sym)) { throw new RuntimeException("FSM node " + current + " can't consume symbol " + sym); } current = current.consume(sym); } System.out.println("FSM consumed all input, end state is " + current); 

Que ferait Flyweight dans ce cas? Eh bien, sous le FsmNode, il y aurait probablement quelque chose comme ceci:

 Map> fsm; // A state is an Integer, the transitions are from symbol to state number FsmState makeState(int stateNum) { return new FsmState() { public FsmState consume(final Symbol sym) { final Map transitions = fsm.get(stateNum); if (transisions == null) { throw new RuntimeException("Illegal state number " + stateNum); } final Integer nextState = transitions.get(sym); // May be null if no transition return nextState; } public boolean canConsume(final Symbol sym) { return consume(sym) != null; } } } 

Cela crée les objects State sur la base du besoin d’utiliser, il vous permet d’utiliser un mécanisme sous-jacent beaucoup plus efficace pour stocker la machine d’état réelle. Celui que j’utilise ici (Carte (Entier, Carte (Symbole, Entier))) n’est pas particulièrement efficace.

Notez que la page Wikipedia se concentre sur les cas où de nombreux objects assez similaires partagent les mêmes données, comme c’est le cas dans l’implémentation Ssortingng en Java. À mon avis, Flyweight est un peu plus général et couvre toute création à la demande d’objects avec une durée de vie courte (utilisez plus de CPU pour économiser sur une structure de données sous-jacente plus efficace).

EasyFSM est une bibliothèque Java dynamic pouvant être utilisée pour implémenter un FSM.

Vous pouvez trouver la documentation pour la même chose à: Machine à états finis en Java

Vous pouvez également télécharger la bibliothèque à l’adresse suivante: Bibliothèque Java FSM: DynamicEasyFSM

Considérez la bibliothèque Java facile et légère EasyFlow . De leurs documents:

Avec EasyFlow, vous pouvez:

• implémenter une logique complexe mais garder votre code simple et propre
• gérer les appels asynchrones avec facilité et élégance
• éviter les access simultanés en utilisant une approche de programmation pilotée par les événements
• éviter l’erreur StackOverflow en évitant la récursivité
• simplifier la conception, la programmation et les tests d’applications Java complexes

Vous pouvez implémenter Finite State Machine de deux manières différentes.

Option 1:

Machine à états finis avec un stream de travail prédéfini : recommandé si vous connaissez tous les états à l’avance et que la machine à états est presque fixe sans aucune modification à l’avenir

1. Identifiez tous les états possibles dans votre application

2. Identifier tous les événements de votre application

3. Identifier toutes les conditions de votre application, ce qui peut conduire à une transition d’état

4. L’occurrence d’un événement peut provoquer des transitions d’état

5. Construisez une machine à états finis en décidant d’un workflow d’états et de transitions.

   Par exemple, si un événement 1 se produit à l’état 1, l’état sera mis à jour et l’état de la machine peut toujours être à l’état 1.

   Si un événement 2 se produit à l’état 1, lors d’une évaluation de certaines conditions, le système passera de l’état 1 à l’état 2.

Cette conception est basée sur les modèles d’ état et de contexte .

Jetez un coup d’œil aux classes de prototypes Finite State Machine .

Option 2:

Arbres comportementaux: recommandés en cas de modifications fréquentes du stream de travail de la machine à états. Vous pouvez append dynamicment un nouveau comportement sans casser l’arborescence.

La classe Task de base fournit une interface pour toutes ces tâches, les tâches leaf sont celles qui viennent d’être mentionnées et les tâches parent sont les nœuds intérieurs qui décident de la prochaine tâche à exécuter.

Les tâches n’ont que la logique dont elles ont besoin pour faire ce qui est demandé, toute la logique de décision indiquant si une tâche a démarré ou non, si elle doit être mise à jour, si elle a abouti, etc. est regroupée dans TaskController classe, et ajouté par composition.

Les décorateurs sont des tâches qui «décorent» une autre classe en la recouvrant et en lui donnant une logique supplémentaire.

Enfin, la classe Blackboard est une classe appartenant à l’IA parent à laquelle chaque tâche a une référence. Il fonctionne comme une firebase database de connaissances pour toutes les tâches de feuille

Regardez cet article de Jaime Barrachina Verdia pour plus de détails

Je conçois et implémente un exemple simple de machine à états finis avec Java.

IFiniteStateMachine : l’interface publique pour gérer la machine à états finis
tels que l’ajout de nouveaux états à la machine à états finis ou le transit vers les états suivants par
actions spécifiques.

 interface IFiniteStateMachine { void setStartState(IState startState); void setEndState(IState endState); void addState(IState startState, IState newState, Action action); void removeState(Ssortingng targetStateDesc); IState getCurrentState(); IState getStartState(); IState getEndState(); void transit(Action action); } 

IState : l’interface publique pour obtenir des informations relatives à l’état
tels que le nom de l’état et les mappages aux états connectés.

 interface IState { // Returns the mapping for which one action will lead to another state Map getAdjacentStates(); Ssortingng getStateDesc(); void addTransit(Action action, IState nextState); void removeTransit(Ssortingng targetStateDesc); } 

Action : la classe qui provoquera la transition des états.

 public class Action { private Ssortingng mActionName; public Action(Ssortingng actionName) { mActionName = actionName; } Ssortingng getActionName() { return mActionName; } @Override public Ssortingng toSsortingng() { return mActionName; } } 

StateImpl : l’implémentation d’IState. J’ai appliqué une structure de données telle que HashMap pour conserver les mappages État-Action.

 public class StateImpl implements IState { private HashMap mMapping = new HashMap<>(); private String mStateName; public StateImpl(String stateName) { mStateName = stateName; } @Override public Map getAdjacentStates() { return mMapping; } @Override public Ssortingng getStateDesc() { return mStateName; } @Override public void addTransit(Action action, IState state) { mMapping.put(action.toSsortingng(), state); } @Override public void removeTransit(Ssortingng targetStateDesc) { // get action which directs to target state Ssortingng targetAction = null; for (Map.Entry entry : mMapping.entrySet()) { IState state = entry.getValue(); if (state.getStateDesc().equals(targetStateDesc)) { targetAction = entry.getKey(); } } mMapping.remove(targetAction); } } 

FiniteStateMachineImpl : Implémentation de IFiniteStateMachine. J’utilise ArrayList pour garder tous les états.

 public class FiniteStateMachineImpl implements IFiniteStateMachine { private IState mStartState; private IState mEndState; private IState mCurrentState; private ArrayList mAllStates = new ArrayList<>(); private HashMap> mMapForAllStates = new HashMap<>(); public FiniteStateMachineImpl(){} @Override public void setStartState(IState startState) { mStartState = startState; mCurrentState = startState; mAllStates.add(startState); // todo: might have some value mMapForAllStates.put(startState.getStateDesc(), new ArrayList()); } @Override public void setEndState(IState endState) { mEndState = endState; mAllStates.add(endState); mMapForAllStates.put(endState.getStateDesc(), new ArrayList()); } @Override public void addState(IState startState, IState newState, Action action) { // validate startState, newState and action // update mapping in finite state machine mAllStates.add(newState); final Ssortingng startStateDesc = startState.getStateDesc(); final Ssortingng newStateDesc = newState.getStateDesc(); mMapForAllStates.put(newStateDesc, new ArrayList()); ArrayList adjacentStateList = null; if (mMapForAllStates.containsKey(startStateDesc)) { adjacentStateList = mMapForAllStates.get(startStateDesc); adjacentStateList.add(newState); } else { mAllStates.add(startState); adjacentStateList = new ArrayList<>(); adjacentStateList.add(newState); } mMapForAllStates.put(startStateDesc, adjacentStateList); // update mapping in startState for (IState state : mAllStates) { boolean isStartState = state.getStateDesc().equals(startState.getStateDesc()); if (isStartState) { startState.addTransit(action, newState); } } } @Override public void removeState(String targetStateDesc) { // validate state if (!mMapForAllStates.containsKey(targetStateDesc)) { throw new RuntimeException("Don't have state: " + targetStateDesc); } else { // remove from mapping mMapForAllStates.remove(targetStateDesc); } // update all state IState targetState = null; for (IState state : mAllStates) { if (state.getStateDesc().equals(targetStateDesc)) { targetState = state; } else { state.removeTransit(targetStateDesc); } } mAllStates.remove(targetState); } @Override public IState getCurrentState() { return mCurrentState; } @Override public void transit(Action action) { if (mCurrentState == null) { throw new RuntimeException("Please setup start state"); } Map localMapping = mCurrentState.getAdjacentStates(); if (localMapping.containsKey(action.toSsortingng())) { mCurrentState = localMapping.get(action.toSsortingng()); } else { throw new RuntimeException("No action start from current state"); } } @Override public IState getStartState() { return mStartState; } @Override public IState getEndState() { return mEndState; } } 

exemple :

 public class example { public static void main(Ssortingng[] args) { System.out.println("Finite state machine!!!"); IState startState = new StateImpl("start"); IState endState = new StateImpl("end"); IFiniteStateMachine fsm = new FiniteStateMachineImpl(); fsm.setStartState(startState); fsm.setEndState(endState); IState middle1 = new StateImpl("middle1"); middle1.addTransit(new Action("path1"), endState); fsm.addState(startState, middle1, new Action("path1")); System.out.println(fsm.getCurrentState().getStateDesc()); fsm.transit(new Action(("path1"))); System.out.println(fsm.getCurrentState().getStateDesc()); fsm.addState(middle1, endState, new Action("path1-end")); fsm.transit(new Action(("path1-end"))); System.out.println(fsm.getCurrentState().getStateDesc()); fsm.addState(endState, middle1, new Action("path1-end")); } } 

Exemple complet sur Github