Antecedentes

Las Máquinas de Estados Finitos (FSM), también conocidas como Autómatas de Estados Finitos (FSA), explicado de forma simple, son modelos de comportamiento de un sistema o un objeto complejo, con un número limitado de modos o condiciones predefinidos, donde existen transiciones de modo.

Las FSMs están compuestas por 4 elementos principales:

• estados que definen el comportamiento y pueden producir acciones
• transiciones de estado que son movimientos de un estado a otro
• reglas o condiciones que deben cumplirse para permitir un cambio de estado
• eventos de entrada que son externos o generados internamente, que permiten el lanzamiento de las reglas y permiten las transiciones

Una máquina de estados finitos debe tener un estado inicial que actúa de punto de comienzo, y un estado actual que recuerda el producto de la anterior transición de estado.  Los eventos recibidos como entrada actúan como disparadores, que causan una evaluación de las reglas que gobiernan las transiciones del estado actual a otro estado. La mejor manera de visualizar una FSM es pensar en ella como un diagrama de flujo o un grafo dirigido de estado, aunque como se verá existen técnicas de abstracción más precisas que pueden ser usadas.

Figura 1.1: Una posible implementación de un sistema de control mediante Máquina de Estados Finitos

Las FSMs se usan típicamente como un tipo de sistema de control donde el conocimiento está representado en los estados, y las acciones están restringidas por las reglas.

"...Una de las cosas más fascinantes acerca de los FSMs es que las mismas técnicas pueden ser usadas para diseñar programas de Visual Basic, circuitos lógicos o firmware para un microcontrolador. Muchos ordenadores y chips de microprocesadores tienen, en su corazón, una FSM."^[1]

Las máquinas de estados finitos son una técnica adoptada por la inteligencia artificial que se originó en el campo de las matemáticas, inicialmente utilizada para la representación de lenguajes.  Están relacionadas de cerca con otras técnicas fundamentales de representación del conocimiento las cuales merece la pena mencionar, como redes semánticas ^[5] y una extensión de las redes semánticas llamada espacio de estados ^[5].

Las redes semánticas se propusieron para representar el significado y la relación entre palabras del inglés. Se construye un grafo donde los nodos representan conceptos y las esquinas relaciones. El espacio de estados es una extensión de esta idea, los nodos denotan un estado válido y las esquinas transiciones entre estados. El espacio de estados, a diferencia de las FSM, requiere tanto un estado inicial como un estado objetivo, y se utiliza normalmente en la resolución de problemas donde se requiere una secuencia de acciones para resolver el problema (la secuencia desde los estados iniciales hasta los objetivos).  Como las FSM, el espacio de estados tiene condiciones en la transición de estados, y son activados por los eventos de entrada.

Como cualquier otro sistema basado en reglas, si todos los antecedente(s) de una regla son ciertos, entonces la regla se activa.  Es posible que se activen múltiples reglas, y en al área de los sistemas de razonamiento, este hecho es conocido como grupo de conflicto. Solo puede haber una transición desde el estado actual, por ello se requiere una estrategia consistente de resolución de conflictos para seleccionar una de las reglas activadas para dispararse y así realizar la transición de estado.

Esto nos brinda dos tipos principales de FSM. La simple FSM original es lo que se conoce como determinista, significando que dada una entrada y el estado actual, puede predecirse la transición de estado. Una extensión del concepto opuesto al anterior es una máquina de estados finitos no determinista. Dado el estado actual; la transición de estado no es predecible. Puede darse el caso que múltiples entradas se reciban en tipos diferentes, esto significaría que desde el estado actual no puede conocerse la transición a otro estado hasta que las entradas se reciban (dirigido por eventos).

Una implementación de una máquina de estados finitos determinista debe prever la activación de la primera regla que se activa. Esto puede ser perfecto para muchos problemas, pero no para los juegos de ordenador. El comportamiento fácilmente predecible no es usualmente una característica deseable ya que tiende a eliminar el "factor de diversión" del juego.

"...un jugador se siente como si estuviera jugando contra una simulación realística de la inteligencia, y no contra contra una reproducción de una secuencia de acciones." ^[2]

La "secuencia", que es una de las claves de los beneficios de una FSM, no debe ser cegadoramente obvia en los juegos de ordenador. Existe numerosas extensiones a las FSM y trucos para "mezclar" la secuencia para hacer más difícil predecir sus actos. Una de estas opciones no deterministas  implica la aplicación de otra técnica probada en la inteligencia artificial: Lógica Difusa, llamada Máquina de Estados Difusa (FuSM).

Al igual que existe una gran flexibilidad en las máquinas de estados también existe al implementar una máquina de estados difusa. Se puede aplicar una valor difuso a varias transiciones de estados. Cuando se encuentra un grupo de conflicto la transición con el valor difuso más alto será la transición más adecuada.  Esto permite la especificación de prioridades difusas a las transiciones de estados.

Una  implementación de una FuSM puede implicar la asignación de valores difusos a varias entradas para representar su grado. El sistema difuso usará esta entrada de valores ponderada en la evaluación de reglas, activándose solo las transiciones de estados cuyo valor alcanzado esté sobre un umbral específico.

Otra aproximación para convertir una FSM determinista en una FSM no determinista sería simplemente usar un generador de números aleatorios para seleccionar la regla a activar. Puede ser que no sea necesario implementar una máquina de estados finitos no determinista para percibir cierto nivel de impredictibilidad. Esto puede conseguirse mediante un objeto o sistema con un número muy elevado de estados definidos y una red compleja de transiciones, dando así la apariencia de ser impredecible.

Es importante comprender la diferencia entre un estado y una acción. Al diseñar un programa de ordenador, las funcionalidades grandes se descomponen en un numero de acciones o actividades menores. Esto se realiza de manera que cada una pueda ser definida en una función, haciendo la solución general modular y más fácil de mantener. Las FSMs son parecidas, ya que son una descomposición del comportamiento de un objeto o sistema, e incluso un estado puede ser descompuesto en sub-estados. La diferencia está en que un estado puede desarrollar una o más acciones.

Ejemplo 1: una acción moveUnit() puede ser usada tanto por el estado evadirEnemigo como por el estado atacarEnemigo.

Ejemplo 2: el estado evadirEnemigo puede consistir en muchas acciones, algunas evaluaciones y algunas directivas de movimiento. Si la entidad ha sido arrinconada, por ejemplo, puede haber una transición del estado evadirEnemigo a atacarEnemigo, donde la acción de ser arrinconado es el activador.

Me gusta pensar en el término acción como una actividad que consigue un objetivo como una evaluación o un movimiento, y en el término estado como un colección de acciones que se usan en un modo particular. Un estado es la circunstancia de algo, es una condición, y las acciones son atributos de ese estado. Provee la habilidad de limitar el alcance de las acciones o la cantidad de conocimiento necesario para el estado actual.

Existen dos métodos principales para seleccionar donde generar las salidas de una máquina de estados finitos. Se les llaman Máquina de Moore y  Máquina de Mearly, llamadas así por el nombre de sus respectivos autores.

Una  Máquina de Moore es un tipo de máquina de estados finitos donde las salidas se generan como producto de los estados. En el ejemplo de abajo los estados definen que hacer; como por ejemplo encender la bombilla.

Figura 1.2: Un sistema de luz ejemplo de una Máquina de Moore

Una Máquina de Mearly, a diferencia de la Máquina de Moore es una máquina de estados finitos donde las salidas se generan como producto de las transiciones entre estados. En el ejemplo de abajo la luz se ve afectada por el cambio de estado.

Figure 1.3: Un sistema de luz ejemplo de un Máquina de Mearly

Las máquinas de estados finitos no son una nueva técnica, ya hace tiempo que existe. El concepto de descomposición debe ser familiar a las personas con experiencia de programación o diseño. Existen varias técnicas de modelado abstracto que pueden ayudar o mejorar el entendimiento al definir y diseñar una máquina de estados finitos, la mayoría provienen del área del diseño o las matemáticas.

• Diagrama de Transiciones de Estados: también conocido como diagrama de burbujas, muestra la relación entre los estados y las entradas que causan las transiciones. ^[1]
• Diagrama Estado-Acción-Decisión: simplemente un diagrama de flujo con el añadido de burbujas que representan la espera de entradas externas ^[1]
• Diagrama Statechart: una forma de notación UML usada para mostrar el comportamiento de un objeto individual con un número de estados y transiciones entre esos estados. ^[3]
• análisis de Jerarquía de Tareas (HTA): aunque no estudia los estados, HTA es una técnica de descomposición que estudia como una tarea puede dividirse en subtareas, y el orden en que deben realizarse. ^[4]

Ventajas de una FSM

• Su simplicidad hace fácil para los desarrolladores sin experiencia realizar la implementación con poco o nada de conocimiento extra (fácil entrada)
  
• Predictibilidad (en FSM deterministas), dado un grupo de entradas y un estado actual conocido, puede predecirse la transición de estados, facilitando la tarea de verificación
  
• Dada su simplicidad, los FSM son rápidos de diseñar, rápidos e implementar y rápidos de ejecutar
  
• FSM en una técnica antigua de representación de conocimiento y modelado de sistemas, y ha sido usados desde hace tiempo, como tal ha sido verificado como una técnica de inteligencia artificial, con muchos ejemplos de los que aprender
  
• Las FSM son relativamente flexibles. Existen varias maneras de implementar un sistema basado en FSMs en términos de su topología, y es fácil incorporar muchas otras técnicas.
  
• La transferencia desde una representación abstracta del conocimiento a una implementación es fácil
  
• Bajo uso del procesador; apropiado para dominios donde el tiempo de ejecución está compartido entra varios módulos o subsistemas. Solo el código del estado actual ha de ser ejecutado, además de un poco de lógica para determinar el estado actual.
  
• Es fácil determinar si se puede llegar o no a un estado, en las representaciones abstractas, resulta obvio si se puede o no llegar a un estado desde otro, y que requerimientos existen para hacerlo.
  

Desventajas de una FSM

• La naturaleza predecible de las FSM deterministas puede no resultar conveniente en algunos dominios como los juegos por ordenador (la solución pasa por implementar una FSM no determinista)
  
• Si se implementa un sistema grande usando FSMs puede ser difícil de administrar y mantener sin un buen diseño.  Las transiciones entre estados pueden causar cierto grado de "factor espagetti" al intentar seguir una linea de ejecución.
  
• No es apropiado para todos los dominios de problema, solo debe ser usado cuando el comportamiento de un sistema puede ser descompuesto en estados separados con condiciones bien definidas para las transiciones. Esto significa que todos los estados, transiciones y condiciones deben ser conocidos y estar bien definidos.
  
• Las condiciones para las transiciones entre estados son rígidas, significando que están fijadas (puede superarse usando una FuSM)
  

Como la mayoría de técnicas, las heurísticas para saber donde y como implementar máquinas de estados finitos son subjetivas y dependen de cada problema específica. Está claro que las FSMs están bien adaptadas a dominios de problemas que se expresan fácilmente usando diagramas de flujo y poseen un grupo de estados y reglas que gobiernan las transiciones entre estados bien definidos.

Para una mayor discusión sobre las máquinas de estados finitos yo os recomiendo; Finite State Machines - Making simple work of complex functions ^[1]

Visita Artificial Intelligence Depot.