Komplexe Zustandsautomaten (FSM) implementieren

Es gibt ein paar nette Headerdateien, wo man den Zustandsautomaten in 
einer Pseudosyntax einträgt, und die dann zur Compilezeit ein 
switch/case draus bauen. Das hilft zwar bei der Übersichtlichkeit nicht 
unbedingt, aber dadurch kannst du 1:1 vom Diagramm in den Code und auch 
zurück vergleichen.

Überforderter schrieb:
> Nach welchen Stichworten kann ich googeln?

Hierarchischer Zustandsautomat?

Divide et impera!

Richtig 'teilen' will gelernt sein!

Thomas schrieb:
> Hast du nun deinen Zustandsautomaten vorab skizziert oder nicht?

Vielleicht braucht der TO noch einen Tipp, mit welcher SW er das machen 
könnte.

Bei MatLab-Stateflow kommt man per Doppelclick auf einen State in das 
Innere.

Aber Stateflow kann ich hier wohl kaum empfehlen.
Vielleicht hat jemand von Euch einen Tipp.

Ich hab fuer mich mal einen Simulator geschrieben, der alle Pfade 
durchgehen kann, um zu schauen, ob
- alle Zustaende erreicht und verlassen werden koennen,
- es Endlosloops gibt, die nicht mehr verlassen werden koennen
- wie lange es dauert, um von jedem Zustand in den sicheren Zustand zu 
gehen,

usw.
Man muss so eine State Machine natuerlich auch im Prozess in Echtzeit 
debuggen koennen. Das ist unbedingt vorzusehen. Dazu muss man sich von 
jeder State - und Substatemachine den aktuellen und den letzten Zustand 
ausgeben lassen koennen.

Ueber dieses Problem gibt es ein ganz nettes Buch von Miro Samek: 
Practical UML Statecharts in C/C++. Er stellt da ein ziemlich 
umfangreiches Framework vor mit dem man FSMs fuer eingebettete Systeme 
umsetzen kann.
Wir haben eine Untermenge davon in unserem System implementiert und sind 
sehr zufrieden.
Vielleicht sind eure Anwendungen noch komplexer, aber wir haben unter 
anderem erfolgreich eine hierarchische FSM mit insgesamt 24 States damit 
implementiert und es laesst sich auch ziemlich gut warten.
Wie bereits mehrfach von anderen angemerkt ist es dabei sehr wichtig 
vorher eine grafische Repraesentation zu erstellen und die auch synchron 
zum Code zu halten. Ich nutze dazu Dia, was zwar teilweise eine 
harkelige Bedienung hat, aber alles bietet was ich brauche.

Kopf hoch Überforderter ;-)

Überforderter schrieb:
> Gibt es vielleicht Alternativen zu FSM? Nach welchen Stichworten kann
> ich googeln? Was sag die aktuelle Forschung zu dem Thema?

Evtl. würde es helfen, wenn Du den Automaten in einer eigenen Sprach 
beschreiben kannst? (Stichwort wäre: DSL).

Ansonsten:
- Automatische Tests. Die Problem, die Du hier beschreibst sind super 
gut für unit Tests geeignet. Test Driven Development (Stichwort TDD) 
macht ausserdem einfach sehr viel Spaßt. Wenn Du eine gute Testabdeckung 
hast, dann kannst Du Deine Implementierung später einfach austauschen 
oder siehst einfach, wo Änderungen ggf. etwas kaput machen.
- Versuchen Baugruppen zu finden, die ihren eigenen Automaten haben. 
Häufig sind dann im Gesamtkontext nur bestimmte Zustände / 
Zustandwechsel einer Baugruppe interessant (gestört / nicht gestört).

HTH
Torsten

Überforderter schrieb:
> Gibt es vielleicht Alternativen zu FSM? Nach welchen Stichworten kann
> ich googeln? Was sag die aktuelle Forschung zu dem Thema?

Zum Gugglen: Systemarchitektur SysML.
Was du da vor dir hast ist zu komplex um nur mit ein paar 
Zustandsautomaten bewältigen zu können. Dein ganzes System kann 
beschrieben werden in einer Systemarchitektur, die das ganze in 
einzelnen Komponenten zerlegt. Für jeder dieser Komponenten kann dann 
eine Softwarearchitektur aufgesetzt werden (mit Ablaufdiagrammen, 
Zustandsautomaten und was sonst noch nötig ist).

BirgerT schrieb:
> Aufteilung in Funktionsgruppen ist immer möglich

Sehe ich auch so.
5 Bänder ergibt schonmal 5 FSM und noch eine FSM obendrüber, die sie 
aufruft.
Alles mit einer riesigen FSM zu erschlagen, gibt nur Chaos.

Thomas schrieb:
> Bleistift, Papier und Radiergummi?

Nur so kommt man schnell zum Ziel. Auf Papier sieht man vieles besser, 
als auf dem Bildschirm.

Überforderter schrieb:
> Aber der
> Bediener kann den Carrier an beliebiger Stelle wieder zurück stellen und
> das System muss den Carrier wieder an die richtige Stelle
> transportieren.

Klingt sportlich.
Aber solange man das nicht mit Papier und Bleistift gelöst hat, kann das 
eine beliebig teure Steuerung erst recht nicht.

gerhard schrieb:
>>Evtl. würde es helfen, wenn Du den Automaten in einer eigenen Sprach
>>beschreiben kannst? (Stichwort wäre: DSL).
> ich denke du meintest SDL oder?

Nein, er meinte sicherlich eine sog. Domain Specific Language. Solche 
DSL werden verwendet, um mit einem optimalen Satz an Befehlen genau die 
Kategorie von Aufgaben zu bearbeiten, für die sie definiert wurde. 
Beispielsweise werden DSLs in der Bahntechnik verwendet, um damit 
SPS-Entwicklung für Stellwerke zu betreiben. Man erhofft sich, durch DSL 
die automatisierte Testbarkeit von Programmen verbessern zu können.

SDL (gemäß ITU-T X.100) war vor langer Zeit einmal der neueste Schrei 
für die Modellierung von Telekommunikationssystemen. ISDN und GSM wurden 
vom CCITT/ETSI in SDL beschrieben, und auch etliche Hersteller 
verwendeten SDL für die Entwicklung. Gebräulich waren z.B. Telelogic Tau 
SDL (mittlerweile IBM Rational Tau) und Cinderella, wobei letzteres auf 
dem SDL-Codegenerator der FU Berlin basierte.

Auch ich war "in meinem früheren" Leben sehr stark mit SDL bzw. dessen 
Codegenerierung und Systemintegration befasst. Damals wurde versucht, 
SDL in alle möglichen anderen Gebiete hineinzudrücken, was aber nur 
mäßig gelang, da sowohl die Sprache als auch die Tools ganz erhebliche 
Schwächen aufwiesen.

SDL lebt aber noch weiter, und zwar als der Diagrammtyp Statechart in 
UML.

Andreas S. schrieb:
> gerhard schrieb:
>>>Evtl. würde es helfen, wenn Du den Automaten in einer eigenen Sprach
>>>beschreiben kannst? (Stichwort wäre: DSL).
>> ich denke du meintest SDL oder?
>
> Nein, er meinte sicherlich eine sog. Domain Specific Language.

Genau, die meint er.

gerhard schrieb:
>>SDL lebt aber noch weiter, und zwar als der Diagrammtyp Statechart in
>>UML.
> Ein Statechart mit einem SDL-Digramm zu vergleichen ist doch etwas
> vermessen.

Vielleicht meint Andreas den Diagrammtyp 'Aktivitätsdiagramm' in UML?

Nach meiner Erfahrung ist es am Besten einen eindeutigen Ablauf 
herauszuarbeiten und nicht zu versuchen auf verschiedene Zustände 
optimal zu reagieren. Die Schwierigkeit ist ja das gleichzeitige 
Abarbeiten von Bewegungen und die damit verbundene Erfassung der 
Zustände.

In deinem Beispiel sind es die beiden Werkstückträger, die 
Gleichzeitigkeiten hervorrufen, ansonsten kann man eigentlich einen 
linearen Ablauf implementieren. Für die beiden WTs würde ich also zwei 
Abläufe vorsehen, die parallel abgearbeitet werden aber auf Ereignisse 
des anderen Ablaufs warten. Beide Abläufe sind gleich, aber 
gewissermaßen Phasenverschoben.

Zunächst braucht man eine Grundstellung, die über den Ablauf der 
Grundstellungsfahrt erreicht wird. Da dieser Ablauf nur nach Fehlern 
oder beim Aufstarten angefahren wird, ist keine parrallele Abarbeitung 
notwendig (kein Zeitdruck).

Nach der Grundstellung kommt optional eine Initialisierungsfahrt die 
solange geht, bis die Entladenzustände erreicht sind, das kann auch Teil 
der Grundstellungsfahrt sein.

Grundstellung:
WT1 (leer) auf Band 1, WT2 (leer) auf Band 4. Band 2 in Stellung oben.

In diesem Zustand beginnen beide Abläufe in jeweils ihrem Startpunkt.

-> WT1 beladen (Greifer ab)
-> Warten auf Signal "Lift-down frei für WT1" (Teil der Grundstellung 
und sonst Signal von WT2 gesetzt)
-> WT1 auf Band 2 bewegen, Voraussetzung Band 2 oben und WT2 auf Band 4 
(Timeout)
-> Band 2 nach unten
-> WT1 auf Band 3 bewegen
-> Anwesenheit Werkstück testen, wenn vorhanden: Signal geben "Lift-up 
frei für WT2", sonst Schleife bis Werkstück vorhanden
-> Warten bis Signal "Unteres Deck frei für WT1 vorhanden"
-> WT1 zu Band 4 bewegen -> Schott öffnen -> zu Band 5 bewegen-> Schott 
schließen
-> Auf Starttaster warten -> Schott öffnen
-> WT1 zu Band 4 -> Schott schließen -> WT1 zu Band 3
-> Werkstück auf WT1 testen, Schleife bis leer
-> WT1 (leer) zu Band 4, Signal geben "Lift-down frei für WT2"
   *Hier ist Startpunkt von WT2
-> Warten auf Signal "Lift-up frei für WT1"
-> WT1 zu Band 2 -> Band 2 nach oben -> WT1 zu Band 1
Und hier gehts von vorne los

Dieser Ablauf ist also relativ übersichtlich darstellbar, Abfragen, 
Timeouts (bei allen Bewegungen) etc. kann man eine Ebene tiefer packen, 
um die Abstraktion zu erhalten. Tritt eine unvorhergesehene Situation 
auf, liegt ein Fehler vor und man muss mit einer Grundstellungsfahrt 
zurück auf Null.

Für den Fall, dass nur ein WT eingesetzt wird, gibt es einen gesonderten 
Ablauf. Die Anzahl der WTs kann in der Grundstellungsfahrt ermittelt 
werden.

Zusammengefasst heißt dass, ich würde nicht versuchen für jedes einzelne 
Band die Zustände zu erfassen und daraufhin eine Aktion auslösen, 
sondern vom Prozessfluss ausgehend einen (oder mehrere) Abläufe 
implementieren. In deinem Beispiel gibt es zwei Möglichkeiten, die WTs 
aneinander vorbeizujonglieren. Normalerweise reicht es, sich auf einen 
Fall zu beschränken, wie ich es im obigen Ablauf gemacht habe. Ein 
fehlerfreier Ablauf ist mehr wert wie eine minimale Taktzeitoptimierung.

Wichtig sind natürlich auch Standardbausteine für Timeouts, für 
Warteschleifen auf Signale, zur parallelen Abarbeitung von Abläufen etc.

denk blos nicht dass hier jemand die Arbeit für dich macht. Eigentlich 
ist es nahezu egal mit welcher Sprache man eine Zustandsmaschine 
implementiert. Wichtig ist der sauberer Entwurf. Von Petrinetzen möchte 
ich dir abraten, da diese wegen der gleichzeitigkeit der Marken schnell 
unübersichtlich werden.

Tipp: Der Mensch bzw. normale Programmierer lässt sich von parallelen 
bzw. gleichzeitigen Vorgängen ziemlich verwirren.
Link: http://psychclassics.yorku.ca/Miller/

Hier setzt die Zustandsmaschine an. Merke stets: Für jeden Vorgang der 
gleichzeitig laufen kann, gibt es eine eigenen Zustandsmaschine. Es 
bedarf aber einiger Übung zu erkennen was ein gleichzeitig laufender 
Vorgang ist.
Kommt die Zustandsmaschine an eine Grenze weil etwas parallel gehen muß, 
mach dazu eine Neue auf. Bei Pneumatikzylindern geht das halbwegs, bei 
Behältern die umgefüllt werden ist es deutlich schwieriger. Also viele 
Zustandsdigagramme malen und die Synchronisierung untereinander öfters 
theoretisch durchspielen. Am Schluß ist das codieren nur noch ein 
formaler Vorgang.