Proxel-basierte Simulationsverfahren für Stochastische Petri-Netze

• Applicant: Professor Dr.-Ing. Graham Horton
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2004 to 2007
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5424348

• Final Report Year: 2007

Final Report Abstract

2.1 Allgemeinverständliche Darstellung der wesentlichen Ergebnisse und der erzielten Fortschritte gegenüber dem Stand des Wissens Beim Projektpartner Daimler AG befindet sich ein System zur Überwachung und Prognose von Qualitäts- und Zuverlässigkeitseigenschaften von Kraftfahrzeugen im Aufbau. Für die Ermittlung von Kennzahlen für diese Eigenschaften werden neben anspruchsvollen Technologien aus den Bereichen Datenbanken und Data Mining vor allem effiziente Methoden zur Analyse von stochastischen Modellen benötigt. Proxel-basierte Methoden stellen einen neuen Ansatz zur Simulation stochastischer Modelle dar, die beispielsweise von stochastischen Petri-Netzen und Warteschlangen implementiert werden. Sie eignen sich besonders für die transiente Analyse kleiner, steifer Simulationsmodelle, so wie diese bei der Qualitäts- und Zuverlässigkeitsmodellierung zum Einsatz kommen. Der Ansatz zeichnet sich gegenüber den bisher eingesetzten Verfahren vor allem durch seine Einfachheit, die deterministische Berechnungsweise und die monotone Konvergenz gegen die exakte Lösung aus. In diesem Forschungsvorhaben werden Proxel-basierte Methoden zur Simulation stochastischer Petri-Netze entwickelt und untersucht. Es konnte nachgewiesen werden, dass sich die neuen Methoden für die Aufgabenstellung beim Industriepartner Daimler sehr gut eignen, da sie mit sehr viel weniger Rechenzeit auskommen als die bisher verwendeten "klassischen Simulationen". Die erarbeiteten Methoden wurden deswegen in das Petri-Netz-Werkzeug des Industriepartners integriert und bilden somit einen Bestandteil des Qualitäts- und Zuverlässigkeitsprognosesystems. Mit Hilfe von Phasentypverteilungen werden allgemein verteilte stochastische Aktivitäten in Simulationsmodellen durch Netzwerke von gedächtnislosen Zuständen ersetzt, für die wiederum bereits effiziente Analyseverfahren bekannt sind. Verbindet man diese Ersetzung anschließend mit Proxel-basierten Verfahren simuliert werden, so lässt sieht dadurch eine hohe Rechenzeitersparnis erzielen. In diesem Forschungsvorhaben wurde ein Algorithmus erarbeitet, der für allgemeine Wahrscheinlichkeitsverteilungen eine sehr genaue Approximation durch zeitdiskrete Phasentypverteilungen bestimmt. Weiterhin wurde ein Verfahren entwickelt und publiziert, wie sich Phasen- und Altersansätze miteinander kombinieren lassen. Die Fehlerbaumanalyse spielt eine sehr wichtige Rolle bei der Qualitäts- und Zuverlässigkeitsmodellierung. Bereits vor dem Forschungsvorhaben konnten Proxelbasierte Verfahren erfolgreich für die quantitative und transiente Analyse einzelner Fehlerbäumen angewendet werden. Durch Studien- und Diplomarbeiten und eine sich in Arbeit befindliche Dissertation wird beim Industriepartner ein allgemeines Fehlerbaumwerkzeug entwickelt, welche die ehemals trivialen Basisereignisse der Fehlerbäume durch Stochastische Petri-Netze ersetzt. Die so vereinigten Modellparadigmen werden anschließend unter anderem durch Proxel-basierte Verfahren analysiert. Das Werkzeug ermöglicht eine realistischere Modellierung von komplexen technischen Systemen als bisher und wird daher in Zukunft beim Industriepartner die momentan eingesetzte Fehlerbaumsoftware eines Drittanbieters ersetzen. 2.2 Ausblick auf künftige Arbeiten und Beschreibung möglicher Anwendungen Proxel-basierte Methoden sind für die Anwendung auf diskrete stochastische Modelle mit kleinem Zustandsraum und hoher Steifheit geeignet. Die am nächsten liegende Anwendung sind daher Qualitäts-, Sicherheits- und Zuverlässigkeitsanalysen für technische Systeme mit sehr hohen Anforderungen an die Genauigkeit der Ergebnisse. Solche Modelle sind zum Beispiel in der Automobilindustrie oder der Luft- und Raumfahrtbranche anzutreffen. Üblicherweise werden mit ihnen die Wahrscheinlichkeiten und finanziellen Konsequenzen von möglichen Ausfällen bestimmt. Bei derartigen Modellen erreichen die neuen Verfahren in vergleichbarer Zeit eine um mehrere Größenordnungen höhere Genauigkeit als die klassische Monte-Carlo-Simulation. Die erarbeitete Methode wird unter anderem in ein Petri-Netz-Werkzeug des Industriepartners Daimler im Rahmen eines Systems zur Qualitätssicherung integriert. Zum Gelingen des Vorhabens sind zwei weitere Innovationen erforderlich: die Kombination von diskreten Phasen- und Alterszusatzvariablen und der Einsatz lokal angepasster Zeitschrittweiten während der Simulation. Phasen- und Altersvariablen ließen sich bisher kaum kombinieren. Unsere Voruntersuchungen haben nachgewiesen, dass ein gemeinsamer Einsatz von Proxels und zeitdiskreten Phasen sehr elegant möglich ist und viel Rechenzeit spart. Es konnte ebenfalls prototypisch gezeigt werden, dass die lokal angepasste Zeitschrittweite die notwendige Rechenzeit drastisch verringern kann. Das Hauptanliegen im weiteren Verlauf des Forschungsvorhabens ist, die Ergebnisse der bisherigen prototypischen Entwicklungen so zu verallgemeinern, dass diese in einer für Anwender nutzbaren Form vorliegen. Dazu gehören die Weiterentwicklung eines Softwarewerkzeuges und die fortgesetzte Integration der neuen Verfahren in das Prognosesystem des Industriepartners. Weiterhin ist vorgesehen, die Analyse für allgemeine diskrete stochastische Modelle und unter Zuhilfenahme von verschiedenen Klassen von Zusatzvariablen weitestgehend zu automatisieren. Eine Möglichkeit zur automatischen Parametrisierung des Verfahrens würde die Anwendung erleichtern und damit nicht zuletzt auch die Akzeptanz erhöhen.

Publications

• C. Isensee, F. Wickborn, G. Morton. TRAINING HIDDEN NON-MARKOV MODELS The 13th International Conference on ANALYTICAL and STOCHASTIC MODELLING TECHNIQUES and APPLICATIONS, 28-31 May 2006, Bonn, Germany
  
  
• C. Isensee, G. Horton. A Multi-Level Method for the Steady State Solution of Markov Chains. Simulation und Visualisierung 2004. SCS European Publishing House 2004.
  
  
• C. Isensee, G. Horton. Approximation of Discrete Phase-Type Distributions. Annual Simulation Symposium 2005, San Diego, USA April 2005.publikation
  
  
• C. Isensee, G. Horton. Fast Simulation Without Randomness: A Simulation Tool Combining Proxels & Discrete Phases. 18th Symposium Simulationstechnik (ASIM 2005), SCS European Publishing House, Erlangen, Germany. September 2005.
  
  
• C. Isensee, G. Horton. Proxel-based Simulation of Project Schedules. European Simulation multiconference 2004. SCS European Publishing House 2004.
  
  
• C. Isensee, G. Morton. A Multi-Level Method for the Steady State Solution of Discrete-Time Markov Chains 2nd Balkan Conference in Informatics (BCI), 17-19 November 2005, Ohrid, Institute of Informatics, Faculty of Natural Sciences and Mathematics, Skopje, Macedonia. November 2005.
  
  
• C. Isensee, S. Lazarova-Molnar, G. Morton. Combining Proxels and Discrete Phases. International Conference on Modeling, Simulation and Applied Optimization 2005. Sharjah, U.A.E. February 2005,
  
  
• F, Engelhard, S. Heller, G. Morton. Safety Analyses with non-Markovian Stochastic Petri Nets. 18th Symposium Simulationstechnik (ASIM 2005), SCS European Publishing House, Erlangen, Germany. September 2005.
  
  
• F. Wickborn, C. Isensee, T. Simon, S. Lazarova-Molnar, G. Norton. A New Approach for Computing Conditional Probabilities of General Stochastic Processes. 39th Annual Simulation Symposium 2006, Huntsville, AL, USA April 2006.
  
  
• F. Wickborn, G. Morton, S. Heller, F. Engelhard. A General-Purpose Proxel Simulator for an Industrial Software Tool. 18th Symposium Simulationstechnik (ASIM 2005), SCS European Publishing House, Erlangen, Germany. September 2005.
  
  
• F. Wickborn, G. Morton. Feasible State Space Simulation: Variable Time Steps for the Proxel Method. 2nd Balkan Conference in Informatics (BCI) 17-19 November 2005, Ohrid, Institute of Informatics, Faculty of Natural Sciences and Mathematics, Skopje, Macedonia. November 2005.
  
  
• F. Wickborn, G. Morton. Using Proxel-based Simulation for Reliability Analysis of a Hazardous System. Information Technologies in Environmental Engineering. Magdeburg, Germany. September 2005.
  
  
• S. Heller, F. Engelhard, G. Horton, F. Wickborn. Expect, ein industrielles Tool für Zuverlässigkeits-, Sicherheits- und Kostenanalysen komplexer Systeme. 18th Symposium Simulationstechnik (ASIM 2005), SCS European Publishing House, Erlangen, Germany. September 2005
  
  
• S. Lazarova-Molnar, C. Isensee, G. Morton. Phases orProxels: The Decision Factors 2nd Balkan Conference in Informatics (BCI) 17-19 November 2005, Ohrid, Institute of Informatics, Faculty of Natural Sciences and Mathematics, Skopje, Macedonia. November 2005.
  
  
• S. Lazarova-Molnar, G. Morton. A Framework For Perfomability Modeling Using Proxels. International Conference on Modeling, Simulation and Applied Optimization 2005. Sharjah, U.A.E
  
  
• S. Lazarova-Molnar, G. Morton. Proxel-Based Simulation of Stochastic Petri Nets. Simulation und Visualisierung 2004. SCS European Publishing House 2004.
  
  
• S. Lazarova-Molnar, G. Morton. The Meaning of the Lifetime Factor. 18th Symposium Simulationstechnik (ASIM 2005), SCS European Publishing House, Erlangen, Germany. September 2005.
  
  
• S. Lazarova-Molnar, G. Norton. Proxel-Based Simulation of a Warranty Model. European Simulation multiconference 2004. SCS European Publishing House 2004.