S/T-Systeme (Petri-Netze mit anonymen Marken)

Inhaltsverzeichnis

Abbildungsverzeichnis

Übersicht der Definitionen

1 Einleitung

2 Petri-Netze: Einordnung und Überblick
2.1 Definitionen und Varianten
2.2 Einordnung von Petri-Netzen in die Graphentheorie
2.3 Anwendungsgebiete von Petri-Netzen
2.4 Elemente, Begriffe und Zusammenhänge in S/T-Systemen
2.4.1 Graphische Strukturelemente und deren Bedeutung
2.4.2 Grundbegriffe der Schaltdynamik
2.4.3 Nebenläufigkeit und Nichtdeterminismus

3 Wichtige Struktur- und Dynamik-Aspekte von S/T-Systemen
3.1 Struktureigenschaften von Netzen
3.1.1 Schlichtheit
3.1.2 Konflikte
3.1.3 Netzklassen
3.2 Statische Transformationen und ihre Bedeutung
3.3 Zustandsänderungen und ihre Darstellungsmöglichkeiten

4 Fazit

Anhang A: Exemplarische Erreichbarkeitsanalyse und Erreichbarkeitsgraph

Anhang B: Beispiel für algebraische Bestimmung von Zustandsänderungen

Literaturverzeichnis

Abbildungsverzeichnis

Abb. 1: Prof. Dr. C. A. Petri

Abb. 2: Elemente eines Petri-Netzes und ein Beispiel-Netzgraph

Abb. 3: S/T-System zum Netz aus Abb. 2

Abb. 4: Beispiele für logisches UND und ODER

Abb. 5: Knoten- und Kantenmengen zu einem Netz

Abb. 6: Schaltvorgang anhand des IVM-Fallstudien-Seminars WS04/05

Abb. 7: Sperrkante

Abb. 8: Beispiel für lokalen Nichtdeterminismus und Nebenläufigkeit

Abb. 9: Markenweiche zur Vermeidung eines Nichtdeterminismus

Abb. 10: Beispiele für Konflikte im Vor- und Nachbereich

Abb. 11: Beispiele für Synchronisations-Elemente

Abb. 12: Beispiele für Netzklassen

Abb. 13: Konfliktlösende Einbettung

Abb. 14: Faltung eines unendlichen Netzes zu einem endlichen

Abb. 15: Eine Schlinge

Abb. 16: Ein S/T-System samt Inzidenzmatrix und Zustandsvektor

Abb. A1: Ein S/T-System D

Abb. A2: Erreichbarkeitstabelle zu D

Abb. A3: Erreichbarkeitsgraph zu D Übersicht der Definitionen

Definition 1: Petri-Netze (informell)

Definition 2: Petri-Netze (formell)

Definition 3: S/T-System

Definition 4: Bipartiter, gerichteter Graph

Definition 5: Kantengewichtung und Stellenkapazität

Definition 6: Aktiviertheit

Definition 7: Schaltung

Definition 8: Nebenläufigkeit

Definition 9: Nichtdeterminismus

Definition 10: Schlichtheit

Definition 11: Konflikt

Definition 12: Zustandsmaschine

Definition 13: Synchronisationsgraph

Definition 14: Isomorphismus

Definition 15: Einbettung

Definition 16: Verfeinerung

Definition 17: Faltung

Definition 18: Erreichbarkeitsmenge

1 Einleitung

Petri-Netze sind, wie einst von Peter Stahlknecht als ironischer Hinweis auf ihren Verbreitungs- und Bekanntheitsgrad bemerkt, keine Instrumente zum Fische fangen. Vielmehr handelt es sich bei Petri-Netzen um eine der seltenen deutschen Beiträge zur theoretischen Informatik, die weltweit und auch in der US-amerikanischen Fachöffentlichkeit wahrgenommen wurden [vgl. ROS91, S. 1].

Abbildung in dieser Leseprobe nicht enthalten

Petri-Netze gehören zu den wenigen wissen­schaftlichen Schulen, die auch im heutigen Zeitalter nach dem Namen ihres Begründers benannt wurden. Der Erste, der sich systematisch mit dieser Art von Graphen auseinandergesetzt hat, war Carl Adam Petri in seiner 1962 erschienenen Dissertation mit dem Titel „Kommunikation mit Automaten“ [vgl. PRI03, S. V].

Während der praktische Nutzen von Petri-Netzen für Anwender noch immer weithin unbekannt ist [vgl. SCH02, S. 8], haben Petri-Netze in der akademischen Welt bereits eine weite Verbreitung und Beachtung erfahren. 2004 fand bereits zum 25. Mal die „International Conference on Application and Theory of Petri Nets“^[1] statt, eine Fachgruppe der deutschen „Gesellschaft für Informatik“ beschäftigt sich mit Petri-Netzen^[2] und neben vielen anderen hat auch Konrad Zuse ein Buch über Petri-Netze geschrieben^[3].

Da es sich bei dieser Ausarbeitung um die erste in einer Sequenz von sechsen zum Thema Petri-Netze handelt, wird im zweiten Kapitel besonderer Wert darauf gelegt, einen Überblick über die allgemeinen Eigenschaften und Arten von Petri-Netzen und deren Grundbegriffe zu geben. Das dritte Kapitel beschäftigt sich tiefer gehender zum einen mit ausgewählten statischen Struktur­eigenschaften und Transformationen von Petri-Netzen. Zum Anderen wird dort auch eine Einführung in die dynamischen, also im Zeitablauf auftretenden Zustands­veränderungen und deren Darstellungsmöglichkeiten gegeben. Sofern von Bedeutung, finden sich auch Hinweise auf die Bedeutung für den Entwurf und die Anwendung von Petri-Netzen. Um einen größeren Zusammenhang herzustellen, wird an entsprechenden Stellen dieser Arbeit kurz auf die weiteren Ausarbeitungen zum Thema Petri-Netze verwiesen.

2 Petri-Netze: Einordnung und Überblick

2.1 Definitionen und Varianten

Petri-Netze stellen ein geeignetes Mittel dar, um den zeitlichen Ablauf eines Systems und dessen Zustandsänderungen graphisch zu repräsentieren und erfüllen daher die gleiche Funktion wie Zustandsgraphen [vgl. SCH02, S. 11].

Definition 1: Petri-Netze (informell):

Petri-Netze lassen sich informell zweckmäßig definieren als ein Modellierungs­werkzeug, mit dessen Hilfe man reale oder logische Systeme beschreiben kann, bei denen bestimmte Objekte durch Ereignisse verbraucht und erzeugt werden [vgl. BB96, S. 15-17].

Von Petri-Netzen existieren drei verschiedene Varianten [vgl. BE03, S. 116-119]:

- Bedingungs/Ereignis-Netze (B/E-Netze) zeichnen sich dadurch aus, dass jedes modellierte Ereignis nur unter 1 bis n Bedingungen eintritt, die jeweils entweder erfüllt sind oder nicht [vgl. BB96, S. 111-115].
- Stellen /Transitions-Netze (S/T-Netze) besitzen die gleichen Elemente wie B/E-Netze. Bedingungen für Ereignisse haben nun nicht nur den Status „erfüllt“ oder „nicht erfüllt“, sondern werden durch eine quantifizierbare Menge von nicht unterscheidbaren Objekten, genannt „Marken“, charakterisiert. Graphisch werden Marken oft als kleine, schwarze Punkte dargestellt. „Erfüllt“ ist eine Bedingung erst dann, wenn ein bestimmter Grenzwert von Marken erreicht ist.
- Prädikat/Transitions-Netze (Pr/T-Netze) unterscheiden sich von S/T-Netzen insofern, als dass die Marken, die gemeinsam eine Bedingung für ein Ereignis darstellen, nun auch individuell verschieden, also unterscheidbar sein können^[4].

Abbildung in dieser Leseprobe nicht enthalten

Es ist möglich, die einzelnen Varianten in einander zu überführen. So kann beispiels­weise ein S/T-Netz in ein B/E-Netz überführt werden [vgl. BB96, S. 114-115]. Diese Arbeit beschäftigt sich ausschließlich mit S/T-Netzen bzw. S/T-Systemen. S/T-Systeme bestehen zum einen aus einem Petri-Netz.

Definition 2: Petri-Netz (formell):

Ein Petri-Netz oder Netzgraph ist formell durch das Tripel (S, T, F) definiert [vgl. BB96, S. 50; BE03, S. 115].

Abbildung in dieser Leseprobe nicht enthalten

S steht hierbei für die Menge aller objekt­aufnehmenden Behälter, genannt „Stellen“ oder „Plätze“, T für die Menge aller Ereignisse, genannt „Transitionen“ und F für die Menge aller existierenden Verbindungen zwischen Stellen und Transitionen, genannt „Kanten“ [vgl. BB96, S. 50; SCH02, S. 15-16] (Abb. 2, siehe auch Abb. 5).

Definition 3: S/T-System:

Ein S/T-System wird formell durch das 6-Tupel (S, T, F, K, W, M0) beschrieben [vgl. BB96, S. 79-80].

Gemeinsam mit einer Menge von Kapazitäten der objektaufnehmenden Stellen K, einer Menge von Kantengewichten W und einer Anfangs-Ausstattung mit Objekten, genannt „Markierung“ M0 bildet ein Petri-Netz ein S/T-System (Abb. 3). Die Kantengewichte geben dabei an, wie viele Objekte von einer Stelle zu einer

Abbildung in dieser Leseprobe nicht enthalten

Transition oder von einer solchen wieder zu einer Stelle wandern, wenn dieses eintritt.

Prinzipiell handelt es sich den Stellen-, Transitions- und Kantenmengen S, T und F um die statischen Elemente der Petri-Netz-Theorie. Marken und Markierungen hingegen drücken die Dynamik, also den zeitlichen Ablauf und die Zustände der abzubildenden Systeme und Prozesse aus [vgl. ROS91, S. 7, 15]. Einzelne Elemente von Definition 3 und deren Zusammenhänge werden in den Kapiteln 2.4 und 3 näher betrachtet. Im Folgenden ist, analog zur Literatur, der Begriff „Petri-Netz“ entweder immer mit einem S/T-System gleichzusetzen oder es ist das einem S/T-System zugrundeliegende Netz gemeint [vgl. BB96, S. 49].

2.2 Einordnung von Petri-Netzen in die Graphentheorie

Petri-Netze gehören in das Gebiet der Graphen-Theorie [vgl. SCH02, S. 113]. Ein Graph ist eine Menge von Knoten, die mit einander durch Kanten verbunden sind [vgl. SCH02, S. 12]. Bei Petri-Netzen bilden die Menge der Stellen und der Transitionen zusammen die Menge der Knoten, von denen wiederum je zwei durch eine Kante verbunden sein können. Ein Petri-Netz ist daher ein Graph [vgl. SCH02, S. 15]. Petri-Netze werden, wie Graphen auch, aus Übersichtlichkeits­gründen für gewöhnlich graphisch dargestellt. Andere Darstellungsformen sind jedoch denkbar, so können alle Mengen einfach aufgezählt werden [vgl. BB96, S. 80] oder die Kanten und deren Gewichtungen in einer Matrix aufgelistet werden^[5] [vgl. BB96, S. 90].

Definition 4: Bipartiter, gerichteter Graph:

Ein bipartiter, gerichteter Graph ist ein Graph, dessen Kanten gerichtet sind und dessen Knoten so in zwei disjunkte Teilmengen V1 und V2 zerlegt werden kann, dass alle Kanten einen Knoten aus V1 und einen aus V2 verbindet [vgl. BB96, S. 42].

Ein Petri-Netz ist ein gerichteter Graph (engl. Abkürzung „Digraph“ [vgl. SCH02, S. 13]). Dieses bedeutet, dass alle enthaltenden Kanten gerichtet sind und die Beziehung zwischen zwei Knoten nur in einer Richtung gültig ist. Graphisch wird dieses mit einem Pfeil an einem Kantenende dargestellt. Gerichtete Graphen sind daher im Wesentlichen Relationen, da sie eine Beziehung zwischen Elementen mehrerer Mengen sichtbar machen [BB96, S. 42].

Petri-Netze sind darüber hinaus bipartit, d.h. ihre Knotenmenge wird immer auf eine Weise in zwei disjunkte Teilmengen, S für Stellen und T für Transitionen zerlegt, dass eine Kante je einen Knoten aus S mit einem aus T verbindet [vgl. BB96, S. 42; SCH02, S. 12-13]. Eine Kante kann daher niemals zwei Stellen oder zwei Transitionen verbinden, sondern nur genau eine Stelle und eine Transition.

Im Unterschied zu allgemeinen Zustandsgraphen besitzen Petri-Netze Markierungen, die angeben, in welchem Zustand sich das Gesamtsystem momentan befindet. Die Markierungen können sich im Zeitverlauf verändern und machen Petri-Netze so zu einem aussagekräftigeren Instrument als Zustands­graphen [vgl. SCH02, S. 11]. Somit stellen Petri-Netze teilweise eine Alternative zu Zustandsgraphen dar. Zu Petri-Netzen lassen sich spezielle Zustandsgraphen bilden, deren Knoten mögliche Markierungen des Petri-Netzes, also Zustände, im Zeitverlauf repräsentieren. Da in Petri-Netzen die Übergänge zwischen Zuständen mit Transitionen erfolgen, wird jede Transition zu einer Kante im dazugehörigen Zustandsgraph. Zustandsgraphen von Petri-Netzen werden Erreichbarkeitsgraphen genannt und können im Allgemeinen nicht so kompakt dargestellt werden wie das dazugehörige Petri-Netz^[6] [vgl. SCH02, S. 70-75; BB96, S. 88]. Es besteht eine Verwandtschaft zwischen Petri-Netzen und den in der Praxis häufig eingesetzten CPM (critical path method)-Netzen [vgl. SCH02, S. 11]. Beide können einen Weg von einem Ausgangs- zu einem Zielzustand darstellen. Lässt man eine zeitliche Verzögerung der Transitionen in Petri-Netzen zu^[7] [vgl. SCH02, S. 19], so ist es möglich, ein CPM-Netz in ein Petri-Netz zu überführen.

2.3 Anwendungsgebiete von Petri-Netzen

Petri-Netze sind ein Mittel, um reale Systeme in ein formales Modell zu überführen oder um aus einem Modell heraus Erkenntnisse über das untersuchte System zu gewinnen. Hintergrund einer Modellierung kann daher sowohl ein Dokumentationszweck als auch ein Analysezweck sein [vgl. BB96, S. 12]. Darüber hinaus bringen Modelle einen Nutzen hinsichtlich Entwurf und Test des untersuchten Systems und abstrahieren zu diesem Zweck immer in angemessener Weise von der Realität [vgl. BB96, S. 22-25].

Abbildung in dieser Leseprobe nicht enthalten

Das modellierte System kann dabei bei Petri-Netzen nicht nur praktisch, sondern auch theoretisch orientiert sein. Jedoch können nur diskrete Systeme mit Petri-Netzen beschrieben werden. Diskret bedeutet, dass die Objekte und Ereignisse in einem System wohlunterscheidbar sind [vgl. BB96, S. 15]. Dies ist z.B. bei einer Fließbandfertigung von Autos aus Einzelteilen einfach möglich, aber schwer z.B. beim Abernten eines Feldes oder der konstanten Verarbeitung von Schüttgut. Ein praxis­orientiertes Einsatzgebiet von Petri-Netzen ist z.B. der Transport, bei dem reale Güter oder Nachrichten transportiert werden [vgl. SCH02, S. 31, 62-63]. Daher lassen sich auch ganze Kommunikations­protokolle, d.h. Regeln für den Nachrichtentransport, mit Petri-Netzen darstellen^[8]. Weitere praktische Einsatz­möglichkeiten umfassen Geschäfts­vorgänge, Organisations­strukturen und die Bedienung von Automaten [vgl. BB96, S. 5, 12, 15].

Auf der anderen Seite lassen sich Petri-Netze auch auf dem Gebiet der Logik einsetzen [vgl. BB96, S. 12]. Mit Petri-Netzen lassen sich einfache logische Ausdrücke darstellen (Abb. 4). So entsprechen die Bedingungen, die zum Eintreten eines Ereignisses alle erfüllt sein müssen, einem logischen „UND“. Zwei oder mehr Ereignisse, die dafür sorgen können, dass eine nachfolgende Bedingung erfüllt wird, entsprechen hingegen dem logischen „ODER“ [vgl. SCH02, S. 19]. Neben logischen Ausdrücken ist in Petri-Netzen zudem ein eingeschränktes, arithmetisches Rechnen möglich. Ganzzahlige Werte lassen sich addieren, was die Grundlage für höhere Rechenarten darstellt. Ebenfalls möglich ist es, einfache Zählwerke zu modellieren [vgl. SCH02, S. 24-25], worauf an dieser Stelle aber nicht näher eingegangen wird.

Die breite Anwendbarkeit von Petri-Netzen ergibt sich zum erheblichen Teil auch aus den vielfältigen Interpretationsmöglichkeiten für die Marken. Diese in S/T-Systemen nicht unterscheidbaren Objekt-Repräsentanten können z.B. konkrete Gegenstände wie Bauteile darstellen. Auf diese Weise lassen sich ganze industrielle Fertigungsprozesse, bei denen aus Einzelteilen ein Fertigprodukt hergestellt wird, mit Petri-Netzen modellieren [vgl. BB96, S. 78; SCH02, S. 105]. Andererseits können Marken für abstrakte Objekte stehen und so beispielsweise darstellen, dass eine Ressource momentan nicht genutzt wird [vgl. SCH02, S. 47, 87]. Solche Ressourcen können z.B. die Gabeln des in der Informatik weithin bekannten „Problems der fünf speisenden Philosophen“ sein [vgl. BB96, S. 64; SCH02, S. 90; DES98, S. 90]. Mit Petri-Netzen ist es zudem leicht möglich, das Hinzufügen oder das Wegnehmen eines Objektes aus einem Bestand zu modellieren [vgl. SCH02, S. 50]. Auf diesen Grundelementen aufbauend lassen sich z.B. Lagersysteme auf verschiedene Arten beschreiben [vgl. SCH02, S. 96-99; ROS91, S. 10-11]. Als letztes Beispiel sei die Möglichkeit zur Modellierung von Ampelanlagen genannt. Diese besitzen zeitlich wechselnde Zustände und klar unterscheidbare Phasen und sind daher schon aufgrund ihrer Natur gut mit Petri-Netzen modellierbar [vgl. SCH02, S. 92-94].

Insgesamt lässt sich sagen, dass es sich bei Petri-Netzen um eine der leistungsfähigsten Methoden zur bildlichen Darstellung dynamischer Vorgänge handelt. Die Betrachtungsebene ist nicht zu abstrakt und es ist möglich, ein eingebettetes, d.h. ein in einem größeren Zusammenhang existierendes System unabhängig von der zu Grunde liegenden Technologie zu untersuchen [vgl. SCH02, S. 8]. Es können auch komplexe Szenarien modelliert werden und für die Anwendungsgebiete gibt es kaum erkennbare Begrenzungen [vgl. SCH02, S. 87].

[...]

---

^[1] http://www.cs.unibo.it/atpn2004/ (Stand: 05.01.2005)

^[2] http://www.informatik.uni-hamburg.de/TGI/GI-Fachgruppe0.0.1/index.html (Stand: 05.01.2005)

^[3] Zuse, K.: „Petri-Netze aus der Sicht des Ingenieurs“, Vieweg-Verlag, 1982

^[4] siehe Ausarbeitung „Petri-Netze mit individuellen Marken“

^[5] siehe Kapitel 3.3 und Anhang B

^[6] siehe Anhang A

^[7] siehe Kapitel 2.4.2

^[8] siehe Ausarbeitung „Kommunikationsprotokolle und Petri-Netze“