External PhD Students - Felix Engelhard

Name:	Felix Engelhard
Affiliation:	DaimlerChrysler AG, Research Center Esslingen
Email:	Felix.Engelhard@daimlerchrysler.com
Degree:	Diplom-Informatik, Universität Erlangen-Nürnberg, 2001

Title of Thesis Project

Effiziente numerische Analyse nicht-Markoff’scher Petri-Netze mit Hilfe symbolischer Speichertechniken

Summary of Thesis Project

Das Hauptziel dieser Arbeit ist die Entwicklung und Implementierung eines Verfahrens, das die analytisch numerische Lösung nicht-Markoffscher Petri-Netze erlaubt, um damit Fahrzeugkomponenten bezüglich Sicherheit, Zuverlässigkeit, ... analysieren zu können. Hierbei handelt es sich um Petri-Netze, bei denen im Unterschied zu den bekannten GSPNs die verwendeten Transitionen nicht nur exponentiell verteilt oder zeitlos sein können, sondern beliebige Verteilungsfunktionen verwendet werden können. Dies ist insbesondere notwendig, da gerade das Ausfallverhalten von Fahrzeugkomponenten sich nicht durch eine Exponentialverteilung beschreiben läßt. Eine simulative Lösung der aufgebauten Netze scheidet aufgrund der Anforderung, mit dem Verfahren auch sicherheitsanalysen durchführen zu können, aus, da hierbei nicht garantiert werden kann, daß alle möglichen Systemzustände auch durchlaufen werden und somit potentiell gefährliche Zustände übersehen werden können. Eine der wichtigsten Anforderungen an das zu entwickelnde Lösungsverfahren ist, daß dem Benutzer keinerlei Modellierungseinschränkungen bezüglich der Struktur der aufgebauten Netze auferlegt wird, wie das bei anderen Verfahren, wie z.B. der Methode der zusätzlichen Variablen der Fall ist.

Der in dieser Arbeit verfolgte Lösungsansatz verwendet für die Behandlung der nicht-exponentiellen Verteilungen eine Approximation durch Phasentypverteilungen. Damit wird die eigentliche Analyse auf die Analyse eines GSPNs reduziert, allerdings tritt in den meisten Fällen eine enorme Zustandsraumexplosion auf. Das Vorgehen zur Analyse „beliebiger“ Petri-Netze läßt sich somit wie folgt beschreiben:

1. Aufbau des Erreichbarkeitsgaphen für das ursprüngliche Petri-Netz (RG)
2. Reduktion des Erreichbarkeitsgraphen à RRG (= Entfernen aller zeitlosen Zustände aus dem RG, da die Aufenthaltswahrscheinlichkeit in Ihnen 0 ist). Der Grund dafür, daß nicht direkt der reduzierte Erreichbarkeitsgraph aufgebaut wird sondern erst die Variante mit allen Zuständen liegt darin, daß die implementierte Komponente später auch für weitergehende, strukturelle Analysen eingesetzt werden soll, bei denen evtl. die verschwindenden (zeitlosen) Zustände von Bedeutung sind (Livelock)
3. Fit der allgemein verteilten Übergänge im RRG durch jeweils eine Phasentypverteilung
4. Einarbeitung der Phasentypverteilten Übergänge in den Erreichbarkeitsgraphen unter Berücksichtigung der jeweiligen Verdrängungsstrategie
5. Aufbau der für die Analyse (das Hauptaugenmerk liegt hier auf der transienten Analyse) benötigten Matrizen und Vektoren und Berechnung der numerischen Lösung
6. Berechnung von durch Rewards definierten Meßwerten

• Effiziente Erzeugung und Speicherung eines RRG für Netze ohne strukturelle Beschränkungen, was die Verwendung von symbolischen Techniken (MDDS, MTBDDs, Matrixdiagramme, ...) ausschließt
• Fit beliebiger Verteilungsfunktionen durch Phasentypverteilungen: hierbei ist zu beachten, daß die ursprüngliche Funktion gut durch die Phasentypverteilung approximiert werden muß, andererseits aber die Anzahl der verwendeten Phasen möglichst klein gehalten werden muß, da ansonsten das sowieso schon vorhandene Problem der Zustandsraumexplosion noch verschärft wird
• Handhabung der Zustandsraumexplosion bei der Einarbeitung der Phasentypverteilungen in den RRG: dies soll durch die Verwendung symbolischer Techniken ermöglicht werden
• Anpassung von Lösungsverfahren an die verwendeten symbolischen Techniken
• Rückrechnung der Zustandswahrscheinlichkeiten auf dem Phasentypverteilten RRG auf die Rewardwerte, die auf Netzebene definiert sind und nur bis zum RRG mit den Zuständen verknüpft werden können.

• Weibullverteilung (2- und 3-parametrig)
• Exponentialverteilung
• Normalverteilung
• Logarithmische Normalverteilung
• Eine Verteilung, deren Ausfallrate die bekannte Badewannenkurve mit Frühausfällen, stabiler Lebensphase und Verschleißverhalten nachbildet

Ein besonderes Augenmerk bei allen implementierten Techniken liegt, schon durch die Industriebeteiligung, auf der Praxistauglichkeit der verwendeten Techniken und der Umsetzung in Tools, die auch von nicht-Experten angewendet werden können.