Zum Hauptinhalt springen

Endliche Automaten (Finite State Machine)

Programme oder logische Systeme, welche eine endliche Anzahl verschiedener Zustände aufweisen und diese nach festgelegten Kriterien ändern sollen, können durch endliche Automaten (auch endliche Zustandsmaschine oder finit state machine - FSM) modelliert werden. Ein endlicher Automat soll ein Verhalten modellieren, welches auf einer endlichen Anzahl von Zuständen, Aktionen und Zustandsübergängen basiert.

Wichtige Begriffe​

Im Folgenden werden die Begriffe am Beispiel der blinkenden LED mit der millis()-Funktion erläutert:

  • Zustände speichern Information bzw. einen Status ab. Im Beispiel der blinkende LED wird dafür die Variable zustandLED verwendet, welche angibt, ob die LED an- oder ausgeschaltet ist. Zustände alleine ändern das System jedoch nicht, dafür ist immer eine Aktion notwendig!
  • Durch eine Aktion wird der Zustand des endlichen Automaten geändert. Wann ein bestimmter Zustand geändert bzw. angenommen wird, hängt von dem System ab. Bei der blinkenden LED wird der Zustand des Automaten mit dem Befehl digitalWrite(LED, zustandLED) nach der Zeitabfrage geändert.
  • Zustandsübergänge oder auch Zustandsänderungen werden in der Regel durch Programmverzweigungen wie if-else oder switch-case beschrieben. Sie geben an, unter welchen Bedingungen ein Zustand in einen anderen wechseln soll. Beim Blink-Beispiel gibt es genau zwei Zustandsänderungen: Anschalten und Ausschalten der LED.

Zustandsdiagramm​

Mit einem Zustandsdiagramm lassen sich endliche Automaten graphisch darstellen. Das abgebildete Zustandsdiagramm beschreibt den endlichen Automaten für die blinkende LED.

drawing

In einem Zustandsdiagramm wird das Verhalten eines endlichen Automaten anschaulich dargestellt. Die Zustände des Automaten werden hierbei mit Kreisen oder abgerundeten Vierecken abgebildet. Jeder Zustand darf nur einmal dargestellt werden.

Erlaubte Zustandsübergänge werden mit Pfeilen dargestellt. Aktionen, die zu Zustandsänderungen führen, müssen nicht unbedingt dargestellt werden, können aber für das Verständnis sehr hilfreich sein. Das Gleiche gilt für die Bedingungen, unter welchen der Automat seine Zustände ändert.

Im Allgemeinen gilt, so lange wie es dem Verständnis und der Übersichtlichkeit dient, sollten die Aktionen und die notwendigen Bedingungen vermerkt werden, ansonsten ist darauf zu verzichten.

Programmiertechniken​

Im Abschnitt Zeitkritische Aufgaben wurde der oben abgebildete Automat mit Hilfe der Variablen int zustandLED und der if-else Verzweigung programmiert. Bei Automaten mit mehr als nur zwei Zuständen oder bei geschachtelten Automaten gibt es jedoch einen besseren Ansatz, der das Programm übersichtlicher und lesbarer macht.

Ein etwas komplexerer Automat, welcher im Folgenden programmiert werden soll, lässt sich mit zwei LEDs erstellen. Ähnlich wie bei der blinkenden LED, wechselt der Automat nach einer vorgegeben Zeitspanne seinen Zustand. Im Zustandsdiagramm sind die vier möglichen Zustände mit den erlaubten Zustandsübergängen abgebildet.

drawing

enum Aufzählungstyp​

Das Schlüsselwort enum ermöglicht die Aufzählung von Konstanten. Mit enum wird ein Aufzählungstyp deklariert:

enum LedStates {AUS, LED1, LED12, LED2};  // Typendeklaration (Aufzählungstyp)

Mit dieser Zeile wird der Aufzählungstyp LedStates mit den Konstanten AUS, LED1, LED12, LED2 deklariert.

Nach dieser Deklaration ist es möglich, die Variable ledState als LedStates-Typ zu deklarieren und ihr den Wert AUS zuzuweisen.

LedStates ledState; // Variablendeklaration
ledState = AUS;     // Variablenzuweisung

Da der LedStates vorher als Aufzählungstyp deklariert wurde, kann der Variablen ledState nur einer der vorher deklarierten Werte zugewiesen werden. Hier wird der Variablen ledState der Wert AUS zugewiesen.

Wie bei einfachen Variablen kann die Deklaration und die Zuweisung auch in einer Zeile durchgeführt werden.

LedStates ledState  = AUS; // Variablendeklaration und Zuweisung

switch-case Verzweigung​

Ähnlich wie bei der if Verzweigung, ermöglicht es die switch-case Verzweigung, den Programmablauf in Abhängigkeit von verschiedene Bedingungen zu kontrollieren. Besonders geeignet ist die switch-case Verzweigung für den Fall, dass viele verschiedene Bedingungen abgefragt werden sollen.

Als einfaches Beispiel wird die Variable a ausgewertet. Für den Fall, dass a die Werte 1, 2 oder 3 annimmt, soll das Programm spezielle Anweisungen ausführen. Für alle anderen Werte von a wird der so genannte Default-Fall ausgeführt.

int a = 2;

// Nach dem Schlüsselwort `switch` folgt in Klammern der auszuwertende Ausdruck
switch (a)                      
{
  case 1:                       // Vergleicht `a` mit dem Wert nach case (hier 1).
    Serial.println("Fall 1.");        
    break;                      // Beendet die gesamte Switch-Verzweigung. 

  case 2:
    Serial.println("Fall 2.");  // Wird ausgewertet, da a=2 
    break;

  case 3:
    Serial.println("Fall 3.");
    break;

  default:                       // alle nicht aufgeführten Fälle
    Serial.println("Alle anderen Zustände.");
}

Arduino-Programmbeispiel​

Die switch-case Verzweigung eignet sich zusammen mit der enum Aufzählung besonders gut zur Programmierung eines Automaten. Am Beispiel des Automaten mit 2 LEDs soll das Grundprinzip erläutert werden.

#define pinLed1 6  // LED_1
#define pinLed2 5  // LED_2

// Zustände des Automaten als Aufzählungstyp deklarieren
enum LedStates {AUS, LED_1, LED_12, LED_2};
LedStates ledState = AUS;

unsigned long letzteZeit = 0;  //  Zeitpunkt letzte LED-Änderung
const    long intervall  = 500;    // Blinkintervall in ms (Konstante)

void setup() {
  pinMode(pinLed1, OUTPUT);
  pinMode(pinLed2, OUTPUT);
} 

void loop() {

  // Bedingung für den Zustandsübergang. Der Automat soll seinen Zustand 
  // nur ändern, wenn die angegebene Intervall-Zeit überschritten ist.
  if (millis() - letzteZeit >= intervall)
  {
    letzteZeit = millis();  // Zeitstempel für Zeitvergleich

    // Jeder `case` der switch-Verzweigung entspricht dem *alten* Zustand 
    // des Automaten und gibt an, in welchen neuen Zustand gewechselt werden 
    // soll. In der case-Anweisung wird der neue Zustand des Automaten 
    // aktualisiert. Der neue Zustand wird sofort aktiviert, die entsprechenden
    // LEDs werden an- oder ausgeschaltet.
    switch (ledState)
    {
      case AUS:                      // aktueller Zustand: AUS
        ledState = LED_1;            // neuer Zustand des Automaten: LED_1
        digitalWrite(pinLed1, HIGH); // LED_1 AN
        digitalWrite(pinLed2, LOW);  // LED_2 AUS
        break;                       // ohne `break` würde sofort 
                                     // 'case LED_2' ausgeführt werden

      case LED_1:                    // aktueller Zustand: LED 1 an
        ledState = LED_12;
        digitalWrite(pinLed1, HIGH);
        digitalWrite(pinLed2, HIGH);
        break;

      case LED_12:                   // aktueller Zustand: LED 1&2 an
        ledState = LED_2;
        digitalWrite(pinLed1, LOW);
        digitalWrite(pinLed2, HIGH);
        break;

      case LED_2:                    // aktueller Zustand: LED 2 an
        ledState = AUS;
        digitalWrite(pinLed1, LOW);
        digitalWrite(pinLed2, LOW);
        break;

        // Der Default-Fall wird nicht benötigt, da alle Wert abgefragt werden.
    }
  }
}

Automaten und Zustandsdiagramme sind besonders bei der Programmierung von Robotern sehr wichtig, da diese ein Vielzahl verschiedener Zustände einnehmen können.

Aufgaben

  1. Kopieren Sie des Beispielprogramm und lassen sie es auf Ihrem Arduino mit der entsprechenden Schaltung laufen. Untersuchen Sie, was passiert, wenn einige der break-Anweisung auskommentiert (// ) werden. Wie verhält sich dann Ihr Programm?

  2. Zeichnen Sie ein Zustandsdiagramm für den Automaten mit zwei LEDs, bei dem folgende Übergänge bzw. Zustände erlaubt sind. Nach dem letzten Zustand springt der Automat in der ersten Zustand zurück.

    alle Leds aus → Led 1 an, Led 2 aus → alle Leds aus → Led 1&2 an → alle LEDs aus → Led 2 an, Led 1 aus → . . .

  3. Schreiben Sie ein Programm für den obigen Automaten und testen Sie es an einer entsprechenden Schaltung.

  4. Ändern Sie das Programm für den ursprünglichen Automaten mit 2 LEDs so, dass für jeden der vier Zustände ein eigenes Zeitintervall (dTime1, dTime2,...) angegeben werden kann, in welchem er aktiv ist. Oder anders ausgedrückt, jeder der vier Zustände soll unterschiedlich lange aktiv sein.

  5. Programmieren Sie einen Reaktionstester. Bauen Sie dafür zuerst eine Schaltung mit zwei Tastern und zwei verschiedenfarbigen LEDs auf. Implementieren Sie folgendes Verhalten:

    1. Als Indikator, das der Test beginnen kann, leuchtet zu Beginn die LED 1 und auf dem seriellen Monitor wird folgender Text ausgegeben:

      -------------------------------
      Reaktionstester bereit!

    2. Anschließend wird der Taster S1 gedrückt. Auf dem seriellen Monitor erscheint der Text:

      Warten auf das rote Licht ...

      Jetzt wird gewartet bis die LED 2 aufleuchtet.

    3. Nach einer zufälligen Zeit leuchtet die LED 2 auf und die LED 1 fängt an schnell zu blinken. Von diesem Zeitpunkt wird die Zeit gemessen, bis der Taster 2 betätigt wird.

    4. Sobald der Taster 2 gedrückt wurde, erlischt die LED 1 und auf dem seriellen Monitor wird die Reaktionszeit in Sekunden angegeben:

      Reaktionszeit: 1,23 Sekunden
      -------------------------------

  6. Zeichnen Sie das Zustandsdiagramm für eine einfache Autoampel (mit den Bedingungen für die Zustandsübergänge). Für die Zeiten der einzelnen Ampelphasen gilt:

    • ROT: 3 Sekunden
    • ROT-GELB: 0.5 Sekunden
    • GRÜN: 3 Sekunden
    • GELB: 1 Sekunde

    Bauen Sie anschließend eine geeignete Schaltung auf und programmieren Sie mit der switch-case Anweisung und dem enum Datentyp den endlichen Automaten für die Ampel.

  7. Entwickeln Sie ein Programm und eine elektrische Schaltung zur Simulation einer Ampelanlage für Fußgänger (eine Fußgängerampel FA und eine Ampel für PKWs PA). Ähnlich wie bei echten Ampelanlagen für Fußgänger, darf die Fußgängerampel erst nach dem Betätigen eines Tasters (Anforderung durch einen Fußgänger) und einer gewissen Wartezeit auf Grün umschalten. Beachten Sie bei der Bearbeitung der Aufgabe folgende Punkte:

    • Erstellen Sie ein vollständiges Zustandsdiagramm für beide Ampeln. Recherchieren Sie die möglichen Zustände der Ampeln und benennen Sie diese sinnvoll (FArot, FAgruen, PArot, ...). Geben Sie im Zustandsdiagramm alle Zustände und Bedingungen für die Zustandsübergänge korrekt an.
    • Entwickeln Sie eine Schaltung für die Ampelanlage. Zeichnen Sie Ihre Schaltung auf und bauen Sie sie anschließend auf dem Steckbrett auf. Vergessen Sie nicht den Taster für die Fußgängeranforderung.
    • Schreiben Sie ein Programm, welches ihr Zustandsdiagramm umsetzt. Verwenden Sie die switch-case-Anweisung.