Was ist eine Stelle in einem Petri-Netz?
Was ist eine Transition in einem Petri-Netz?
Was ist eine Kante in einem Petri-Netz?
Wofür wurden Petri-Netze ursprünglich entwickelt?
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.
Was ist ein Petri-Netz?
Was ist ein Petri-Netz in Mengendarstellung?
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)
Was sind Pre- und Post-Kanten in einem Petri-Netz?
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
Was ist der Vorbereich einer Transition? Was ist der Nachbereich einer Transition?
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:
Wie kommt Dynamik in Petri-Netze? Welche Rolle spielen Marken und Transitionen dabei?
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.
Was ist eine Testkante in einem Petri-Netz und wie wirkt sie beim Schalten?
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.
Worin unterscheidet sich eine Testkante von einer normalen Pre-Kante?
Testkante prüft nur, ob Marke vorhanden ist → keine Entnahme
Pre-Kante entnimmt beim Schalten eine Marke
Testkanten beeinflussen die Markierung nicht
Was ist eine Inhibitorkante im Petri-Netz und wann erlaubt sie das Schalten?
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“)
Was ist ein Bedingungs-Ereignis-Netz (B-E-Netz)?
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
Wann ist eine Transition in einem B-E-Netz schaltbereit? (1. Schaltregel)
Wenn:
alle Vor-Stellen markiert sind
alle Nach-Stellen unmarkiert sind
→ auch: Konzessionsregel
Was passiert beim Schalten einer Transition? (2. Schaltregel)
Marken aus Vor-Stellen entfernt
→ ergibt neue Markierung mₖ₊₁
→ auch: Markenflussregel
Was ist eine Schlinge im B-E-Netz und was bewirkt sie?
Eine Schlinge liegt vor, wenn eine Stelle gleichzeitig im Vor- und Nachbereich einer Transition liegt.
→ Die Transition ist niemals schaltbereit
→ Schlingenfreie Netze = „rein“
Schlinge:
Welche Bedingung muss gelten, damit eine Transition überhaupt schaltbereit werden kann?
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.
Was sind Schaltkonflikte in B-E-Netzen? Was ist der Unterschied zwischen Vorwärts- und Rückwärtskonflikt?
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.
Anwendungsbeispiel VL07
Wozu benötigt man Test- und Inhibitorkanten im Petri-Netz? Wie hängt das mit Informationsabfragen zusammen?
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.
Welchen Einfluss hat die Anfangsmarkierung m₀ auf ein Petri-Netz?
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.
Was ist ein Erreichbarkeitsgraph und wie wird er erstellt?
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:
Was bedeutet Lebendigkeit in einem Petri-Netz?
Ein Netz ist lebendig, wenn jede Transition (oder Teilnetz) irgendwann wieder schalten kann.
→ Keine dauerhafte Blockade
Was bedeutet Reversibilität in einem Petri-Netz?
Ein Netz ist reversibel, wenn von jeder erreichbaren Markierung aus die Anfangsmarkierung m₀ wieder erreichbar ist.
→ Rückkehr zum Ausgangszustand möglich
Was ist ein Livelock im Petri-Netz?
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.
Was ist ein Deadlock (Verklemmung) im Petri-Netz?
Ein Zustand, in dem keine Transition mehr schalten kann.
→ System steht still
→ Ursache: keine schaltbereiten Transitionen mehr
Was ist eine tote Transition?
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.
Was ist der Unterschied zwischen Komposition und Dekomposition bei Petri-Netzen?
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
Worauf sollte man bei einer Komposition achten?
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
Was bringt die Komposition für die Analyse von Petri-Netzen?
Vereinfachung des Modells ohne Verlust wichtiger Eigenschaften
ermöglicht bessere Übersicht und gezieltere Erreichbarkeitsanalyse
reduziert unnötige Komplexität im Erreichbarkeitsgraphen und spart Aufwand
Was ist die Inzidenzmatrix in Petri-Netzen?
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.
Wie ist die Inzidenzmatrix aufgebaut?
Was sagt der Spaltenvektor einer Transition aus?
Was bedeuten die Werte in der Inzidenzmatrix?
Was sind S- und T-Invarianten?
Wie hilft die Inzidenzmatrix in der Analyse?
Sie dient zur Berechnung von:
Folgemarkierungen
Erreichbarkeitsgraphen
Konflikten / Deadlocks
Zustandsschätzungen
Besonders hilfreich bei komplexen Netzen mit vielen möglichen Markierungen.
Was ist eine T-Invariante in einem Petri-Netz und wie findet man sie?
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.
Was ist eine S-Invariante in einem Petri-Netz und wie findet man sie?
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.
Aufgabe zur Nachbereitung VL07
Was ist ein Stellen-Transitions-Netz (S-T-Netz)?
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.
Was sind zentrale Unterschiede zwischen B-E- und S-T-Netzen?
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)
Was gibt der Erreichbarkeitsgraph eines S-T-Netzes an?
Er zeigt für jede mögliche Markierung, wie viele Marken sich auf welchen Stellen befinden, und welche Transitionen zu welcher Nachmarkierung führen.
Was passiert beim Schalten einer Transition in einem S-T-Netz?
Voraussetzung: Alle Stellen im Vorbereich müssen so viele Marken enthalten, wie durch die Kantengewichte gefordert.
aus dem Vorbereich: Entnahme der Marken gemäß Kantengewicht
im Nachbereich: Hinzufügen von Marken gemäß Kantengewicht
Kurz: Markenfluss = Entnahme und Erzeugung nach Kantengewicht
Welche Arten von dynamischen Abläufen lassen sich durch Petrinetze darstellen?
Abstrakte Zustände und Zustandsübergänge (Angebot-Auftrag-Zustimmung)
Physikalische Zustände und Zustandsübergänge (Dunkel-Licht einschalten-Hell)
Ressoursenzustände und Bestandänderungen (Material verfügbar-Verbrauch-Material verbraucht)
Positions-Zustände und Zustandsübergänge (Fahrzeug im Depot-herausholen-Fahrzeug draußen)
Zuletzt geändertvor 7 Tagen