Cómo implementar una Máquina de Estados Finitos FSM en Java

Hmm, yo sugeriría que use Peso Mosca para implementar los estados. Propósito: Evite la sobrecarga de memoria de un gran número de objetos pequeños. Las máquinas estatales pueden ser muy, muy grandes.

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

No estoy seguro de ver la necesidad de usar el Estado de patrón de diseño para implementar los nodos. Los nodos de una máquina de estados son apátridas. Simplemente coinciden con el símbolo de entrada actual con las transiciones disponibles del estado actual. Eso es, a menos que haya olvidado por completo cómo funcionan (lo cual es una posibilidad definitiva).

Si lo estuviera codificando, haría algo como esto:

interface FsmNode {
  public boolean canConsume(Symbol sym);
  public FsmNode consume(Symbol sym);
  // Other methods here to identify the state we are in
}

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

¿Qué haría el Peso mosca en este caso? Bueno, debajo del FsmNode probablemente habría algo como esto:

Map<Integer, Map<Symbol, Integer>> 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<Symbol, Integer> 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;
    }
  }
}

Esto crea los objetos de Estado sobre una base de necesidad de uso, le permite usar un mecanismo subyacente mucho más eficiente para almacenar la máquina de estado real. El que uso aquí (Map (Integer, Map (Symbol, Integer))) no es particularmente eficiente.

Tenga en cuenta que la página de Wikipedia se centra en los casos en los que muchos objetos algo similares comparten los datos similares, como es el caso de la implementación de cadenas en Java. En mi opinión, Flyweight es un poco más general, y cubre cualquier creación bajo demanda de objetos con una vida útil corta (use más CPU para ahorrar en una estructura de datos subyacente más eficiente).

EasyFSM es una biblioteca Java dinámica que se puede utilizar para implementar un FSM.

Puede encontrar documentación para el mismo en : Máquina de Estados finitos en Java

También, puede descargar la biblioteca en : Java FSM Library: DynamicEasyFSM

Considere la biblioteca Java fácil y ligera EasyFlow. De sus documentos:

Con EasyFlow puedes:

• implemente lógica compleja pero mantenga su código simple y limpio
• maneja llamadas asíncronas con facilidad y elegancia
• evite la concurrencia mediante el uso de un enfoque de programación basado en eventos
• evite el error de StackOverflow evitando la recursión
• simplifique el diseño, la programación y las pruebas de aplicaciones java complejas

Puede implementar la Máquina de Estados Finitos de dos maneras diferentes.

Opción 1:

Máquina de Estados finitos con un flujo de trabajo predefinido: Se recomienda si conoce todos los estados de antemano y la máquina de estados está casi fija sin cambios en el futuro

1. Identifique todos los posibles estados en su solicitud

2. Identifique todos los eventos en su aplicación

3. Identificar todos los condiciones en su solicitud, que pueden conducir a la transición de estado

4. La ocurrencia de un evento puede causar transiciones de estado

5. Construya una máquina de estados finitos decidiendo un flujo de trabajo de estados y transiciones.

   Por ejemplo, si se produce un evento 1 en el Estado 1, el estado se actualizará y el estado de la máquina aún puede estar en el estado 1.

   Si ocurre un evento 2 en el Estado 1, en alguna evaluación de condición, el sistema se moverá del Estado 1 a Estado 2

Este diseño se basa en los patrones State y Context.

Eche un vistazo a Clases prototipo de Máquina de Estados Finitos.

Opción 2:

Árboles de comportamiento: Recomendado si hay cambios frecuentes en el flujo de trabajo de la máquina de estado. Puede agregar un nuevo comportamiento dinámicamente sin romper el árbol.

La clase base Task proporciona una interfaz para todos estos tareas, las tareas hoja son las que acabamos de mencionar, y las tareas padre son los nodos interiores que deciden qué tarea ejecutar a continuación.

Las Tareas solo tienen la lógica que necesitan para hacer realmente lo que se requiere de ellas, toda la lógica de decisión de si una tarea ha comenzado o no, si necesita actualizarse, si ha terminado con éxito, etc. se agrupa en la clase TaskController, y se añade por composición.

Los decoradores son tareas que "decora" otra clase envolviéndola y dándole lógica adicional.

Finalmente, la clase Blackboard es una clase propiedad de la IA principal a la que cada tarea tiene una referencia. Funciona como una base de datos de conocimiento para todas las tareas de hoja

Echa un vistazo a este artículo de Jaime Barrachina Verdia para más detalles

Diseñé e implementé un ejemplo de máquina de estados finitos simple con java.

IFiniteStateMachine : La interfaz pública para administrar la máquina de estados finitos
tales como agregar nuevos estados a la máquina de estados finitos o transitar a los estados siguientes mediante
acciones específicas.

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: La interfaz pública para obtener información relacionada con el estado
como el nombre del estado y las asignaciones a estados conectados.

interface IState {
    // Returns the mapping for which one action will lead to another state
    Map<String, IState> getAdjacentStates();

    String getStateDesc();

    void addTransit(Action action, IState nextState);

    void removeTransit(String targetStateDesc);
}

Action : la clase que causa la transición de los estados.

public class Action {
    private String mActionName;

    public Action(String actionName) {
        mActionName = actionName;
    }

    String getActionName() {
        return mActionName;
    }

    @Override
    public String toString() {
        return mActionName;
    }

}

StateImpl: la implementación de IState. Apliqué una estructura de datos como HashMap para mantener las asignaciones de Estado de acción.

public class StateImpl implements IState {
    private HashMap<String, IState> mMapping = new HashMap<>();
    private String mStateName;

    public StateImpl(String stateName) {
        mStateName = stateName;
    }

    @Override
    public Map<String, IState> 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<String, IState> entry : mMapping.entrySet()) {
            IState state = entry.getValue();
            if (state.getStateDesc().equals(targetStateDesc)) {
                targetAction = entry.getKey();
            }
        }
        mMapping.remove(targetAction);
    }

}

FiniteStateMachineImpl: Implementación de IFiniteStateMachine. Uso ArrayList para mantener todos los estados.

public class FiniteStateMachineImpl implements IFiniteStateMachine {
    private IState mStartState;
    private IState mEndState;
    private IState mCurrentState;
    private ArrayList<IState> mAllStates = new ArrayList<>();
    private HashMap<String, ArrayList<IState>> 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<IState>());
    }

    @Override
    public void setEndState(IState endState) {
        mEndState = endState;
        mAllStates.add(endState);
        mMapForAllStates.put(endState.getStateDesc(), new ArrayList<IState>());
    }

    @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<IState>());
        ArrayList<IState> 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<String, IState> 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;
    }
}

Ejemplo:

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

}

Ejemplo Completo en Github