Máquinas de estados finitos

 

Máquinas de Estados Finitos (FSM)

• También conocidas como Autómatas deEstados Finitos (FSA), 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.

 

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.“ [Gibson, “Finite State Machines”]

 

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 y una extensión de las redes semánticas llamada espacio de estados.

 

 

 

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 computadora. El comportamiento fácilmente predecible no es usualmente una característica deseable ya que tiende a eliminar el "factor de diversión" del juego.

 

 

 

 

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.

 

Herramientas para el análisis y diseño de FSM:

 

• 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.

• Diagrama Estado-Acción-Decisión: simplemente un diagrama de flujo con el añadido de burbujas que representan la espera de entradas externas.

• 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.

• 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.

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 se puede aprender.

 

Ventajas de una FSM

 

• Las FSM son relativamente flexibles. Existen varias manerasde 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 computadora (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 línea 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 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.