Come implementare un FSM – Finite State Machine in Java

Ho qualcosa da fare per il lavoro e ho bisogno del tuo aiuto. Vogliamo implementare un FSM - Finite State Machine , per identificare la sequenza di caratteri (come: A, B, C, A, C), e dire se ha accettato.

Pensiamo di implementare tre classi: State , Event e Machine . La class di state presenta un nodo FSM , abbiamo pensato di implementarlo con lo State design pattern , ogni nodo si estenderà dallo stato astratto della class e ogni class gestirà diversi tipi di eventi e indicherà le transizioni a un nuovo stato. È una buona idea secondo te?

Seconda cosa, non sappiamo come salvare tutte le transizioni. Ancora una volta abbiamo pensato di implementarlo con una sorta di map , che mantiene il punto di partenza e ottiene una sorta di vettore con gli stati successivi, ma non sono sicuro che sia una buona idea.

Sarei felice di avere qualche idea su come implementarlo o forse potresti darmi dei punti di partenza.

Come dovrei salvare l’FSM, cioè come dovrei build l’albero all’inizio del programma? L’ho cercato su google e ho trovato molti esempi ma nulla che mi aiuti.

Molte grazie.

Il cuore di una macchina a stati è la tabella di transizione, che prende uno stato e un simbolo (quello che stai chiamando un evento) in un nuovo stato. Questo è solo un array di stati a due indici. Per sanità mentale e sicurezza del tipo, dichiarare stati e simboli come enumerazioni. Aggiungo sempre un membro di “lunghezza” in qualche modo (specifico della lingua) per controllare i limiti dell’array. Quando ho codificato a mano gli FSM, ho formattato il codice in formato riga e colonna con smanettoni bianchi. Gli altri elementi di una macchina a stati sono lo stato iniziale e l’insieme di stati accettanti. L’implementazione più diretta dell’insieme di stati accettanti è una serie di valori booleani indicizzati dagli stati. In Java, tuttavia, le enumerazioni sono classi, ed è ansible specificare un argomento “accettando” nella dichiarazione per ogni valore enumerato e inizializzarlo nel costruttore per l’enumerazione.

Per il tipo di macchina, puoi scriverlo come una class generica. Ci vorrebbero due argomenti di tipo, uno per gli stati e uno per i simboli, un argomento di matrice per la tabella di transizione, un singolo stato per l’iniziale. L’unico altro dettaglio (anche se è fondamentale) è che devi chiamare Enum.ordinal () per ottenere un numero intero adatto per l’indicizzazione della matrice di transizione, poiché non esiste alcuna syntax per dichiarare direttamente una matrice con un indice di enumerazione (anche se dovrebbe essere).

Per prevenire un problema, EnumMap non funzionerà per la tabella di transizione, poiché la chiave richiesta è una coppia di valori di enumerazione, non una singola.

 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, ti suggerirei di utilizzare Flyweight per implementare gli stati. Scopo: evitare l’overhead della memoria di un gran numero di piccoli oggetti. Le macchine di stato possono diventare molto, molto grandi.

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

Non sono sicuro di vedere la necessità di utilizzare lo stato del modello di progettazione per implementare i nodes. I nodes in una macchina a stati sono senza stato. Corrispondono semplicemente al simbolo di input corrente alle transizioni disponibili dallo stato corrente. Cioè, a meno che non abbia completamente dimenticato come funzionano (che è una possibilità definita).

Se lo stessi scrivendo, farei qualcosa del genere:

 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); 

Cosa potrebbe fare Flyweight in questo caso? Bene, sotto il FsmNode ci sarebbe probabilmente qualcosa del genere:

 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; } } } 

Ciò crea gli oggetti di stato su una base di necessità, consente di utilizzare un meccanismo sottostante molto più efficiente per memorizzare la macchina di stato effettiva. Quello che uso qui (Map (Integer, Map (Symbol, Integer))) non è particolarmente efficiente.

Si noti che la pagina di Wikipedia si concentra sui casi in cui molti oggetti in qualche modo simili condividono i dati simili, come nel caso dell’implementazione String in Java. Secondo me, Flyweight è un po ‘più generico e copre qualsiasi creazione on-demand di oggetti con una breve durata (usare più CPU per risparmiare su una struttura dati sottostante più efficiente).

EasyFSM è una libreria Java dynamic che può essere utilizzata per implementare un FSM.

Puoi trovare la documentazione per lo stesso su: Finite State Machine in Java

Inoltre, è ansible scaricare la libreria su: Libreria Java FSM: DynamicEasyFSM

Prendi in considerazione la libreria Java facile e leggera EasyFlow . Dai loro documenti:

Con EasyFlow puoi:

  • implementa una logica complessa ma mantieni il tuo codice semplice e pulito
  • gestire le chiamate asincrone con facilità ed eleganza
  • evitare la concorrenza utilizzando un approccio di programmazione basato sugli eventi
  • evitare l’errore StackOverflow evitando la ricorsione
  • semplificare la progettazione, la programmazione e il test di applicazioni Java complesse

È ansible implementare la macchina a stati finiti in due modi diversi.

Opzione 1:

Macchina a stati finiti con un stream di lavoro predefinito : consigliata se si conoscono tutti gli stati in anticipo e la macchina a stati è quasi fissa senza modifiche in futuro

  1. Identifica tutti gli stati possibili nella tua applicazione

  2. Identifica tutti gli eventi nella tua applicazione

  3. Identifica tutte le condizioni nella tua applicazione, che possono portare alla transizione di stato

  4. Il verificarsi di un evento può causare transizioni di stato

  5. Costruisci una macchina a stati finiti decidendo un stream di lavoro di stati e transizioni.

    Ad esempio, se si verifica un evento 1 nello stato 1, lo stato verrà aggiornato e lo stato della macchina potrebbe essere ancora nello stato 1.

    Se un evento 2 si verifica nello stato 1, in alcune condizioni di valutazione, il sistema passerà dallo stato 1 allo stato 2

Questo disegno è basato su modelli di stato e contesto .

Dai un’occhiata alle classi di prototipi di Finite State Machine .

Opzione 2:

Alberi comportamentali: consigliati se sono presenti frequenti modifiche al stream di lavoro dello stato macchina. È ansible aggiungere dynamicmente un nuovo comportamento senza rompere l’albero.

inserisci la descrizione dell'immagine qui

La class Task di base fornisce un’interfaccia per tutte queste attività, le attività foglia sono quelle appena menzionate e le attività principali sono i nodes interni che decidono quale attività eseguire successivamente.

I Task hanno solo la logica di cui hanno bisogno per fare effettivamente ciò che è richiesto da loro, tutta la logica decisionale per stabilire se un’attività è stata avviata o meno, se ha bisogno di aggiornarsi, se ha finito con successo, ecc. È raggruppata nel TaskController class e aggiunta per composizione.

I decoratori sono compiti che “decorano” un’altra class avvolgendola e dandogli una logica aggiuntiva.

Infine, la class Blackboard è una class di proprietà dell’IA genitore a cui ogni attività ha un riferimento. Funziona come un database di conoscenza per tutte le attività foglia

Date un’occhiata a questo articolo di Jaime Barrachina Verdia per maggiori dettagli

Ho progettato e implementato un semplice esempio di macchina a stati finiti con java.

IFiniteStateMachine : l’interfaccia pubblica per gestire la macchina a stati finiti
come aggiungere nuovi stati alla macchina a stati finiti o passare agli stati successivi di
azioni specifiche.

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

IState : l’interfaccia pubblica per ottenere informazioni relative allo stato
come il nome dello stato e le mappature agli stati connessi.

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

Azione : la class che causerà la transizione degli stati.

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

StateImpl : l’implementazione di IState. Ho applicato la struttura dei dati come HashMap per mantenere i mapping Action-State.

 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 String getStateDesc() { return mStateName; } @Override public void addTransit(Action action, IState state) { mMapping.put(action.toString(), state); } @Override public void removeTransit(String targetStateDesc) { // get action which directs to target state String targetAction = null; for (Map.Entry entry : mMapping.entrySet()) { IState state = entry.getValue(); if (state.getStateDesc().equals(targetStateDesc)) { targetAction = entry.getKey(); } } mMapping.remove(targetAction); } } 

FiniteStateMachineImpl : implementazione di IFiniteStateMachine. Io uso ArrayList per mantenere tutti gli stati.

 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 String startStateDesc = startState.getStateDesc(); final String 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.toString())) { mCurrentState = localMapping.get(action.toString()); } else { throw new RuntimeException("No action start from current state"); } } @Override public IState getStartState() { return mStartState; } @Override public IState getEndState() { return mEndState; } } 

esempio :

 public class example { public static void main(String[] 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")); } } 

Esempio completo su Github