Zustandsautomaten für Fortgeschrittene

[Serenifly]

Ich möchte hier man zwei alternative Versionen von FSMs zeigen, die über das einfache switch/case hinausgehen.

Wenn hier jemand Zustandsautomaten erklärt bekommt, wird i.d.R. zu switch/case gegriffen. Das ist völlig in Ordnung. Es ist einfach zu verstehen (und für Anfänger immer noch kompliziert genug), einfach zu implementieren und reicht vor allem für viele einfache Anwendungen aus. Ich sage also nicht, dass es schlecht ist oder dass man es in allen Fällen ersetzen sollte!

Es wird allerdings auch mit zunehmenden Zuständen und mehr Code pro Zustand schnell unübersichtlich, da der ganze Code an einer Stelle steht und die Zustände nicht voneinander getrennt sind.

Ein schöner - und immer noch sehr einfacher - Weg den Code für die Zustände zu trennen ist es jede Funktionen einen Zeiger auf die nachfolgende Funktion zurückgeben zu lassen. Dadurch hat man für jeden Zustand eine völlig getrennte Funktion.



Der Beispiel Code wechselt lediglich zwischen zwei Zuständen in dem unterschiedlich lange der Funktionsname auf Serial ausgegeben wird.

Code: [Select]


/Funktionszeiger in struct verpacken um Abhängigkeitsrekursion aufzulösen
struct nextFunc
{
  nextFunc(*next)(void);  //Zeiger auf Funktion ohne Parameter die ein nextFunc struct zurück gibt
};


//Hilfsfunktion um Funktion in struct zu verpacken. Funktion übergeben um struct zu bekommen.
inline nextFunc getNext(nextFunc (*func)(void))
{
  nextFunc next = { func };
  return next;
}

void setup()
{
  Serial.begin(9600);
}

void loop()
{
  static nextFunc next = { function_1 }; //Zeiger auf nächste Funktion. Wird mit Start-Funktion initalisiert
  next = next.next(); //Zeiger auf nächste Funktion holen und aufrufen. Rückgabewert abspeichern
}

//Verzögerung beim Umschalten der Funktionen
bool check_timer(unsigned long interval)
{
  static unsigned long previousMillis;

  if (millis() - previousMillis > interval)
  {
    previousMillis = millis();
    return true;
  }
  else
    return false;
}

//Verzögerung der Serial Ausgabe. Könnte auch LED blinken sein
void print_serial(const char* str)
{
  static unsigned long previousMillis;

  if (millis() - previousMillis > 1000)
  {
    previousMillis = millis();
    Serial.println(str);
  }
}

struct nextFunc function_1()
{
  print_serial("Function 1");

  if (check_timer(5000)) //wenn Zeit abgelaufen nächste Funktion zurückgeben
    return getNext(function_2);

  return getNext(function_1); //gleiche Funktion aufrufen
}

struct nextFunc function_2()
{
  print_serial("Function 2");

  if (check_timer(3000))
    return getNext(function_1);

  return getNext(function_2);
}




Der Zeiger ist einem struct verpackt, da man sonst eine Funktion deklarieren müsste die einen Funktionszeiger zurück gibt, der auf die Funktion zeigt die man gerade deklarieren will. Das struct löst diese Rekursion auf. Alternativ könnte man jede Funktion einen void Pointer zurückgeben lassen und diesen vor dem Aufrufen auf den eigentlichen Typ casten. Ist vielleicht einfacher..


Next: FSM mit Zustandsübergangstabelle

[Serenifly]

Eine weitere Version die man oft sieht ist eine Zustandsübergangstabelle. Diese ist vor allem interessant wenn die Zustände und die Übergänge umfangreicher werden und wenn man mehr externe Ereignisse hat die Zustandsübergänge auslösen. Aber auch dann wird es irgendwann unübersichtlich. Da gibt es glaube auch Makros um die Tabelle automatisch zu erzeugen.

In dieser Version werden alle Zustände, die Ereignisse und die Aktionen in eine Tabelle eingetragenen und diese wird automatisch bearbeiten. Praktisch ist dies ein zwei-dimensionales Array.

Auch hier gilt: man muss nicht gleich hierzu greifen. Gerade für einfache Anwendung wird das zu kompliziert sein. Aber es ist eine Option.


Das Beispiel ist vielleicht nicht so anschaulich und bei sowas würde ich diesen Ansatz auch nicht empfehlen. Aber mir ging es darum was zu haben, dass ohne Zusatz-Hardware läuft.

Die onboard LED an Pin 13 blinkt dabei 3 Geschwindigkeiten die automatisch wechseln. Außerdem kann man den Zustand wechseln wenn man ein Zeichen auf Serial eingibt. Dann wird immer eins weiter geschaltet. Außerdem kann man so das Blinken ganz ausschalten, was im automatischen Modus nicht geht.



Ähnlich wie bei switch/case hat man hier ein enum mit den Zuständen und eine Variable für den aktuellen Zustand:

Code: [Select]


enum states
{
  OFF,
  SLOW,
  MEDIUM,
  FAST
} currentState;

Das ist nötig um das Array zu adressieren

Und ein enum für die Ereignisse:

Code: [Select]


enum event
{
  TIMER,
  BUTTON
};


Der Zustand hat folgende Eigenschaften:
* die Funktion die während des Zustands aufgerufen werden soll
* der nächste Zustand
* die Funktion die beim Zustandsübergang aufgerufen werden soll

Code: [Select]


typedef struct
{
  funcPtr currentStateFunc;     //aktuelle Zustandsfunktion
  states nextSate;       //nächster Zustand
  funcPtr actionToDo;       //Aktion bei Zustandsübergang
} stateElement;



Dann die eigentliche Tabelle:

Code: [Select]


stateElement stateMatrix[4][2] =
{
                /* TIMER EVENT*/                               /* BUTTON EVENT*/
  /* OFF */    { { NULL, OFF, NULL },                    { state_off, SLOW, action_slow }       },
  /* SLOW */   { { state_slow, MEDIUM, action_medium },  { state_slow, MEDIUM, action_medium }  },
  /* MEDIUM */ { { state_medium, FAST, action_fast },    { state_medium, FAST, action_fast }    },
  /* FAST */   { { state_fast, SLOW, action_slow },      { state_fast, OFF, action_off }        }
};


Die Reihen sind die Zustände. Die Spalten sind die Events. Dann gibt man für jeden Fall die Funktion an die im aktuellen Zustand aufgerufen werden soll, den nächsten Zustand für den Fall dass das jeweilige Ereignis eintritt und die Funktion die in diesem Fall aufgerufen werden soll (von links nach rechts).

Wie man sieht kann man auch NULL für Zustandsfunktionen oder Übergangsfunktionen angeben. Oder man kann angeben dass für einen Zustand bei einem Event nichts geschehen soll, wenn man in den gleichen Zustand wechselt. In diesem Fall müsste man z.B. für den OFF Zustand keine Funktion aufrufen. Die LED auf LOW zu setzen könnte man auch in action_slow() machen.

Das lässt sich auch modifizieren. Für manchen Anwendungen will man vielleicht beim Übergang niemals eine Aktion ausführen. Dann kann man das auch komplett entfernen.

In dem Beispiel gibt es nur einen Taster. Man könnte das auch auf zwei Taster erweitern und dann +/- Schalten. Dann hätte man zwei Button Events und würde jeweils die Reihenfolge des nächsten Zustands anders herum machen


Und der komplette Code:

Code: [Select]


enum states
{
  OFF,
  SLOW,
  MEDIUM,
  FAST
} currentState;

enum event
{
  TIMER,
  BUTTON
};

void state_change(event e); //Prototyp ist nötig weil der Arduino Prototyp Parser hier versagt
typedef void(*funcPtr)(void); //typedef für Funktionszeiger
funcPtr currentStateFunction;  //aktuelle Funktion

unsigned long previousTimerMillis;

typedef struct
{
  funcPtr currentStateFunc; //aktuelle Zustandsfunktion
  states nextSate; //nächster Zustand
  funcPtr actionToDo; //Aktion bei Zustandsübergang
} stateElement;

stateElement stateMatrix[4][2] =
{
                /* TIMER EVENT*/                               /* BUTTON EVENT*/
  /* OFF */    { { NULL, OFF, NULL },                    { state_off, SLOW, action_slow }       },
  /* SLOW */   { { state_slow, MEDIUM, action_medium },  { state_slow, MEDIUM, action_medium }  },
  /* MEDIUM */ { { state_medium, FAST, action_fast },    { state_medium, FAST, action_fast }    },
  /* FAST */   { { state_fast, SLOW, action_slow },      { state_fast, OFF, action_off }        }
};

void setup()
{
  Serial.begin(9600);
  pinMode(13, OUTPUT);
  digitalWrite(13, LOW);

  //Ausgangszustand setzen
  currentState = SLOW;
  currentStateFunction = state_slow;
}

void loop()
{
  event_trigger();

  //aktuelle Zustandsfunktion ausführen
  if (currentStateFunction != NULL)
    (*currentStateFunction)();
}

//Zustand ändern
void state_change(event e)
{
  //hole Element in Abhänigkeit von aktuellem Zustand und Ereignis
  stateElement stateEvaluation = stateMatrix[currentState][e];

  //setze nächsten Zustand
  currentState = stateEvaluation.nextSate;

  //setze aktuelle Zustandsfunktion
  currentStateFunction = stateMatrix[currentState][e].currentStateFunc;

  //Aktion ausführen
  if (stateEvaluation.actionToDo != NULL)
    (*stateEvaluation.actionToDo)();

  previousTimerMillis = millis();
}

//Events abfragen/auslösen. Hier kann man z.B. Taster oder Sensoren abfragen
void event_trigger()
{
  if (Serial.available())
  {
    Serial.read();
    state_change(BUTTON);
  }
  else if (check_timer(8000))
  {
    state_change(TIMER);
  }
}

void state_off()
{
  digitalWrite(13, LOW);
}

void state_slow()
{
  blink(1500);
}

void state_medium()
{
  blink(500);
}

void state_fast()
{
  blink(50);
}

void action_off()
{
  Serial.println("State OFF");
}

void action_slow()
{
  Serial.println("State SLOW");
}

void action_medium()
{
  Serial.println("State MEDIUM");
}

void action_fast()
{
  Serial.println("State FAST");
}

bool check_timer(unsigned long interval)
{
  if (millis() - previousTimerMillis > interval)
  {
    previousTimerMillis = millis();
    return true;
  }
  else
    return false;
}

void blink(unsigned long interval)
{
  static unsigned long previousMillis;

  if (millis() - previousMillis > interval)
  {
    previousMillis = millis();
    digitalWrite(13, !digitalRead(13));
  }
}


In event_trigger() werden die Ereignisse ausgelöst. Auf dem Arduino sind das Dinge wie Tastendrücken, Empfang von Daten, Meldungen von Sensoren, etc.

In state_change() wird dann der Zustand gewechselt. Der Funktion wird das Ereignis übergeben (was praktisch nur ein Array Index ist). Dann holt man sich aus der Tabelle den nächsten Zustand und die Funktionen die als nächstes aufgerufen werden sollen.

[udoklein]

Ich hätte auch noch was zum Thema FSM: Coroutinen und Gotos: http://blog.blinkenlight.net/experiments/dcf77/goto-considered-helpful/