Petri Netz

Petri Netz

Ein Petri-Netz ist ein mathematisches Modell von nebenläufigen Systemen. Es ist eine formale Methode der Modellierung von Systemen bzw. Transformationsprozessen. Die ursprüngliche Form der Petri-Netze nennt man auch Bedingungs- oder Ereignisnetz. Petri-Netze wurden durch Carl Adam Petri in den 1960er Jahren definiert. Sie verallgemeinern wegen der Fähigkeit, nebenläufige Ereignisse darzustellen, die Automatentheorie.

Inhaltsverzeichnis

Funktionsweise

Einfaches Petri-Netz

Ein Petri-Netz ist ein bipartiter und gerichteter Graph. Er besteht aus Stellen (Places) und Übergängen bzw. Transitionen (Transitions). Stellen und Transitionen sind durch gerichtete Kanten verbunden. Es gibt keine direkten Verbindungen zwischen zwei Stellen oder zwei Transitionen.

Einfaches Petri-Netz

Stellen werden als Kreise, Transitionen als Rechtecke dargestellt. Jede Stelle hat eine Kapazität und kann entsprechend viele Token (Marken bzw. Zeichen) enthalten. Ist keine Kapazität angegeben, steht das für unbegrenzte Kapazität oder für eins. Jeder Kante ist ein Gewicht zugeordnet, das die Kosten dieser Kante festlegt. Ist einer Kante kein Gewicht zugeordnet, wird der Wert eins verwendet.

Sind alle Kapazitäten der Stellen und Gewichte der Kanten eines Petri-Netzes 1, so wird es auch als Bedingungs-, Prädikat- oder Ereignis-Netz bezeichnet.

Die Belegung der Stellen heißt Markierung und ist der Zustand des Petri-Netzes.

Transitionen sind aktiviert bzw. schaltbereit, falls sich in allen Eingangsstellen mindestens so viele Marken befinden, wie die Transitionen Kosten verursacht und alle Ausgangsstellen noch genug Kapazität haben, um die neuen Marken aufnehmen zu können. Schaltbereite Transitionen können zu einem beliebigen Zeitpunkt schalten. Beim Schalten einer Transition werden aus deren Eingangsstellen entsprechend den Kantengewichten Marken entnommen und bei den Ausgangsstellen entsprechend den Kantengewichten Marken hinzugefügt. Marken werden in einem Petri-Netz nicht bewegt. Sie werden entfernt und erzeugt!

Die Marken eines Petri-Netzes sind in ihrer einfachsten Form voneinander nicht unterscheidbar. Für komplexere, aussagekräftigere Petri-Netze sind Markeneinfärbungen, Aktivierungszeiten und Hierarchien definiert worden.

Wichtige Begriffe

Lebendigkeit:

Eine Transition heißt
  • tot, falls sie unter keiner Folgemarkierung aktiviert ist.
  • aktivierbar, falls sie unter mindestens einer Folgemarkierung aktiviert ist.
  • lebendig, falls sie in jeder erreichbaren Markierung aktivierbar ist.
Ein Petri-Netz heißt
  • tot, falls alle Transitionen tot sind.
  • todesgefährdet, falls das Petri-Netz unter einer Folgemarkierung tot ist.
  • verklemmungsfrei oder schwach lebendig, falls es unter keiner Folgemarkierung tot ist.
  • (stark) lebendig, falls alle Transitionen lebendig sind.

Erreichbarkeit: Eine Markierung eines Petri-Netzes heißt erreichbar, falls es eine Schaltsequenz der Transitionen gibt, welche die Startmarkierung in diese Markierung überführt.

Konservativität: Ein Petri-Netz heißt konservativ, falls die (beliebig) gewichtete Summe der Marken konstant ist.

Beschränktheit: Ein Petri-Netz heißt b-beschränkt, wenn es eine Schranke b gibt, so dass nie mehr als b Marken in einer Stelle liegen.

Sicherheit: Ein Petri-Netz heißt sicher, falls es 1-beschränkt ist.

Konflikt: Es besteht ein Konflikt bei einer nicht nebenläufigen Aktivierung von zwei Transitionen. Im Vorbereich bedeutet das, dass zwei Transitionen die gleiche Marke benötigen um zu schalten. Im Nachbereich sind es zwei Transitionen, die Marken erzeugen können, aber die Kapazität nicht für beide ausreicht.

Kontakt: Eine Transition hat Kontakt, wenn sie nicht schalten kann, weil sonst die Kapazität einer Stelle im Nachbereich überschritten würde.

Formale Definition

Ein Petri-Netz ist ein 6-Tupel (S,T,F,K,W,m0). Durch das 3-Tupel (S,T,F) ist ein bipartiter und gerichteter Graph definiert.

  • S, nichtleere Menge von Stellen S = {s1,s2,...,s|S|}
  • T, nichtleere Menge von Transitionen (Übergängen) T = {t1,t2,...,t|T|}
  • F, nichtleere Menge der Kanten (Flussrelation) F ⊆ (S × T) ∪ (T × S)
  • K, Kapazitäten der Plätze, Kapazitätsfunktion K : S → \mathbb{N}\,\cup\,\{\infty\}
  • W, Kosten der Kanten, Gewichtsfunktion W : F → \mathbb{N}
  • m0, Startmarkierung m0 : S → \mathbb{N}

Die Mengen der Stellen S und Transitionen T sind disjunkt (formal: S \cap T = \emptyset). Die aktuelle Markierung m : S \rightarrow \mathbb{N} bezeichnet man als Zustand des Petri-Netzes. m(s) ist die Anzahl der Marken auf Stelle s.

Folgende (Teil-)Mengen sind für t \in T definiert:

  • Vorbereich \bullet t = \lbrace s \in S | (s,t) \in F \rbrace, also alle Stellen, von denen eine Kante zur Transition t führt,
  • Nachbereich t\bullet = \lbrace s \in S | (t,s) \in F \rbrace, also alle Stellen, zu denen eine Kante von der Transition t aus führt.

Schaltbereitschaft

Eine Transition t heißt aktiviert, schaltbereit oder hat Konzession, falls gilt:

  1. \forall s \in \bullet t \setminus t\bullet : m(s) \ge W(s,t)
  2. \forall s \in t\bullet \setminus \bullet t : K(s) \ge m(s) + W(t,s)
  3. \forall s \in t\bullet \cap \bullet t : K(s) \ge m(s) - W(s,t) + W(t,s)

Schaltvorgang

Eine aktivierte Transition t kann schalten. Falls sie schaltet, werden für alle Stellen s die Anzahl der Marken m'(s) wie folgt neu berechnet:


m'(s) = \begin{cases}
m(s) - W(s,t)          & \text{ falls } s     \in \bullet t \text{ und } s \not\in t\bullet\\
m(s) + W(t,s)          & \text{ falls } s \not\in \bullet t \text{ und } s     \in t\bullet\\
m(s) - W(s,t) + W(t,s) & \text{ falls } s     \in \bullet t \text{ und } s     \in t\bullet\\
m(s)                   & \text{ falls } s \not\in \bullet t \text{ und } s \not\in t\bullet
\end{cases}

Aus einer Stelle s im Vorbereich der Transition t werden beim Schalten so viele Marken entnommen, wie es die Kosten W an der entsprechenden Kante (s,t) vorgeben. Entsprechend werden Marken im Nachbereich erzeugt. Eine Stelle s, die weder im Vor- noch im Nachbereich der Transition t liegt, wird nicht verändert, wenn die Transition t schaltet.

Inzidenzmatrix

Die Inzidenzmatrix C eines Petri-Netzes zeigt jeweils an, wie sich die Markenzahl einer Stelle si (dargestellt durch die Zeilen der Matrix) durch ein Schalten der Transition tj (Spalten der Matrix) vergrößert oder verringert.

Sie ist definiert durch:

C_{ij}:=\begin{cases}
-W(s_i,t_j),            & \text{ falls } s_i     \in \bullet t_j \text{ und } s_i \not\in t_j\bullet\\
W(t_j,s_i),             & \text{ falls } s_i \not\in \bullet t_j \text{ und } s_i     \in t_j\bullet\\
W(t_j,s_i)-W(s_i,t_j),  & \text{ falls } s_i     \in \bullet t_j \text{ und } s_i     \in t_j\bullet\\
0                       & \text{ sonst},
\end{cases}

für 1 \leq i \leq m, 1 \leq j \leq n. Hierbei ist zu beachten, dass Schlingen nur mit der Differenz ihrer beiden Kantengewichte, bei Gleichheit also gar nicht, das heißt nur als 0, in der Inzidenzmatrix C auftauchen[1].

Synchronisationskonzepte in Petri-Netzen

  • Nebenläufige Ausführung
  • Semaphore
  • Lese-Schreib-Puffer

Erweiterte Petri-Netze

Um mit Petri-Netzen genauere Modelle aufstellen zu können, wurden diese im Laufe der Zeit um neue Elemente erweitert. Daraus entstanden neue Klassen von Petri-Netzen, die einerseits mächtiger sind, andererseits aber schwerer oder gar nicht geschlossen analysiert werden können.

Prioritäten und hemmende Kanten

  • Prioritäten werden als Zahlen, beginnend mit 1, neben einer Transition notiert. Wenn zwei zeitlose Transitionen aktiviert sind, schaltet die mit der höheren Priorität.
  • Hemmende Kanten verbinden Stellen mit Transitionen. Wenn eine hemmende Kante durch eine Marke in ihrer Ausgangsstelle aktiviert ist, kann die verbundene Transition nicht feuern, auch wenn alle ihre anderen eingehenden Kanten aktiviert sind.

Durch Prioritäten und hemmende Kanten erreichen Petri-Netze die Mächtigkeit der Turingmaschine.

Zeiterweiterte Petri-Netze

Zusätzlich zu den zeitlosen Transitionen der klassischen Petri-Netze wurden Transitionen eingeführt, welche beim Schalten Zeit verbrauchen. Dabei unterscheidet man verschiedene Klassen von Netzen, je nachdem welche Art von zeitverbrauchenden Transitionen in ihnen vorkommen:

  • SPN (Stochastic Petri Net): Jede Transition verbraucht Zeit. Die Zeit, die eine Transition beim Schalten verbraucht, ist eine Zufallsvariable und exponentialverteilt. Diese Klasse von Petrinetzen eignet sich nicht zur Modellierung von Synchronisation.
  • GSPN (Generalized Stochastic Petri Net): Enthalten exponentialverteilte zeitbehaftete Transitionen und zeitlose Transitionen. Diese Klasse von Petri-Netzen lässt sich noch geschlossen analysieren. Warteschlangensysteme lassen sich als sehr einfache GSPNs darstellen.
  • DSPN (Deterministic Stochastic Petri Net): Neben den exponentialverteilten zeitbehafteten Transitionen gibt es auch solche mit deterministischer Schaltzeit. Dieser werden als ausgefüllte Rechtecke gezeichnet. Die Komplexität von DSPNs ist ungleich höher als die von GSPNs: Nur wenn in einem DSPN nie mehr als eine deterministische Transition aktiviert sein kann, ist es überhaupt noch analysierbar. Dennoch sind DSPNs beliebt, da sich viele Sachverhalte mit ihnen sehr viel genauer modellieren lassen und gute numerische Simulationsmethoden existieren.
  • Allgemeine Stochastische Petrinetze mit beliebigen Schaltzeitverteilungen.

Farbige Petri-Netze

Farbige Petri-Netze erweitern Marken um verschiedenen "Farben", indem die Marken nun strukturiert und getypt sind. Während Marken bei normalen Petri-Netzen nicht unterschieden werden können, ist dies durch die Färbung der Marken möglich.

Attributierte Petri-Netze

Verallgemeinerte Form der Petri-Netze, bei der Transitionen, Stellen und Konnektoren mit Attributen versehen werden können.

  • Die Attributierung der Konnektoren dient dazu, Daten und Objekte durch das Petrinetz zu transportieren.
  • Die Attributierung der Stellen dient der Regulierung deren Kapazität.
  • Die Attribute von Transitionen dienen der Zeitmodellierung, Verarbeitung der transportierten Daten sowie der bedingten Ausführung von Transitionen.

Anwendungsgebiete

Siehe auch

Literatur

  • Abel, Dirk: Petri-Netze für Ingenieure − Modellbildung und Analyse diskret gesteuerter Systeme, Berlin: Springer Verlag, 1990, ISBN 3-540-51814-2
  • Baumgarten, Bernd : Petri-Netze - Grundlagen und Anwendungen, Heidelberg: Spektrum Akademischer Verlag, 1996, ISBN 3-8274-0175-5
  • Billington, Jonathan ; Reisig, Wolfgang: Application and Theory of Petri Nets, Springer, 1996, ISBN 3-540-61363-3
  • König, Rainer ; Quäck, Lothar: Petri-Netze in der Steuerungs- und Digitaltechnik, München: Oldenbourg, 1988, ISBN 3-486-20735-0
  • Petri, Carl Adam: Kommunikation mit Automaten, Bonn: Schriften des Rheinisch-Westfälischen Institutes für instrumentelle Mathematik an der Universität Bonn, 1962
  • Priese, Lutz ; Wimmel, Harro: Petri Netze, Berlin: Springer Verlag, 2008, ISBN 978-3-540-76970-5
  • Reisig, Wolfgang: Petrinetze - Eine Einführung, Berlin: Springer, 1990, ISBN 3-540-16622-X
  • Reisig, Wolfgang ; Rozenberg, Grzegorz: Lectures on Petri Nets, Springer, 1998, ISBN 3-540-65306-6
  • Starke, Peter H.: Analyse von Petri-Netz-Modellen, Stuttgart: B.G. Teubner, 1990, ISBN 3-519-02244-3
  • Zuse, Konrad: Petri-Netze aus der Sicht des Ingenieurs, Braunschweig: Vieweg, 1980, ISBN 3-528-09615-2

Weblinks

Einzelnachweise

  1. Baumgarten, Bernd: Petri-Netze. Grundlagen und Anwendungen. BI-Wissenschaftsverlag, Mannheim 1990, ISBN 3-411-14291-X

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Petri-Netz — Petri Netz,   eine 1962 von dem deutschen Mathematiker C. A. Petri (*1926) vorgeschlagene grafische Darstellung (Netz) zur Beschreibung und Analyse von sog. nebenläufigen Prozessen (Nebenläufigkeit), die in Systemen auftreten, die aus vielen… …   Universal-Lexikon

  • Petri-Netz — Petri tinklas statusas T sritis automatika atitikmenys: angl. Petri net vok. Petri Netz, n rus. сеть Петри, f pranc. réseau de Petri, m ryšiai: sinonimas – Petri tinklas …   Automatikos terminų žodynas

  • Petri-Netz — Als Petri Netze werden Modelle diskreter, vorwiegend verteilter Systeme bezeichnet, die alle einigen wenigen, einfachen Prinzipien genügen. Diese Prinzipien hat der Informatiker Carl Adam Petri in den 1960er Jahren entwickelt. Heutzutage werden… …   Deutsch Wikipedia

  • Petri-Netz — Methode zur funktionellen Spezifikation von Abläufen mittels Objekt/Funktion Reihungsnetzen …   Acronyms

  • Petri-Netz — Methode zur funktionellen Spezifikation von Abläufen mittels Objekt/Funktion Reihungsnetzen …   Acronyms von A bis Z

  • Erreichbarkeitsgraph (Petri-Netz) — Ein Erreichbarkeitsgraph ist ein gerichteter Graph, der aus einem Petri Netz und einer Anfangsmarkierung gewonnen werden kann. Er wird dadurch erzeugt, dass, mit der Anfangsmarkierung beginnend, die Menge der in der Markierung aktivierten… …   Deutsch Wikipedia

  • Petri — ist der Familienname folgender Personen: Adam Petri (1454–1528), Schweizer Buchdrucker Anton Peter Petri (1923–1995), deutscher Historiker und Volkskundler August Petri (≈1793–??), deutscher Gartenkünstler Bernhard Petri (1767–1853),… …   Deutsch Wikipedia

  • Petri net — Petri tinklas statusas T sritis automatika atitikmenys: angl. Petri net vok. Petri Netz, n rus. сеть Петри, f pranc. réseau de Petri, m ryšiai: sinonimas – Petri tinklas …   Automatikos terminų žodynas

  • Petri tinklas — statusas T sritis automatika atitikmenys: angl. Petri net vok. Petri Netz, n rus. сеть Петри, f pranc. réseau de Petri, m ryšiai: sinonimas – Petri tinklas …   Automatikos terminų žodynas

  • Netz — Netzwerk; Internet (umgangssprachlich); WWW; World Wide Web; Web * * * Netz [nɛts̮], das; es, e: 1. durch Flechten oder Verknoten von Fäden oder Seilen entstandenes Gebilde aus Maschen, das in unterschiedlicher Ausführung den verschiedensten… …   Universal-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”