una - maquinas de estado java

Cómo implementar un FSM-Máquina de estados finitos en Java

Question

Tengo algo que hacer para el trabajo y necesito tu ayuda. Queremos implementar un FSM - Finite State Machine , para identificar la secuencia de caracteres (como: A, B, C, A, C) e indicar si es aceptable.

Pensamos implementar tres clases: State , Event y Machine . La clase de state presenta un nodo en el FSM , pensamos implementarlo con un State design pattern , cada nodo se extenderá desde el estado de clase abstracta y cada clase manejaría diferentes tipos de eventos e indicaría las transiciones a un nuevo estado. ¿Es buena idea en tu opinión?

En segundo lugar, no sabemos cómo guardar todas las transiciones. Una vez más pensamos implementarlo con algún tipo de map , que mantenga el punto de partida y obtenga algún tipo de vector con los próximos estados, pero no estoy seguro de que sea una buena idea.

Me gustaría obtener algunas ideas sobre cómo implementarlo o tal vez pueda darme algunos puntos de partida.

¿Cómo debo guardar el FSM, es decir, cómo debería construir el árbol al comienzo del programa? Busqué en Google y encontré muchos ejemplos, pero nada que me ayude.

Muchas gracias.

Answer 1

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

Con EasyFlow puedes:

• implemente una lógica compleja pero mantenga su código simple y limpio
• maneja llamadas asíncronas con facilidad y elegancia
• evitar la concurrencia mediante el uso de un enfoque de programación basado en eventos
• evitar el error de al evitar la recursión
• simplificar el diseño, la programación y la prueba de aplicaciones complejas de Java

Answer 2

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

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

Además, puede descargar la biblioteca en: Java FSM Library: DynamicEasyFSM

Answer 3

El corazón de una máquina de estado es la tabla de transición, que toma un estado y un símbolo (lo que está llamando evento) a un nuevo estado. Eso es solo una matriz de estados de dos índices. Para la cordura y la seguridad de tipo, declare los estados y símbolos como enumeraciones. Siempre agrego un miembro de "longitud" de alguna manera (específico del idioma) para verificar los límites de la matriz. Cuando tengo FSM codificados a mano, formateo el código en formato de fila y columna con un toque de espacio en blanco. Los otros elementos de una máquina de estado son el estado inicial y el conjunto de estados de aceptación. La implementación más directa del conjunto de estados aceptables es una matriz de booleanos indexados por los estados. En Java, sin embargo, las enumeraciones son clases, y puede especificar un argumento "aceptar" en la declaración para cada valor enumerado e inicializarlo en el constructor para la enumeración.

Para el tipo de máquina, puede escribirlo como una clase genérica. Tomaría dos argumentos de tipo, uno para los estados y uno para los símbolos, un argumento de matriz para la tabla de transición, un estado único para la inicial. El único otro detalle (aunque es crítico) es que debe llamar a Enum.ordinal () para obtener un entero adecuado para indexar la matriz de transición, ya que no hay sintaxis para declarar directamente una matriz con un índice de enumeración (aunque debería haber una ser).

Para adelantarse a un problema, EnumMap no funcionará para la tabla de transición, porque la clave requerida es un par de valores de enumeración, no uno solo.

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[][] = {
    //  A               B               C
    {
        State.Initial,  State.Final,    State.Error
    }, {
        State.Final,    State.Initial,  State.Error
    }
};

Answer 4

Hmm, sugeriría que uses Flyweight para implementar los estados. Propósito: Evite la sobrecarga de memoria de una gran cantidad de objetos pequeños. Las máquinas de estado pueden ser muy, muy grandes.

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

No estoy seguro de ver la necesidad de utilizar el patrón de diseño State para implementar los nodos. Los nodos en una máquina de estados no tienen estado. Simplemente coinciden con el símbolo de entrada actual a las transiciones disponibles desde el estado actual. Es decir, a menos que haya olvidado completamente cómo funcionan (lo cual es una posibilidad definitiva).

Si 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 Flyweight 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 según la necesidad de uso. Le permite utilizar un mecanismo subyacente mucho más eficiente para almacenar la máquina de estado real. El que uso aquí (Mapa (Entero, Mapa (Símbolo, Entero))) no es particularmente eficiente.

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

Answer 5

Puede implementar la Máquina de estados finitos de dos formas diferentes.

Opción 1:

Máquina de estado finito con un flujo de trabajo predefinido : Recomendada si conoce todos los estados por adelantado y la máquina de estado está casi arreglada sin ningún cambio en el futuro

1. Identifica todos los estados posibles en tu aplicación

2. Identifica todos los eventos en tu aplicación

3. Identifique todas las condiciones en su aplicación, que pueden conducir la transición de estado

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

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

   por ejemplo, si ocurre 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 pasará del estado 1 al estado 2

Este diseño se basa en patrones de estado y contexto .

Eche un vistazo a las clases de prototipos de la máquina de estados finitos .

Opcion 2:

Árboles conductuales: recomendados si hay cambios frecuentes en el flujo de trabajo de la máquina de estados. Puede agregar de forma dinámica un nuevo comportamiento sin romper el árbol.

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

Las Tareas tienen solo la lógica que necesitan para hacer realmente lo que se les exige, toda la lógica de decisión de si una tarea ha comenzado o no, si necesita actualizarse, si ha finalizado con éxito, etc. se agrupa en el TaskController clase, y agregada por composición.

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

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

Echa un vistazo a este article de Jaime Barrachina Verdia para más detalles