En esta entrada vamos a ver cómo modelizar una máquina de estados finitos en un procesador como Arduino.
Una máquina de estados finitos es una abstracción computacional empleada de forma habitual. Es una forma sistematizada de plantear la programación de un autómata. Por este motivo son ampliamente utilizados en el desarrollo de pequeños y medianos proyectos.
Ejemplos que podemos realizar con una máquina de estado son, por ejemplo, máquinas de vending, ascensores, barreras de parking, estaciones industriales, e incluso pequeños robots, entre muchos otros.
¿Qué es una máquina de estados?
Una máquina de estados modeliza el comportamiento de una máquina automática. Está formada por estados, transiciones, entradas y salidas.
Frecuentemente las máquinas de estados se representan con diagramas, en los que cada estado corresponde con un círculo, y las transiciones con flechas que los unen. En ocasiones se añaden las entradas y salidas del sistema según distintos convenios.
Los estados describen las posibles combinaciones de las variables internas del autómata en un determinado instante. Un autómata parte de un estado inicial y, a medida que ocurren eventos, cambia a los distintos estados que describen su posible comportamiento.
Los cambios de un estado a otro están determinados por transiciones, que tienen asociada una determinada condición. Las condiciones asociadas a las transiciones de cambio de estados pueden depender tanto de variables externas (entradas) como internas.
Finalmente, una máquina de estados debe realizar acciones (o salidas). Están pueden estar asociadas a los estados (máquina de Moore) o a las transiciones (máquina de Mealy), siendo ambos planteamientos similares en su formulación.
Ejemplo de máquina de estados
Vamos a realizar una implementación sencilla de una máquina de estados en un procesador como Arduino. La máquina que vamos a implementar como ejemplo corresponde al siguiente esquema.
Como vemos, es una máquina muy sencilla que tiene 4 estados A, B, C y D. Tenemos tres posibles entradas, Fordward, Backward y Reset.
Con Fordward y Backward la máquina pasa al estado siguiente y anterior. Por otro lado, la entrada Reset hace volver al estado A, desde cualquier otro estado.
Se ha decidido que los estados no son cíclicos. Es decir, Fordward no hace pasar de D a A, ni Backward hace pasar de A a D. Aunque también podríamos haberlo hecho sin mayor esfuerzo.
Máquina de estados en Arduino
Una posible implementación de la máquina de estados podría ser la siguiente.
enum State
{
PosicionA,
PosicionB,
PosicionC,
PosicionD
};
enum Input
{
Unknown,
Reset,
Forward,
Backward
};
// Variables globales
State currentState;
Input currentInput;
// Acciones de los estados y condiciones de transiciones
void stateA()
{
if (currentInput == Input::Forward)
changeState(State::PosicionB);
}
void stateB()
{
if (currentInput == Input::Backward)
changeState(State::PosicionA);
if (currentInput == Input::Forward)
changeState(State::PosicionC);
if (currentInput == Input::Reset)
changeState(State::PosicionA);
}
void stateC()
{
if (currentInput == Input::Backward)
changeState(State::PosicionB);
if (currentInput == Input::Forward)
changeState(State::PosicionD);
if (currentInput == Input::Reset)
changeState(State::PosicionA);
}
void stateD()
{
if (currentInput == Input::Backward)
changeState(State::PosicionC);
if (currentInput == Input::Reset)
changeState(State::PosicionA);
}
// Salidas asociadas a las transiciones
void outputA()
{
Serial.println("A B C D");
Serial.println("X ");
Serial.println();
}
void outputB()
{
Serial.println("A B C D");
Serial.println(" X ");
Serial.println();
}
void outputC()
{
Serial.println("A B C D");
Serial.println(" X ");
Serial.println();
}
void outputD()
{
Serial.println("A B C D");
Serial.println(" X");
Serial.println();
}
void setup()
{
Serial.begin(9600);
currentState = PosicionA;
outputA();
}
void loop()
{
readInput();
updateStateMachine();
}
// Actualiza el estado de la maquina
void updateStateMachine()
{
switch (currentState)
{
case PosicionA: stateA(); break;
case PosicionB: stateB(); break;
case PosicionC: stateC(); break;
case PosicionD: stateD(); break;
}
}
// Lee la entrada por puerto serie
void readInput()
{
currentInput = Input::Unknown;
if (Serial.available())
{
char incomingChar = Serial.read();
switch (incomingChar)
{
case 'R': currentInput = Input::Reset; break;
case 'A': currentInput = Input::Backward; break;
case 'D': currentInput = Input::Forward; break;
default: break;
}
}
}
// Funcion que cambia el estado y dispara las transiciones
void changeState(int newState)
{
currentState = newState;
switch (currentState)
{
case State::PosicionA: outputA(); break;
case State::PosicionB: outputB(); break;
case State::PosicionC: outputC(); break;
case State::PosicionD: outputD(); break;
default: break;
}
}Como vemos, en primer lugar, hemos definido dos enumeraciones que corresponden con los posibles estados y entradas. Es una buena práctica para simplificar la legibilidad del código, su mantenibilidad y escalabilidad.
Por otro lado, tenemos 2 variables globales currentState e currentInput, que almacenan el estado actual de la máquina de estados, y la última entrada recibida.
A continuación, tenemos una función (state) por cada uno de los estados. Estas acciones contienen la lógica asociada a las transiciones, es decir, realizan el cambio a otro estado en función de una condición. En este caso, las únicas condiciones que tenemos son las variables de entrada, pero podrían ser temporizaciones, o cualquier otra.
Por otro lado, tenemos las funciones de salida (output) de cada estado, que se disparan al entrar en un nodo. En este ejemplo, únicamente mostramos una representación por puerto de serie del estado de la máquina. En una máquina real, realizaríamos las acciones necesarias.
Para cambiar entre estados usamos la función changeState(int newState), que comprueba el estado actual con el nuevo estado. Aquí lanzamos las funciones de entrada en cada estado.
Si quisiéramos asociar una función asociada a una transición en particular, en lugar de al entrar en un estado podríamos, por ejemplo, lanzarlas en las funciones state al realizar el cambio de estado.
Finalmente, la máquina se actualiza constantemente a través de la función Update(). Esta función únicamente lanza la función state correspondientes al estado actual, y con esto consigue actualizar el estado de la máquina.
En el ejemplo, también tenemos la función readInput(), que recibe un carácter desde el puerto serie. A, D, y R corresponden, respectivamente, con las entradas Backward, Fordward y Reset. Esta función no es propiamente de la máquina de estado, simplemente la usamos en el ejemplo para comprobar el funcionamiento.
Resultados
Si ejecutamos el código anterior podemos ver por puesto serie el resultado. Podemos cambiar el estado pulsando las teclas ‘A’, ‘D’, y ‘R’.
Máquina de estados tabular en Arduino
A continuación, vamos a ver una variación del código anterior, una implementación tabular de una máquina de estados.
Las principales diferencias son que en este lugar las transiciones entre estados pasan a estar recogidas en una matriz de transición de estados, en lugar de en las funciones anteriores por cada estado. El nuevo estado se obtiene por el índice combinado del estado y la entrada actual.
De forma similar, las acciones asociadas a las transiciones están recogidas en un vector de funciones, de forma que accedemos a cada una directamente por el índice del estado actual.
enum State
{
PosicionA,
PosicionB,
PosicionC,
PosicionD
};
enum Input
{
Unknown,
Reset,
Forward,
Backward
};
const void outputA()
{
Serial.println("A B C D");
Serial.println("X ");
Serial.println();
}
const void outputB()
{
Serial.println("A B C D");
Serial.println(" X ");
Serial.println();
}
const void outputC()
{
Serial.println("A B C D");
Serial.println(" X ");
Serial.println();
}
const void outputD()
{
Serial.println("A B C D");
Serial.println(" X");
Serial.println();
}
typedef void (*const StateFunc)();
State currentState;
Input currentInput;
const StateFunc transitionOutput[] PROGMEM = { outputA, outputB, outputC, outputD};
const byte stateChange[4][4] PROGMEM =
{
{ PosicionA, PosicionA, PosicionB, PosicionA },
{ PosicionB, PosicionA, PosicionC, PosicionA },
{ PosicionC, PosicionA, PosicionD, PosicionB },
{ PosicionD, PosicionA, PosicionD, PosicionC },
};
void setup()
{
Serial.begin(9600);
currentState = PosicionA;
outputA();
}
void loop()
{
readInput();
updateStateMachine();
}
void updateStateMachine()
{
State newState = (State)pgm_read_byte(&stateChange[currentState][currentInput]);
if (currentState == newState) return;
currentState = newState;
StateFunc pStateFunc = (StateFunc)pgm_read_ptr(&transitionOutput[currentState]);
pStateFunc();
}
void readInput()
{
currentInput = Input::Unknown;
if (Serial.available())
{
char incomingChar = Serial.read();
switch (incomingChar)
{
case 'R': currentInput = Input::Reset; break;
case 'A': currentInput = Input::Backward; break;
case 'D': currentInput = Input::Forward; break;
default: break;
}
}
}La implementación tabular tiene ventajas en ciertas ocasiones. La ejecución del código es ligeramente más eficiente, dado que, en lugar de computar condicionales para las transiciones de estado y las acciones asociadas, accedemos directamente a través de los índices de la matriz.
Además, en ciertas ocasiones puede ser ligeramente más eficiente en el uso de la memoria, ya que las transiciones pueden ser mapeadas directamente en la memoria de programa (ROM), en lugar de en la memoria dinámica (RAM).
Por último, es más sencillo cambiar el comportamiento de la red, simplemente alterando la matriz de transición. Este cambio puede, por ejemplo, actualizarse desde una SD, o recibirse por un medio de comunicación (UART, Bluetooth, Wifi…).
Sin embargo, es considerablemente más restrictiva. Cualquier entrada a la máquina tiene que ser mapeada a un input, lo cual hace que sea contraproducente en el caso (muy frecuente) de tener transiciones con condiciones combinadas (por ejemplo, en el caso de condición A&B, tendríamos que crear una nueva entrada), temporizaciones, etc…
En cualquier caso, no era posible hacer una entrada sobre máquinas de estados finitos sin presentar una aproximación tabular al problema. Así que aquí queda como alternativa, con respectivas ventajas y desventajas.
Máquina de estados en una librería
Por último, la opción más útil y conveniente es encapsular la máquina de estados finitos en un objeto. Aquí tenemos la librería StateMachine que permite implementar máquinas de estado en un procesador como Arduino.
Con esta librería, el código de este ejemplo quedaría así.
#include "StateMachineLib.h"
enum State
{
PosicionA = 0,
PosicionB = 1,
PosicionC = 2,
PosicionD = 3
};
enum Input
{
Reset = 0,
Forward = 1,
Backward = 2,
Unknown = 3,
};
StateMachine stateMachine(4, 9);
Input input;
void setupStateMachine()
{
stateMachine.AddTransition(PosicionA, PosicionB, []() { return input == Forward; });
stateMachine.AddTransition(PosicionB, PosicionA, []() { return input == Backward; });
stateMachine.AddTransition(PosicionB, PosicionC, []() { return input == Forward; });
stateMachine.AddTransition(PosicionB, PosicionA, []() { return input == Reset; });
stateMachine.AddTransition(PosicionC, PosicionB, []() { return input == Backward; });
stateMachine.AddTransition(PosicionC, PosicionD, []() { return input == Forward; });
stateMachine.AddTransition(PosicionC, PosicionA, []() { return input == Reset; });
stateMachine.AddTransition(PosicionD, PosicionC, []() { return input == Backward; });
stateMachine.AddTransition(PosicionD, PosicionA, []() { return input == Reset; });
stateMachine.SetOnEntering(PosicionA, outputA);
stateMachine.SetOnEntering(PosicionB, outputB);
stateMachine.SetOnEntering(PosicionC, outputC);
stateMachine.SetOnEntering(PosicionD, outputD);
stateMachine.SetOnLeaving(PosicionA, []() {Serial.println("Leaving A"); });
stateMachine.SetOnLeaving(PosicionB, []() {Serial.println("Leaving B"); });
stateMachine.SetOnLeaving(PosicionC, []() {Serial.println("Leaving C"); });
stateMachine.SetOnLeaving(PosicionD, []() {Serial.println("Leaving D"); });
}
void setup()
{
Serial.begin(9600);
Serial.println("Starting State Machine...");
setupStateMachine();
Serial.println("Start Machine Started");
stateMachine.SetState(PosicionA, false, true);
}
void loop()
{
input = static_cast<Input>(readInput());
stateMachine.Update();
}
int readInput()
{
Input currentInput = Input::Unknown;
if (Serial.available())
{
char incomingChar = Serial.read();
switch (incomingChar)
{
case 'R': currentInput = Input::Reset; break;
case 'A': currentInput = Input::Backward; break;
case 'D': currentInput = Input::Forward; break;
default: break;
}
}
return currentInput;
}
void outputA()
{
Serial.println("A B C D");
Serial.println("X ");
Serial.println();
}
void outputB()
{
Serial.println("A B C D");
Serial.println(" X ");
Serial.println();
}
void outputC()
{
Serial.println("A B C D");
Serial.println(" X ");
Serial.println();
}
void outputD()
{
Serial.println("A B C D");
Serial.println(" X");
Serial.println();
}La ventaja de tener la lógica en una clase es que es mucho más cómodo de usar, el código queda más limpio y compacto, y es más fácilmente mantenerle y escalable.
La desventaja es que tendremos una ligera penalización de rendimiento. En la mayoría de casos esto no tendrá la menor importancia y es perfectamente asumible, frente a la ventaja de comodidad y código.
Descarga el código
Todo el código de esta entrada está disponible para su descarga en Github. 