Maquina de estados: ¿A que nos referimos? 1

maquina de estados
 en Electrónica y Control / TIC  Etiquetado Control de sistemas por

Una máquina de estados no es una máquina física. Es una modelización conceptual, generalmente en forma de diagrama, de un problema.

En este problema el sujeto de interés se encuentra en una situación inicial a la espera de recibir un estímulo del mundo exterior para reaccionar a él. Por ejemplo, si tenemos una pelota de playa posada sobre el suelo, que será su posición inicial, podemos darle una patada, con lo que se moverá en una dirección, o podemos darle un puñetazo hacia abajo, con lo que se aplastará. Si queremos plasmar en un papel este problema, de forma esquematizada y concisa, podemos recurrir a múltiples formas, pero la gran mayoría tendrán las siguientes partes. Un objeto de estudio, en este caso la pelota; un estado inicial, parada en el suelo; una entradas que serán la patada y el puñetazo y unas acciones que serán avanzar y aplastarse.

Podríamos dibujarlo así:

esq-basico
Estados en azul y acciones en rojo

Una máquina de estados, lo que hace es sentar unas bases comunes para la modelización de este tipo de problemas, dado que estos pueden crecer en complejidad y llegar a hacerse muy difíciles de representar.

Lo primero que se hizo fue definir algunos términos.

  • Estados: se definen asi las posiciones o acciones por las que pasa el objeto de estudio. Dentro de los estados destaca el denominado estado inicial o de espera, que representa la posición de partida del objeto en la que se encuentra esperando un evento o entrada para pasar al siguiente estado. En general, el resto de estados puede partir/llegar de forma directa a esta posición o forman un anillo con principio y fin en el. Cuando nos movemos entre estados solemos decir que pasamos al siguiente estado o que venimos del estado anterior.
  • Entradas: Son las interacciones del medio con el objeto que pueden alterarlo y hacer que cambie de estado. En nuestro caso serían la patada y el puñetazo.
  • Salidas: Son las acciones que realiza el objeto hacia el exterior. En el caso de la pelota de playa no habría ninguna a no ser que tirara algo al salir despedida por la patada o que explotara por la presión expulsando el aire.
  • Eventos: Son las acciones, ya sean internas o externas que hacen que el objeto cambie de estado. Serían la patada, el puñetazo como externos y la expansión del aire que lo vuelve a llenar y el rozamiento que lo para los internos.
  • Transiciones: Son los “caminos” por los que el objeto cambia de un estado a otro. Acotan los cambios y comprueban las condiciones.

Por lo tanto, en una máquina de estados, tenemos un objeto que puede estar en x posiciones y que debido a la acción de los eventos, ya sean internos o externos, se desplaza entre ellos siguiendo las transiciones permitidas mientras puede o no emitir señales al exterior.

esq-2
Diagrama esquemático del problema según convenio (Ejemplo sin salidas)

Esto parece simple, incluso rozando lo trivial. Pero cuando el problema pasa de tratar sobre una pelota, a un elemento autómata, la cosa se complica mucho. Hasta el punto de que puede hacerse más complicado el seguir las transiciones con sus condiciones que el pensar en que hace el autómata. Y es cierto que cuando empezaron a diseñarse los primeros autómatas, es decir, aquel artilugio que se mueve por sí mismo, sin dirección externa, reaccionando a las entradas del mundo exterior y produciendo salidas, no era necesario realizar complejos esquemas para poder definir los pasos que daban. El problema surgió cuando los autómatas empezaron a hacerse más complejos. De forma que se hizo necesaria una métrica común que pudiera representar tanto los problema simples como los complejos de una forma estructurada.

La importancia de estos aparentemente sencillos esquemas ha traspasado su entorno inicial y ahora se utilizan versiones adaptadas en un gran número de áreas, y no solo en el ámbito de la tecnología. Pero para explicar más a fondo el proceso de construcción de estas máquinas vamos a echar mano de los sistemas descritos para sistemas autónomos. Más concretamente las máquinas de Mealy y de Moore para sistema autónomos independientes y sencillos. Este tipo de máquinas se denominan del tipo de “Máquinas analíticas de estados finitos” (FSM) por tener un conjunto limitado de estados.

Estas dos máquinas se denominan con el nombre de sus creadores, George H. Mealy (1927-2010) y  Edward Forrest Moore (1925-2003) y se diferencian en que se representa la salida en el estado (Moore) o en la transición siendo dependiente de la entrada (Mealy). Con el tiempo la máquina de Moore, más flexible y estable aunque presenta en general más estados, ha pasado a ser la más utilizada y extendida pero ambas comparten el mismo sistema de generación.

Los pasos para generar una de estas máquinas son los mismos. Primero se hace una conceptualización del problema definiendo los estados, las entradas, etc. A continuación se rellena una tabla de estados/entradas donde se dan las pautas para realizar el esquema final.

Con el ejemplo de la pelota quedaría así:

esq-3
Maquinas de Mealy y Moore con los datos del ejemplo. Podría completarse con las transiciones de vuelta al estado inicial (parada/soltar) y de mantenimiento de las acciones que realimentan los estados 1 y 2 (patada/puño)

Cuando el sistema es muy complejo, podemos realizar simplificaciones mediante álgebra de Boole a las ecuaciones matemáticas extraídas de las tablas de estado/entrada. Con este procedimiento seremos capaces de construir un gráfico que podrá usarse para implementar muchos proyectos, tanto a nivel de robótica/automática, como a nivel de programación (mediante bucles y condicionales), etc.

La ecuación resultante puede implementarse mediante chips que simulen las puertas lógicas del Algebra de Boole y por lo tanto puede generarse un sistema de control autómata que cumpla las especificaciones y requisitos de un sistema de una forma sencilla y sin grandes cálculos matemáticos.

Por lo tanto las máquinas de estados son en la actualidad una gran herramienta que es utilizada casi de forma cotidiana por un sinfín de procesos, desde un comparador binario hasta el personaje de un juego de animación.






Referencias:

Deja un comentario

Una idea sobre “Maquina de estados: ¿A que nos referimos?”