OO-Modellierung und Implementierung …NPC – Vorlesung Prof. Janschek: Steuerung diskreter Systeme...

OO-Modellierung und Implementierung eines endlichen Zustandsautomaten

VL MRT-2, SS 2013 Professur für Prozessleittechnik

Übersicht

• Anwendungsbeispiel: Endlicher Zustandsautomat

• C++ Konzepte:

– Vertiefung const

– Freundkonzept

– Spezialisierung von Klassen

– virtuelle Methoden und abstrakte Klassen

• Entwurfsmuster:

– Strategiemuster

18.04.2013 Folie 2 MRT2 (c) 2013, UR

Anwendung: Endlicher Zustandsautomat (finite state machine)

• Modell zur mathematischen Beschreibung von Verhalten, beispielsweise für die Steuerung von Anlagen, Robotern, NPC

– Vorlesung Prof. Janschek: Steuerung diskreter Systeme

– Hauptseminar AMR: Einparkhilfe VIDEO

• Komponenten eines Automaten (generalisiert, UML)

– Zustand: Endlich viele, zu jedem Zeitpunkt ist der Automat in genau einem Zustand

– Startzustand: Zustand zum Zeitpunkt t=0

– Übergang(Transition): Übergang zwischen zwei Zuständen

– Bedingung(Wächter): Voraussetzung für das Ausführen eines Übergangs (Ereignisse, Eingaben, ...)

– Verhalten: wird beim Betreten, Verharren und Verlassen eines Zustands oder bei einem Übergang ausgeführt

18.04.2013 MRT2 (c) 2013, UR Folie 3

Verhaltensspezifikationen

• am Zustand

– Eingangsaktion (entry behaviour)

• Wird bei Eintreten in Zustand ausgeführt

– Ausgangsaktion (exit behaviour):

• wird bei Verlassen des Zustands ausgeführt

– Zustandsaktion (doActivity) :

• wird ausgeführt während sich Automat in Zustand befindet

• am Übergang:

– Übergangsaktion (effect)

• Wird ausgeführt, wenn Zustandsübergang durchlaufen wird

• Je nach Automatenart werden nur Teilmengen benötigt, beispielsweise nur Effekte oder Zustandsaktionen

18.04.2013 MRT2 (c) 2013, UR Folie 4

Anwendungsbeispiel: Baustellenampeln mit Übergangsaktionen

18.04.2013 MRT2 (c) 2013, UR Folie 5

[IS-links] [t>30s] / l-g

[IS-rechts] [t>30s] / r-g

[t>60s &&

IS-rechts] / l-r

[t>60s &&

IS-links] / r-r

UML Aktivitätsdiagramm

18.04.2013 MRT2 (c) 2013, UR Folie 6

Objektorientierte Analyse

• Erste Idee für Klassenstruktur

– Automat

• aktueller Zustand (= Startzustand bei t=0)

• Methode zum Ausführen des Automaten

– Zustand

• Liste aller Transitionen aus diesem Zustand

• Methoden für enter, do, exit

– Transition

• Methoden für Wächterfunktion (guard) und Übergangsverhalten (effect)

• Zielzustand der Transition

18.04.2013 MRT2 (c) 2013, UR Folie 7

Diskussion des Entwurfs

• Zeitoptimal

– bei jedem Schritt wird nur über die Menge der Ausgangstransitionen des aktuellen Zustands iteriert

• Aber: Zirkuläre Abhängigkeit Zustand / Transition

– State.h: #include "Transition.h"

class State { ... }

– Transition.h #include "State.h"

class State; // forward declaration

class Transition { ... }

• Schlechtes Design! – Bei Änderungen in einer Klasse muss auch die andere übersetzt werden,

– Schwierigkeiten bei Freigabe von dynamisch angelegtem Speicher,

– ...

18.04.2013 MRT2 (c) 2013, UR Folie 8

Neuer Ansatz Transitionstabelle

18.04.2013 MRT2 (c) 2013, UR Folie 9

• Transition kennt start und ziel

• Zustand braucht Transition nicht zu kennen

• Direkt aus Graph ablesbar

Start Wächter Effekt Ziel

AlleRot IS-Links LinksLeeren

LinksLeeren z>30 LinksGrün

LinksGrün IS-Rechts && z>60 RechtsLeeren

AlleRot IS-Rechts RechtsLeeren

RechtsLeeren z>30 RechtsGrün

RechtsGrün IS-Links && z>60 LinksLeeren

Deklaration State

#include <string> // Zeichenketten-template aus STL

using namespace std;

class State {

private:

const string id; // Identifier

public:

State(const string& id) : id(id) { }; // Konstruktor

void enter() const; // Verhaltensspezifikation Eintritt

void stay() const; // Verhaltensspezifikation Aufenthalt

void exit() const; // Verhaltensspezifikation Ausgang

const string& getID(); // Zugriff auf Identifier

};

18.04.2013 MRT2 (c) 2013, UR Folie 10

Nicht veränderliches

Objekt

Soll beim Anlegen

einer Instanz aber

gesetzt werden?

Lösung: Element-

initialisierungsliste

C++: Elementinitialisierungsliste

• Liste von Konstruktoren für die Elemente zwischen Kopf und Körper der Konstruktormethode

State::State(const string& id) : id(id) { };

• Anweisungen der Elementinitialisierungsliste werden ausgeführt bevor das Objekt „lebt“

– Klassentypen ohne Standardkonstruktoren und const Elemente müssen in der Elementinitialisierungsliste definiert werden!

• Die Reihenfolge der Elementinitialisierung wird durch die Reihenfolge der Definition der Elemente bestimmt.

– Moderne Compiler warnen, wenn Sie eine Diskrepanz zwischen Elementinitialisierungsliste und Definitionsreihenfolge finden

• Kein Überdecken bei Namensgleichheit von Argument und Element

18.04.2013 MRT2 (c) 2013, UR Folie 11

C++: const (Teil 1)

• Anweisung ab den Compiler Konstrukte zurückzuweisen, die potentiell zu einer (unbeabsichtigten) Änderung führen können.

• Fall 1: Konstante Objektinstanzen

– das Objekt und seine Elemente werden nach Initialisierung nicht mehr verändert!

– const string id; // Identifier

• Fall 2: Nichtmodifizierende Methoden

– die Methode soll die Objektinstanz nicht ändern

– void exit() const;

• Fall 3: Referenz auf ein konstantes Objekt

– Das Objekt soll auch an anderer Stelle nicht geändert werden

– const string& getID();

18.04.2013 MRT2 (c) 2013, UR Folie 12

Nichtelementmethoden zu State Ausgabe auf Strom: operator<<

[...]

class State {

friend ostream& operator<<(ostream& lhs, State& rhs);

friend ostream& operator<<(ostream& lhs, const State& rhs);

private:

const string id; // Identifier

State(const string& id) : id(id) { }

[...]

};

inline ostream& operator<<(ostream& lhs, State& rhs) {

return lhs << rhs.id; }

inline ostream& operator<<(ostream& lhs, const State& rhs) {

return lhs << rhs.id; }

18.04.2013 MRT2 (c) 2013, UR Folie 13

Mit friend deklarierte

Methoden dürfen auf

private Daten

zugreifen

Keine Doppelung

der Methode!

Unterschiedliche

Signaturen

C++: friend

• Ein-/Ausgabeoperatoren und andere überladene Operatoren sollen häufig auf geschützte (private, protected) Attribute zugreifen, dürfen aber nicht Elementfunktionen sein.

• Der Freundmechanismus erlaubt festgelegten Funktionen oder Klassen Zugang zu den nichtöffentlichen Elementen

• Jede überladene Nichtelementfunktion, die Zugang zu den Elementen haben soll, muss als Freund deklariert sein. Die Signatur muss exakt übereinstimmen!

friend ostream& operator<<(ostream& lhs, State& rhs);

friend ostream& operator<<(ostream& lhs, const State&

rhs);

18.04.2013 MRT2 (c) 2013, UR Folie 14

Deklaration Transition

#include <iostream>

using namespace std;

#include "State.h"

class Transition {

public:

const State& start; // Ausgangszustand

const State& target; // Endzustand

Transition(const State& start, const State& target) :

start(start), target(target) { }

bool guard() const; // Wächterfunktion

void effect() const; // Übergangsverhalten

};

18.04.2013 MRT2 (c) 2013, UR Folie 15

Definition der Struktur des Automaten (Mockup, ohne spezifisches Verhalten)

// states

State ar("ar"), ll("ll"), lg("lg"), rl("rl"),

rg("rg");

// transitions

Transition t[] = {

Transition(ar, ll),

Transition(ll, lg),

Transition(lg, rl),

Transition(ar, rl),

Transition(rl, rg),

Transition(rg, ll)

};

18.04.2013 MRT2 (c) 2013, UR Folie 16

Ausführungslogik des Automaten in jedem Schritt – Beschreibung in Pseudo Code

// Prüfe ausgehende Transitionen

ÜBER ALLE ausgehenden Transitionen des aktuellen Zustands

WENN Transition durch Wächter freigegeben ist DANN

- Ausgangsverhalten des aktuellen Zustands

- Übergangsverhalten der Transition

- Eingangsverhalten des Zielzustand der Transition

- aktueller Zustand = Zielzustand der Transition

- RÜCKSPRUNG

ENDE WENN

ENDE ÜBER ALLE

// Wenn keine Transition geschaltet hat

- Beharrungsverhalten des aktuellen Zustands

18.04.2013 MRT2 (c) 2013, UR Folie 17

Deklaration Automaton

#include "State.h"

#include "Transition.h„

class Automaton {

private:

const State* pCurrentState;

const Transition* const pTT;

const int TTlength; int currentStateTicks;

public:

Automaton(State& startState, Transition* const pTT, const int

TTlength) : pCurrentState(&startState), pTT(pTT),

TTlength(TTlength), currentStateTicks(0) {

pCurrentState->enter(); }

void run();

int getCurrentStateTicks();

};

18.04.2013 MRT2 (c) 2013, UR Folie 18

const x*:

Veränderliche

Adresse eines

unveränderlichen

Objekts

const x* const:

Unveränderliche

Adresse eines

unveränderlichen

Objekts

->: Elementzugriffs-

operator für einen

Zeiger auf ein Objekt

analog zur Definition

in C

() ist der

Methodenaufruf-

operator mit

Argumentliste

C++: const (Teil 2)

• Konstante Zeiger auf Objekte - was ist konstant?

• Fall 1: Objektinstanz

– das Objekt dessen Adresse im Zeiger verwaltet wird darf nicht geändert werden

– const links von * bezieht sich auf Objekt (wie const double)

const State* pCurrentState;

State const * pCurrentState;

• Fall 2: Adresse

– Adresse soll nicht geändert werden

– const rechts von * bezieht sich auf Adresse

State* const pCurrentState;

• Fall 3: Adresse und Objektinstanz(en) unveränderlich

const Transition* const pTT;

18.04.2013 MRT2 (c) 2013, UR Folie 19

Die nächsten Schritte zum vollständig spezifizierten Automaten

• Spezialisierung

– Ableitung von spezialisierten Klassen aus den Basisklassen

– diese implementieren die konkreten Verhaltensspezifikationen von State

• enter(), hold(), exit()

– sowie Verhaltensspezifikationen und Wächter der Transition

• effect(), guard()

• C++: frühes und spätes Binden

– virtuelle Methoden (spätes Binden)

– abstrakte Klassen (können nicht versehentlich instanziiert werden)

18.04.2013 MRT2 (c) 2013, UR Folie 20

StateAlleRot ist_ein State (mit einem spezifizierten Eingangsverhalten)

// Spezialisierter Zustand

class StateAlleRot : public State {

public:

StateAlleRot(const string& id) : State(id) { }

void enter() const { cout << "state " << id

<< ": links=rot, rechts=rot" << endl; }

};

StateAlleRot("ar"); ...

• Leider funktioniert das in unserem Kontext so nicht zuverlässig!

18.04.2013 MRT2 (c) 2013, UR Folie 21

nach : wird eine

Liste von

Basisklassen

erwartet, die wir

spezialisieren

public: Zugriff auf

die Methoden der

Basisklasse wird

nicht modifiziert

Konstrukturen der

Basisklasse mit

Argumenten

müssen in der

Element-

initialisierungsliste

aufgerufen werden!!!

Die Methode enter() der

Basisklasse wird überschrieben

Frühes und spätes Binden

• Frühes (statisches) Binden

– Der Compiler bestimmt bereits zur Übersetzungszeit die konkret aufzurufende Methode

– Effizienter Code, Optimierung, ...

• Spätes (dynamisches) Binden

– Der Compiler erzeugt Code, der zur Laufzeit den Typ des Objekts und die konkret aufzurufende Methode bestimmt

• run-Methode des Automaten: pCurrentState->enter()

– State::enter() oder StateAlleRot::enter() ?

• Regeln

– Frühe Bindung: Typ des Zeigers State::enter()

– Späte Bindung: Typ des Objects StateAlleRot::enter()

18.04.2013 MRT2 (c) 2013, UR Folie 22

Spätes Binden „anordnen“: virtual

class State {

private:

const string id; // Identifier

public:

State(const string& id) : id(id) { }

virtual void enter() const;

virtual void exit() const;

virtual void stay() const;

inline const string& getID() const { return id; }

virtual ~State() { }

};

18.04.2013 MRT2 (c) 2013, UR Folie 23

virtuelle Methoden

werden spät

gebunden

Es ist fast immer

richtig auch einen

virtuellen Destruktor

zu definieren

Implementierung

class StateAlleRot : public State {

public:

StateAlleRot(const string& id) : State(id) { }

void enter() const { cout << "execute spezialisiertes

enter von " << getID() << ":links=rot, rechts=rot" <<

endl;}

};

class StateLinksLeeren : public State {

public:

StateLinksLeeren(const string& id) : State(id) { }

void enter() const { cout << "execute spezialisiertes

enter von " << getID() << ":rechts=rot" << endl;; }

};

18.04.2013 MRT2 (c) 2013, UR Folie 24

Nicht-Leere

Konstruktoren

müssen neu

angelegt werden

Alternative: Strategie-Muster

• Die Logik der Ausführung einer Methode einer Klasse wird an die Methode einer Strategieklasse ausgelagert

• Hier: Nutzung von Funktionszeigern

– Das Ausführen einer Methode werden bestimmte extern definierte Funktionen ausgeführt

• Vorteile:

– Kein Überladen von virtuellen Methoden notwendig

– Statisches Binden möglich

– Objekte von unterschiedlichen Typ können gleiche Strategien haben

• Nachteil:

– Externe Methoden haben keinen Zugriff auf die Klasse,

– Aufweichen der Kapselung über public bzw. freund konzepte nicht sinnvoll

18.04.2013 MRT2 (c) 2013, UR Folie 25

Strategie als Funktionszeiger

• Definition in State.h class State; // forward declaration

// Definition des Funktionszeigers Behavior

typedef void (*Behavior)(const State&, const string&);

// Deklaration der Defaultfunktion (nix tun)

void defaultBehavior(const State&, const string&);

• Nutzung in Klasse State private:

Behavior enterFunc;

public:

explicit State(const string& id,

Behavior enterFunc=defaultBehavior,

Behavior stayFunc= defaultBehavior,

Behavior exitFunc=defaultBehavior);

inline void enter() const { enterFunc(*this, "enter"); }

18.04.2013 MRT2 (c) 2013, UR Folie 26

Zum Komfort: Typ

für Funktionszeiger

rückgabe (*name)

(argumentliste)

Funktionsprototyp,

Implementierung an

anderer Stelle

„kleiner“ zirkulärer

Bezug, deshalb

forward declaration

notwendig

Defaultargumente –

wenn nicht

angegeben „nichts

tun“

Restrukturierung Automat

• Das Strategiemuster auf Transitionen angewandt

– doppelte Definition der defaultBehaviours notwendig neues

Design!

• Frage: Welche Elemente und Methoden haben State und Transition gemeinsam?

– string id, const string& getID()

• Lösungsansatz:

– Verlagern dieser Methoden in Basisklasse AutomatonElement, State und Transition werden abgeleitete Klassen

– Behaviours bekommen als Argument Referenz auf Basisklasse, statisches Binding sinnvoll, da nur Methoden der Basisklasse verwendet werden sollen

– AutomatonElement soll eine abstrakte Klasse werden, die nicht instanziiert werden kann

18.04.2013 MRT2 (c) 2013, UR Folie 27

Neues Klassendiagramm Automaton

18.04.2013 MRT2 (c) 2013, UR Folie 28

Automaton

Zustand Transition

Automaton-

Element

Strategie

1

1..*

1

1

2 1

AutomatonElement

class AutomatonElement; // forward

typedef void (*Behavior)(const AutomatonElement&, const string&);

void defaultBehavior(const AutomatonElement&, const string&);

typedef bool (*Guard)(const AutomatonElement&, const string&);

bool defaultGuard(const AutomatonElement&, const string&);

class AutomatonElement {

protected:

const string id; // identifier

public:

AutomatonElement(const string&);

virtual ~AutomatonElement() { };

inline const string& getID() const { return id; }

virtual const string& getType() const = 0;

};

18.04.2013 MRT2 (c) 2013, UR Folie 29

„kleiner“ zirkulärer

Bezug, deshalb

forward declaration

notwendig

prototyp = 0: pure

virtual Method

AutomatonElement

ist eine abstrakte

Klasse, die nicht

instanziiert werden

kann.

Eclipse: Library anlegen

1. Neues Projekt vom Typ Library anlegen

File / New / C++ Project

Project Name: Automaton

Project Type: Static Library / Empty Project

Toolchain: Linux GCC

2. Dateien aus Alt-Projekt kopieren und in neues Projekt einfügen

3. Build

Ergebnis: libAutomaton.a im Projektunterverzeichnis Debug und/oder Release

18.04.2013 MRT2 (c) 2013, UR Folie 30

Eclipse: Library verwenden

1. Referenz anlegen

Project / Properties Project References dort Automaton auswählen

2. Pfad zu Include-Datei für Compiler

Project / Properties C/C++ Build / Settings

Tool Settings: GCC C++ Compiler / Includes

Include paths (-l): Add, Workspace, Automaton auswählen

3. Library für Linker

Project / Properties C/C++ Build / Settings

Tool Settings: GCC C++ Linker / Libraries

Libraries (-l): Add, Automaton eingeben

Library search path (-L): Add, Workspace, Automaton/Debug auswählen

18.04.2013 MRT2 (c) 2013, UR Folie 31

Implementierung Ampelsteuerung

typedef AE AutomatonElement; // zu wenig Platz auf der Folie

const int ROT=0, GRUEN=1; // Signale für die Ampelsteuerung

int links = ROT, rechts= ROT; // Signal für Ampel != Zustand Automat!

ostream* aout = &cout; // Ausgabestrom für Visualisierung

void p(const AE& ae) { *aout << links << " " << rechts << " " <<

ae.getID() << endl; }

void behavior_LRRR(const AE& ae, const string& x) {

links=ROT;rechts=ROT;p(ae);}

// [...]

void behavior_RR(const AE& ae, const string& x) {

rechts=GRUEN;p(ae));}

// [...]

int main {

State ar("4", behavior_LRRR), ll("5", behaviorRR), ...;

Transition t[]={ Transition(ar, ll, guardLSL), ... };

18.04.2013 MRT2 (c) 2013, UR Folie 32

Ein Zeiger auf

Ausgabestrom kann

nochmal verändert

werden

Methodenname

ohne Aufrufoperator

(): Adresse der

Funktion

Visualisierung Ampelsteuerung

1. Trennen Debugausgabe, Zustandsausgabe

clog, cerr: Nutzung der Standardströme für Ausgabe von

Debug und Fehlermeldungen in der Library

ostream* aout = &cout; // Zeiger auf den Ausgabestrom für die

Daten, initialisiert mit cout

2. Visualisierung der Ausgabe auf stdout (cout): Programm aus shell starten, Ausgabe in Datei umlenken und gnuplot mrt$ cd MRT2/TrafficLight/Debug

mrt$ ./TrafficLight > q.q

mrt$ gnuplot

gnuplot> set border 0

gnuplot> set key auto col

gnuplot> plot 'q.q' using 1 with steps, 'q.q' u (\$2+2) w st,

'q.q' u 3 w st

18.04.2013 MRT2 (c) 2013, UR Folie 33

Ergebnis

18.04.2013 MRT2 (c) 2013, UR Folie 34

Linke Ampel

Rechte Ampel

Zustandsänderung

des Automaten

Automatisierung: Ausgabe in Datei, Anzeige mit gnuplot

#include <fstream> // für ofstream

#include <stdlib.h> // für system

ofstream fout("q.q");

aout = &fout;

for (int i = 0; i < 20; i++) a.run();

fout.close();

system("gnuplot -p -e \"" //

"set bor 0;"

"set key auto col;"

"set ytics ('grün' 0, 'rot' 1, 'grün' 2, 'rot' 3, 'ar' 4, 'll' 5,

'lg' 6, 'rl' 7, 'rg' 8);"

"plot 'q.q' u 1 w steps, 'q.q' u (\\$2+2) w steps, 'q.q' u 3 w

steps\"");

18.04.2013 MRT2 (c) 2013, UR Folie 35

Ausgabestrom auf

Datei mit Namen q.q

öffnen

ofstream ist_ein

ostream, genauso

wie cout: Gleiche

Schnittstellen für

Ausgabe auf

Konsole und Datei!

Vor Nutzung

schliessen

Automatisierung: Ausgabe in Datei, Anzeige mit gnuplot

#include <fstream> // für ofstream

#include <stdlib.h> // für system

ofstream fout("q.q");

aout = &fout;

for (int i = 0; i < 20; i++) a.run();

fout.close();

system("gnuplot -p -e \"" //

"set border 0;"

"set key autotitle column;"

"set ytics ('grün' 0, 'rot' 1, 'grün' 2, 'rot' 3, 'ar' 4, 'll' 5,

'lg' 6, 'rl' 7, 'rg' 8);"

"plot 'q.q' u 1 w steps, 'q.q' u (\\$2+2) w steps, 'q.q' u 3 w

steps\"");

18.04.2013 MRT2 (c) 2013, UR Folie 36

Kein Rahmen

Beschriftung der

Kurven aus erster

Zeile der Datendatei

Umbenennung der

Ticks der y-Achse

Formel: Wert in 2.ter

Spalte ($2) plus 2

Taschenrechner: Vorzeichenbehaftete Ganzzahlen, kein Vorrang der Operanden

• Start in 0

• 0,1,2: Linker Operand – 0<->1 Negative Vorzeichen

wechseln Vorzeichen

– 2: Zahlenfolge aggregieren

• 2->3: Operator – Operator merken, Wechsel zum

Einlesen des rechten Operanden

• 3,4,5: Rechter Operand – wie Linker Operand

• 3->5: Operator – den zuletzt gemerkten Operator ausführen, Ergebnis in linkem Operand

speichern, rechten Operand auf 0 setzen, neuen Operator merken

• 5->0: Operator – wie 3->5, nur diesmal alles zurücksetzen

18.04.2013 MRT2 (c) 2013, UR Folie 37

Test: --0002*30+-+1234= -1174 ?

18.04.2013 MRT2 (c) 2013, UR Folie 38