if1.net-schulbuch.deProjekt Ampelsteuerung: Automatentheorie
Ein Automat ist in der Informatik das theoretische Modell eines digitalen Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der Fähigkeiten erlaubt es, das Verhalten eines Automaten leichter zu verstehen und zu vergleichen.
Automaten spielen in der praktischen Informatik eine entscheidende Rolle. So werden zum Beispiel in der Digitaltechnik Automaten zur Steuerung in digitalen und hybriden Systemen eingesetzt. Solche Steuerungsautomaten haben viele Anwendungen. Wir kennen sie meistens aus Haushaltsgeräten. Aber auch die Steuerung einer Ampelkreuzung erfolgt durch einen Automaten.
Das grundsätzliche Verhalten eines Automaten ist immer gleich: Dem Automaten wird von außen eine Eingabe als Folge von Zeichen oder Signalen vorgelegt. Der Automat befindet sich in einem bestimmten Zustand. Jedes Mal, wenn ein Eingabezeichen oder -signal eintrifft, kann sich abhängig vom Eingabezeichen und dem gegenwärtigen Zustand ein neuer Zustand, der Folgezustand, einstellen. Man kann die Menge der möglichen Zustandsübergänge, die das Verhalten des Automaten definiert, als das Programm des Automaten verstehen.
Ein endlicher Automat (engl.: finite state machine (FSM)) ist ein theoretisches Modell eines Verhaltens, bestehend aus endlich vielen Zuständen, Zustandsübergängen und Aktionen.
Endliche Automaten werden in der Informatik üblicherweise durch Zustandsübergangsdiagramme, Übergangstabellen oder mathematische Modelle beschrieben.
Das Zustandsübergangsdiagramm für die Steuerung der Ampelkreuzung kann man wie abgebildet darstellen. Die Zustände, die der Automat einnimmt werden als Kreise dargestellt. Die Pfeile stellen die Übergangsmöglichkeiten von einem Zustand in einen anderen dar. An den Pfeilen werden die Signale oder Zeichen notiert, die als Eingabe den Übergang auslösen. Im Kreis selbst wird der Zustand beschrieben. Diese Beschreibung kann auch in einer Tabelle erfolgen.
Zustandsübergangsdiagramm für die Steuerung der Ampelkreuzung
Als Übergangssignal ist hier eine Stoppuhr abgebildet, die nach einem festgelegten Zeitraum den Übergang auslöst. Die Zustände haben Namen. Diese kann man im Kreis oder wie in diesem Falle direkt darüber notieren.
 |
PYTHON ist ideal geeignet für die Umsetzung endlicher Automaten. Wenn der Automat gestartet wird (durch Anklicken der grünen Fahne), dann werden die Zustände der Reihe nach wiederholt durchlaufen. Die Schleife sendet der Reihe nach vier verschiedene Signale, die den Übergang in den dazugehörigen Zustand bewirken und wartet, bis dieser "fertig" ist. Die Zustände selbst werden unabhängig voneinander als eigene Skripte realisiert, die jedes auf ihr eigenes Signal (Phase1, Phase2, ... ) reagieren. Sie schalten die Lampen der Ampeln passend zum Zustand und starten die Stoppuhr (warte x Sek.), nach deren Ablauf der Übergang in den nächsten Zustand erfolgt. Eine der guten Eigenschaften von SCRATCH ist, dass man jedes der so formulierten Phasen-Skripte einzelnd und unabhängig voneinander testen und korrigieren kann. Ein Klick auf den "Kopf" des Skripts lässt genau nur dieses ablaufen. Das Ergebnis kann man am Steckbrett beobachten. |
 |
Aufgabe 1: Ein Skript in SCRATCH umsetzen "Zerlege" dein im letzten Kapitel erstelltes Skript zur Steuerung der Ampelkreuzung nach obigem Vorbild und teste es wie beschrieben. |
|
Aufgabe 2: In der Aufgabe 3 zur Ampelkreuzung hast du einen erweiterten Signalplan mit Hilfe einer Tabellenkalkulation erarbeitet. Nimm dir deine Lösung vor und stelle das zu deinem Signalplan passende Zustandsübergangsdiagramm nach obigem Vorbild dar. Notiere anstelle des Symbols für die Uhr immer die Zeit in Sekunden, nach der der Übergang erfolgen soll. |
Ein Zustandübergangsdiagramm zeichnen könnenIn der Aufgabe 4 zur Steuerung einer einzelnen Ampel hast du einen "Nachtbetrieb" erarbeitet. Wir können den obigen Automaten um die Darstellung dieses Nachtbetriebe erweitern. Dazu stellen wir fest, dass es von einem Zustand verschiedene Pfade in den nächsten Zustand geben kann (siehe Phase4 oder Phase1.2). In diesem Falle wird der ausgewählte Weg eindeutig durch verschiedene Stoppuhren vorgegeben. In Phase4 löst die rechte Stoppuhr nach einer festgelegten Zahl von Sekunden den Übergang zu Phase1 aus. Die andere Stoppuhr (unten) löst den Übergang zu Phase1.1 bei Überschreiten einer festen Uhrzeit aus (etwa um 21:00 Uhr). Die untere Stoppuhr am Symbol der Phase1.2 löst den Übergang zu Phase1 ab 06:00 Uhr aus.
Die Zusätzliche eingeführte Phase0 ist der Anfangszustand (ausgeschaltete Ampelanlage). Durch Einschalten (Pfeilsymbol) erfolgt sofort der Übergang zum Zustand Phase1.
 |
Aufgabe 3: Ein Zustandübergangsdiagramm in SCRTACH umsetzen Erweitere dein zu Aufgabe 1 erstelltes Skript um die Steuerung des "Nachtteils".
Die Aufgabe erscheint auf den ersten Blick einfach zu lösen. Erst bei Versuchen zur Umsetzung wirst du auf verschiedene Probleme stoßen. Du solltest versuchen, schriftlich zu notieren, an welchen Stellen genau die Schwierigkeiten auftreten und worin sie deiner Meinung nach begründet sind. |
Hinweis zur Lösung: Im Befehlsvorrat "Fühlen" gibt es die Stoppuhr, die durch das Setzen des Häkchens im Auswahlfeld auf der Bühne sichtbare wird. Diese Stoppuhr läuft und zeigt die verstrichenen Sekunden. Man kann ihren Wert in einem Skript verwenden, wie das folgende Beispiel zeigt:
|
Bevor hier eine Lösung der Aufgabe 3 beschrieben wird, wollen wir das obige Zustandsübergangsdiagramm in einer etwas anderen Form darstellen.
Neu sind die beiden Rahmen, die den Tag- und den Nacht-Betrieb einrahmen. Man kann das, was in diesen beiden Rahmen dargestellt ist, jeweils als einen eigene Automaten betrachten. Diese zwei Automaten für den Betrieb am "Tag" und in der "Nacht" sind unabhängig voneinander problemlos nach obiger Einführung in SCRATCH zu übertragen. Die Idee ist, jeden der beiden Automaten unabhängig voneiander zu Testen und danach einen neuen übergeordneten Automaten zu schaffen, der die beiden Automaten "Tag" und "Nacht" steuert. Diese Idee ist unter der Grafik beschrieben.
Die vier Skripte für die Steuerung der Phasen 1 bis 4 sind schon fertig. Wir ergänzen diese um zwei Skripte zur Steuerung der Nachtphasen.
Wir haben also jetzt alle sechs vorhandenen Zustände mit getesteten Skripten hinterlegt.
Nun ist der Rest einfacher als erwartet.
Unser "altes" Steuerskript für den Tagautomaten erhält einen neuen Kopf: "Wenn Fahne angeklickt" wird ersetzt durch "Wenn ich 'Tag' empfange". Testen.
Ganz analog verfassen wir ein Skript zur Steuerung der beiden Nachtphasen. Testen.
Dann entwerfen wir den übergeordneten Automaten.
Wir starten den Automaten genau um 00:00 Uhr, also Mitternacht.
Er beginnt also mit der Nachtphase. Diese dauert solange bis die Stoppuhr den Wert von 180 Sekunden überschritten hat.
Dann beginnt die Tagphase. Sie dauert bis ...
Dann kommt wieder die Nachtphase bis ...
Der Tag ist um. Er hat allerding nur 10 Minuten gedauert!
Wenn wir die Werte für die Stoppuhr anpassen, dann läuft der Automat wie erwartet 24 Stunden.
Wenn der Automat tagelang laufen soll, dann müssen wir die letzten drei Schleifen nur in eine weitere "unendliche" Schleife packen.
Jetzt steht dem mehrtägigen Test nichts mehr im Wege.