Zustandsautomaten sind eine wichtige Grundlage der theoretischen Informatik. In diesem Artikel geht es in erster Linie darum, wie das Konzept praktisch dazu verwendet werden kann, um Handlungsabläufe von Robotern zu programmieren. Deshalb verwenden wir in den ersten Abschnitten Begriffe, die uns intuitiver erscheinen als die in einem anderen Kontext entstandenen Fachbegriffe. Um den Einstieg in die Theorie zu vereinfachen, haben wir die Fachbegriffe in Klammern hinzugefügt.

Hier geht es um eine Problemstellung, das so alt wie die Informatik (und älter als die ersten Computer) ist:

Wie bringe ich einer Maschine bei, in unterschiedliche Situationen auf unterschiedliche Reize angemessen zu reagieren?

Es lohnt sich, diese Frage einmal genauer unter die Lupe zu nehmen. Offenbar gibt es:

• unterschiedliche Reaktionen (Ausgaben) - z.B. kann ein Roboter vorwärts, rückwärts oder auf der Stelle im Kreis fahren
• unterschiedliche Reize (Eingaben) - z.B. kann vor dem Roboter eine Wand, ein Mensch oder ein leerer Raum erkannt werden.
• unterschiedliche Situationen (Zustände) - z.B. Auf der Suche nach der Steckdose, auf der Flucht vor einem Gegner oder im Ruhezustand.

Es reicht also nicht aus, auf einen bestimmten Reiz/Eingabe stets mit der gleichen Aktion/Ausgabe zu reagieren. Um eine Steckdose zu finden, ist es eine vielleicht gute Idee direkt auf die nächste Wand zuzufahren - beim Ausweichen vor einem Verfolger eher nicht…

Man kann sich vorstellen, dass die Sache schnell unübersichtlich wird. Und wenn wichtige Kombinationen von Eingaben und Situationen unberücksichtigt bleiben, gibt es Probleme.

Die ganze Sache wird klarer, wenn man sie strukturiert aufzeichnet. Dabei kommt uns eine interessante Erkenntnis der theoretischen Informatik zu pass:

Es reicht aus, beim Eintreten einer Situation (Zustand) genau eine festgelegte Handlung (Ausgabe) auszuführen und erst danach die Eingabedaten anzuschauen und anhand ihrer zu entscheiden, welche Situation als nächstes vorliegt.

Handlungsmuster, die eine komplexere Abfolge von Eingaben überprüfen, Handeln und Zustände wechseln benötigen (Mealy Automat), lassen sich nach einem einfachen Schema in solche einfacher strukturierten Abfolgen (Moore Automat) zerlegen.

Wir brauchen also nur die Zustände und Bedingungen für einen Zustandswechsel aufzuschreiben, um die Struktur einer so aufgebauten Strategie vollständig zu beschreiben. Zusätzlich brauchen wir eine Liste, die für jeden Situation (Zustand) eine Aktion (Ausgabe) enthält, die ausgeführt wird, wenn die Situation eintritt (der Zustand betreten wird).

Genug Theorie!

Alles wird viel anschaulicher, wenn wir nach und nach alles, was der Roboter tun soll, nach der oben beschriebenen Struktur in einem Grafen aufzeichnen:

Ein Grund, der die Modellierung eines Verhaltens als Zustandsautomat so attraktiv macht, ist dass die Umsetzung in ein funktionierendes Programm sehr einfach ist.

Als erstes brauchen wir etwas, in dem wir den aktuellen Zustand speichern. Diese Variable bildet sozusagen das Gedächtnis des Zustandsautomaten. Besonders eignet sich hierfür ein sogenannter enum wert, der eine komfortable Möglichkeit bietet, verschiedenen Werten Namen zu geben:

//wir definieren einen neuen Variablentypen "ZustandsTyp", der die Werte standby, geradeau und drehen annehmen kann.
enum ZustandsTyp{
 standby,
 geradeaus,
 drehen
}
 
// Die eigentliche Variable definieren wir hier - und geben gleich einen Anfangswert an:
ZustandsTyp aktuellerZustand= standby; 

Hinweis: In Processing muss die Definition des enums in einer eigenen Datei („Tab“) mit der Endung .java stehen. (vgl. auch http://stackoverflow.com/questions/13370090/enums-in-processing-2-0)

Jetzt brauchen wir noch etwas, das je nach aktuellem Zustand unterschiedlichen Code ausführt.
Dafür eignet sich am besten das switch/case statement. Es funktioniert wie eine if-abfrage, kann aber zwischen mehr als zwei Alternativen auswählen. Sie könnte z.B. zentral in der Hauptschleife des Programms immer wieder durchlaufen:

void loop(){
  // führe unterschiedlichen Code aus, je nach dem welchen Wert die Variable aktuellerZustand hat
  switch(aktuellerZustand){
  case standby: // alles was danach kommt, wird ausgeführt, wenn 'aktuellerZustand' den Wert 'standby' hat.
    //führe die oben beschriebene Funktion für den standby Zustand aus und verwende ihren Rückgabewert als neuen Zustand.
    // hier kommt mal standby-code hin
    break; // 'break' verhindert, dass der ganze Rest, der danach kommt, auch noch ausgeführt wird. Also nicht vergessen...
  case geradeaus:
    // hier kommt mal der code zum geradeausfahren hin
    break;
  case wenden:
   // hier kommt der code zum wenden hin
   break;
  }
}

Um den Überblick zu wahren, empfiehlt es sich sehr, den Code für jeden Zustand in eine einzelne Funktion zu packen. Die Struktur dieser Funktion ist immer gleich:

1. Die Aktionen durchführen, die für diesen Zustand/Situation passen. (Also z.B. Motoren anmachen oder einen timer starten)
2. Die Eingabedaten (also z.B. Sensoren oder Timer) auslesen, die darüber entscheiden, welcher Zustand als nächstes betreten werden soll.
3. Den nächsten Zustand festlegen. (Besonders bequem geht das, indem man den neuen Zustand als Rückgabewert der Funktion an die Hauptschleife zurückgibt)

Für den Standby-Zustand könnte diese Funktion z.B. konkret so aussehen:

//deklariere eine Funktion, die einen Wert vom Typ 'ZustandsTyp' zurückgibt
ZustandsTyp standbyFun(){
  ////////////////////////////////////
  //Anfangsaktion: Was ist zu tun?
  ////////////////////////////////////
 
  //wir schalten die Motoren aus.
  motorLinks.setSpeed(0);  //die Details wären noch zu regeln...
  motorRechts.setSpeed(0);
 
  ////////////////////////////////////
  //Eingabe und Entscheidung für nächsten Zustand
  ////////////////////////////////////
 
  // Das onOffButtonPin Objekt ist global deklariert und kümmert sich um das Erkennen von neuen Tastendrücken.
  // Wie so etwas gehen kann, steht z.B. im 'ButtonDebounce' Beispiel von Arduino
  if(onOffButton.newPushDetected()){
    //wechsle auf Knopfdruck in den Fahrmodus
    return(geradeaus);
  }else{
    // bleibe im Standby
    return(standby);
  }
}

Die oben definierten Funktionen können wir jetzt einfach in den entprechenden Abschnitten des switch/case Statements aufrufen. Den Rückgabewert der Funktion speichern wir dabei in der Zustandsvariablen für die nächste Runde.

void loop(){
  switch(aktuellerZustand){
  case standby:
    //führe die oben beschriebene Funktion für den standby Zustand aus und verwende ihren Rückgabewert als neuen Zustand.
    aktuellerZustand=standbyFun();
    break;
  case geradeaus:
    aktuellerZustand=geradeausFun();
    break;
  case wenden:
    aktuellerZustand=wendenFun();
   break;
  }
}

Die so erzeugten Programme lassen sich sehr einfach nachträglich um weitere Zustände erweitern, ohne dass die Übersichtlichkeit gefährdet wird. Es bietet sich daher an, mit einer einfachen Grundstruktur zu starten und dann nach und nach die komplexeren Funktionen hinzuzufügen.

Die bisher vorgestellte relativ starre Struktur von Aktion, Messung, Zustandsübergang entspricht dem Konzept des Moore-Automaten. Sie hat die großen Vorteil, dass sie sich sehr übersichtlich graphisch darstellen lässt.

Bei bestimmten Problemen führt sie aber zu umständlichen Konstrukten. Wir wollen das am Beispiel des 'Wenden' Zustands illustrieren:

ZustandsTyp wendenFun(){
  ////////////////////////////////////
  //Anfangsaktion: Was ist zu tun?
  ////////////////////////////////////
  // Wir drehen uns im , indem wir die Räder in unterschiedlich Richtungen drehen lassen
  motorLinks.setSpeed(-100); 
  motorRechts.setSpeed(100);
  navigationModule.updateData();
 
  ////////////////////////////////////
  //Eingabe und Entscheidung für nächsten Zustand
  ////////////////////////////////////
  // Erstmal schauen, ob der Benutzer die Kiste ausschalten will:
  if(onOffButton.newPushDetected()){
    return(standby);
  }else{
    //wenn wir genug gedreht haben, fahren wir wieder geradeaus, sonst drehen wir weiter
    if(navigationModule.turnAngle>=navigationModule.desiredAngle){
      return(geradeaus);
    }else{
      return(wenden);
    }
  }
}

Jetzt gibt es aber ein Problem: Wann wird der gewünschte Winkel eingestellt und der bisher gefahrene zurückgesetzt?

Wir können das über die Einführung eines weiteren Zustands lösen, in dem nichts anderes passiert, als 'die Uhr zu stellen':

Die Funktion für diesen Zustand könnte dann z.B. so aussehen:

ZustandsTyp wendeStartenFun(){
  // die Wende ist abgeschlossen, wenn der Winkel sich um 180° (PI radian) geändert hat:
  navigationModule.desiredAngle=navigationModule.turnAngle+PI; 
  return (drehen); // als nächstes soll gedreht werden.
}

In bestimmten Fällen kann das zu einer großen Anzahl von Behelfszuständen führen, die die Übersichtlichkeit vermindern.

Dann kann es sinnvoll sein, beim Wechsel in einen Zustand direkt die entsprechende Aktion durchzuführen. In unserem Beispiel könnte also anstatt den zusätzlichen Zustand 'wendeStarten' einzuführen die Funktion des Zustands 'geradeaus' angepasst werden:

ZustandsTyp geradeauFun(){
  ////////////////////////////////////
  //Anfangsaktion: Was ist zu tun?
  ////////////////////////////////////
  // Wir fahren geradeaus...
  motorLinks.setSpeed(100); 
  motorRechts.setSpeed(100);
  navigationModule.updateData();
 
  ////////////////////////////////////
  //Eingabe und Entscheidung für nächsten Zustand
  ////////////////////////////////////
  // Erstmal schauen, ob der Benutzer die Kiste ausschalten will:
  if(onOffButton.newPushDetected()){
    return(standby);
  }else{
    // wie genau die Kollision erkannt wird, wäre noch zu klären...
    if(collisionDetected){
      // Hier wird eine Aktion ausgeführt - in einem Moore Automaten ginge das nicht:
      // Die Wende ist abgeschlossen, wenn der Winkel sich um 180° (PI radian) geändert hat:
      navigationModule.desiredAngle=navigationModule.turnAngle+PI; 
      return (drehen); // als nächstes soll gedreht werden.
    }else{
      return(geradeaus);
    }
  }
}

Diese Zusätzlichen Aktionen beim Zustandswechsel können auch in den Grafen eingetragen werden (hier in rot):

Wer etwas mathematisch denkt und gewohnt ist, sich Gedanken über die Struktur von Verfahren und Algorithmen zu machen, wird sich jetzt einige Fragen stellen:

Ja, man kann: http://de.wikipedia.org/wiki/Moore-Automat

Hier wird es interessant!
Um es kurz zu fassen: Ja.
Fragen wie diese haben ein ganzes Gebiet der theorethischen Informatik hervorgebracht - die Berechenbarkeitstheorie. Die Frage, welche (formalen) Sprachen sich durch formal eingeschränkte 'Rechner' erkennen lassen, führt zur http://de.wikipedia.org/wiki/Chomsky-Hierarchie

Jein.

Ein endlicher Zustandsautomat im formalen Sinne speichert Informationen ausschließlich in Form des aktuell vorliegenden Zustandes. So bricht z.B. jede Aktion, die Spuren hinterlässt (also z.B das Setzen einer anderen Variable als des aktuellen Zustands) aus diesem Paradigma aus. Solche Aktionen dürfen dann nicht ohne Weiteres in einem formalen Beweis für bestimmte Eigenschaften des Systems verwendet werden, der auf der Automatentheorie aufbaut.

In der Praxis spielt das z.B. dann eine Rolle, wenn anhand einer mathematisch-formalen Argumentation bewiesen werden soll, dass der Automat für alle Arten von Eingaben das erwünschte Verhalten zeigt. Wenn dies nur der Fall ist, weil in einer Aktion eine bestimmte Variable gesetzt, und in einem anderen Zustand zur Entscheidung herangezogen wird, ist solch ein Beweis ungleich schwerer zu führen, als bei einem Automaten, der nicht auf so etwas angewiesen ist.

Trotzdem bleibt das Zustandsdiagramm und die sich aus ihm ergebende Programmstruktur auch in diesen Fällen oft ein gutes Hilfsmittel zur Dokumentation und Weiterentwicklung des Verhaltens.