Petri-Netz

Zur Modellierung und Analyse von parallelen, nebenläufigen Prozessen in technischen und informatischen Systemen.

Ziel: Abläufe mit Synchronisation, Parallelität und Bedingungen verständlich und mathematisch beschreibbar machen.

Ein Petri-Netz ist ein 3-Tupel: PN(S, T, F)

• S = Stellen (Zustände)

• T = Transitionen (Ereignisse)

• F = Flussrelation (Kanten)

• S ∩ T = ∅

• F ⊆ (S × T) ∪ (T × S)

• Pre-Kanten: von einer Stelle zu einer Transition (S × T)

• Post-Kanten: von einer Transition zu einer Stelle (T × S)

• F = PRE ∪ POST = gesamte Flussrelation

Vorbereich: Alle Stellen, von denen eine Kante zur Transition führt:

•Tᵢ = { s ∈ S | (s, Tᵢ) ∈ F }

Nachbereich: Alle Stellen, zu denen die Transition eine Kante hat:

Tᵢ• = { s ∈ S | (Tᵢ, s) ∈ F }

Beispiel:

• Marken zeigen aktive Zustände (liegen auf Stellen)

• Transitionen sind schaltbereit, wenn alle Vor-Stellen markiert sind

• Beim Schalten:

  • Marken werden aus Vor-Stellen entfernt

  • Marken in Nach-Stellen eingefügt

→ Dadurch ändert sich die Markierung, der Ablauf schreitet voran

→ Petri-Netze werden so dynamisch und können Abläufe modellieren

Grafisch: Marken = schwarze Punkte auf Stellen (◦●◦)

→ Verschiedene Netztypen unterscheiden sich in Anzahl, Art, Bedingungen und Wirkung der Marken.

Eine Testkante erlaubt das Schalten einer Transition nur, wenn die verbundene Stelle markiert ist.Beim Schalten bleibt die Marke unverändert → reine Zustandsprüfung, keine Markenänderung.

• Testkante prüft nur, ob Marke vorhanden ist → keine Entnahme

• Pre-Kante entnimmt beim Schalten eine Marke

• Testkanten beeinflussen die Markierung nicht

Eine Inhibitorkante erlaubt das Schalten einer Transition nur, wenn die verbundene Stelle nicht markiert ist. Beim Schalten bleibt die Markierung unverändert.

→ Dient zur Ausschlussbedingung (z. B. „Not-Aus darf nicht aktiv sein“)

Ein B-E-Netz ist ein 4-Tupel PN(S, T, F, m₀) mit:

• binärer Markierung m: S → {0, 1}

• jede Stelle hat entweder 0 oder 1 Marke

• Markierung ist dynamisch und ändert sich beim Schalten

Wenn:

• alle Vor-Stellen markiert sind

• alle Nach-Stellen unmarkiert sind

• → auch: Konzessionsregel

• Marken aus Vor-Stellen entfernt

• Marken in Nach-Stellen eingefügt

• → ergibt neue Markierung mₖ₊₁

• → auch: Markenflussregel

Eine Schlinge liegt vor, wenn eine Stelle gleichzeitig im Vor- und Nachbereich einer Transition liegt.

→ Die Transition ist niemals schaltbereit

→ Schlingenfreie Netze = „rein“

Schlinge:

Vor- und Nachbereich der Transition müssen disjunkt sein: 

•Tᵢ ∩ Tᵢ• = ∅

→ sonst keine Schaltbereitschaft möglich (z. B. bei Schlingen)

Zwei Mengen sind disjunkt, wenn sie keine gemeinsamen Elemente haben.

Schaltkonflikte: Mehrere Transitionen sind gleichzeitig schaltbereit, aber nicht alle dürfen schalten

Vorwärtskonflikt: T₁ und T₂ haben gemeinsame Vor-Stelle – Nur eine Transition kann die Marke verwenden

Rückwärtskonflikt: T₁ und T₂ haben gemeinsame Nach-Stelle – Nur eine darf die Stelle markieren

Hinweis: Konflikte deuten auf fehlende Entscheidung im Modell → durch Entscheidungsregeln lösbar.

Testkanten:

• Werden genutzt, wenn eine Stelle als Bedingung geprüft, aber nicht geleert werden soll

• → z. B. „Maschine o.k.“ = Information, keine Ressource

Inhibitorkanten:

• Prüfen, ob keine Marke vorhanden ist

• → Nützlich für Zustände wie „Nicht belegt“, „Störung aktiv“

Fazit:

• → Beide Kantenarten ermöglichen logische Abfragen ohne Einfluss auf den Ablauffluss.

• → Wichtig bei steuernden Informationen statt Ressourcenverbrauch.

Die Anfangsmarkierung bestimmt, welche Transitionen schaltbereit sind und beeinflusst die gesamte Netzdynamik. Beispiel: Gleiches Netz kann je nach m₀ nur einmal oder unendlich oft schalten.

Für eine Anfangsmarkierung m₀ kann man:

• alle schaltfähigen Transitionen ermitteln

• durch deren Schalten die Folgemarkierungen berechnen

• so alle erreichbaren Markierungen im Netz bestimmen

• → diese werden im Erreichbarkeitsgraph als Knoten mit Übergängen dargestellt

Ziel: Darstellung aller möglichen Zustandsverläufe des Netzes

Beispiele:

Ein Netz ist lebendig, wenn jede Transition (oder Teilnetz) irgendwann wieder schalten kann.

→ Keine dauerhafte Blockade

Ein Netz ist reversibel, wenn von jeder erreichbaren Markierung aus die Anfangsmarkierung m₀ wieder erreichbar ist.

→ Rückkehr zum Ausgangszustand möglich

Eine Transition ist lebendig, kann aber nie schalten, weil sie nicht in den zyklischen Abläufen enthalten ist.

→ System läuft, aber bestimmte Aktionen bleiben blockiert

→ Beispiel: zwei Personen weichen sich im Flur aus, ohne weiterzukommen.

Ein Zustand, in dem keine Transition mehr schalten kann.

→ System steht still

→ Ursache: keine schaltbereiten Transitionen mehr

Eine tote Transition ist eine Transition, die bei der gegebenen Anfangsmarkierung niemals schaltbereit wird – egal, wie sich das Netz entwickelt.

→ Sie bleibt dauerhaft inaktiv.

→ Hinweis auf ungenutzte Teile des Modells.

• Komposition: Zusammenfassen mehrerer Netze oder Schritte zu einem gröberen Ablauf

• Dekomposition: Aufteilen eines groben Netzes in feinere Teilschritte

• → Ziel: Anpassung der Modelltiefe je nach Analysezweck

• Die dynamischen Eigenschaften (z. B. Markenzahl) müssen erhalten bleiben

• wichtig: relevante Stellen und Transitionen dürfen nicht ersetzt werden

• Komposition sollte vor dem Erreichbarkeitsgraphen erfolgen, um die Komplexität zu reduzieren

• Vereinfachung des Modells ohne Verlust wichtiger Eigenschaften

• ermöglicht bessere Übersicht und gezieltere Erreichbarkeitsanalyse

• reduziert unnötige Komplexität im Erreichbarkeitsgraphen und spart Aufwand

• Die Inzidenzmatrix beschreibt die Struktur des Petri-Netzes in Matrixform.

• Sie zeigt die Verknüpfung von Stellen und Transitionen.

• Eine Zeile entspricht einer Stelle, eine Spalte einer Transition.

• Wird verwendet zur Berechnung von Folgemarkierungen, S-Invarianten und T-Invarianten.

1. Sie dient zur Berechnung von:

   • Folgemarkierungen

   • Erreichbarkeitsgraphen

   • Konflikten / Deadlocks

   • Zustandsschätzungen

2. Besonders hilfreich bei komplexen Netzen mit vielen möglichen Markierungen.

• Eine T-Invariante ist eine Menge von Transitionen, bei denen nach einmaligem Schalten jeder Transition wieder die ursprüngliche Markierung entsteht.

• Sie beschreibt zyklisches Verhalten im Netz.

• Man findet sie über die Spaltensumme der Inzidenzmatrix C: → Die Summe der Spalten, die zur T-Invariante gehören, ergibt den Nullvektor.

• Beispiel:

• Eine S-Invariante ist eine Menge von Stellen, bei denen die Gesamtanzahl der Marken konstant bleibt, unabhängig vom Schalten.

• Sie beschreibt Ressourcenerhaltung im Netz.

• Man findet sie über die Zeilensumme der Inzidenzmatrix C: → Die Summe der Zeilen, die zur S-Invariante gehören, ergibt den Nullvektor.

• Beispiel:

Ein S-T-Netz erlaubt beliebige (natürliche) Anzahl von Marken in einer Stelle. Kanten besitzen ein Kantengewicht und beim Schalten einer Transition werden entsprechend viele Marken entfernt bzw. hinzugefügt. Vor- und Nachbereich dürfen überlappen.

• Markierung: B-E-Netz: binär (0 oder 1), S-T-Netz: beliebige Anzahl (≥ 0)

• Disjunktheit: B-E-Netz: Vor-/Nachbereich müssen disjunkt sein, S-T-Netz: nicht notwendig

• Kanten: B-E-Netz: Kanten ohne Gewicht, S-T-Netz: Kanten mit Gewicht (>1 möglich)

Er zeigt für jede mögliche Markierung, wie viele Marken sich auf welchen Stellen befinden, und welche Transitionen zu welcher Nachmarkierung führen.

• Voraussetzung: Alle Stellen im Vorbereich müssen so viele Marken enthalten, wie durch die Kantengewichte gefordert.

• Beim Schalten:

  • aus dem Vorbereich: Entnahme der Marken gemäß Kantengewicht

  • im Nachbereich: Hinzufügen von Marken gemäß Kantengewicht

• Kurz: Markenfluss = Entnahme und Erzeugung nach Kantengewicht

1. Abstrakte Zustände und Zustandsübergänge (Angebot-Auftrag-Zustimmung)

2. Physikalische Zustände und Zustandsübergänge (Dunkel-Licht einschalten-Hell)

3. Ressoursenzustände und Bestandänderungen (Material verfügbar-Verbrauch-Material verbraucht)

4. Positions-Zustände und Zustandsübergänge (Fahrzeug im Depot-herausholen-Fahrzeug draußen)