Heim

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

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.

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 Kanten eines Petri-Netzes 1, so wird es auch als Bedingungs-/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
Ein Petri-Netz heißt

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, wo man den Konflikt auch als Kontakt bezeichnet, sind es zwei Transitionen, die Marken erzeugen können, aber die Kapazität nicht für beide ausreicht.

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.

Die Mengen der Stellen S und Transitionen T sind disjunkt (formal: ). Die aktuelle Markierung bezeichnet man als Zustand des Petri-Netzes. m(s) ist die Anzahl der Marken auf Stelle s.

Folgende (Teil-)Mengen sind für definiert:

Schaltbereitschaft

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

  1. ∀s ∈ •t : m(s) ≥ W(s,t)
  2. ∀s ∈ t•\•t : K(s) ≥ m(s) + W(t,s)
  3. ∀s ∈ t•∩•t : K(s) ≥ m(s) - W(s,t) + W(t,s)

Schaltvorgang

Eine aktivierte Transition t kann schalten. Falls sie schaltet, werden für alle Plätze s die Anzahl der Marken wie folgt neu berechnet:

m'(s) = m(s) - W(s,t) falls s ∈ •t und s ∉ t•
m'(s) = m(s) + W(t,s) falls s ∉ •t und s ∈ t•
m'(s) = m(s) - W(s,t) + W(t,s) falls s ∈ •t und s ∈ t•
m'(s) = m(s) sonst

Synchronisationskonzepte in Petri-Netzen

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

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:

Farbige Petri-Netze

Farbige Petri-Netze erweitern die zeiterweiterten Petrinetze um Marken mit verschiedenen Farben. 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.

Anwendungsgebiete


Siehe auch

Literatur