SucheSynthese von Petrinetzen aus Szenarien (SYNOPS)
Synops- Synthese von Petrinetzen aus Szenarien (2007 - 2010)
ZusammenfassungLeiter
Vorträge und Publikationen
Diplomarbeiten
Tools
ZusammenfassungDas Verhalten eines Petrinetzes kann gegeben sein durch die Menge seiner Schalt- oder Schrittfolgen, durch Erreichbarkeitsgraphen, aber auch durch halbgeordenete Ereignismengen, die oft als beschriftete azyklische Graphen dargestellt werden. Die zuletzt genannte Semantik erlaubt die explizite Darstellung von kausaler Unabhängigkeit; zwei Ereignisse finden unabhängig statt, wenn sie im Graphen nicht geordnet sind. Während derartige halbgeordnete Semantiken in der Theorie seit langer Zeit betrachtetet werden, finden sie erst in jüngerer Zeit in Anwendungen Beachtung, insbesondere in den Bereichen Geschäftsprozessmodellierung, Webdienste und Eingebettete Systeme, meist in Form verschiedener Varianten von Sequenzdiagrammen.Die traditionelle Vorgehensweise beim modellbasierten Systementwurf - Konstruktion eines Modells und anschließende explizite oder implizite Betrachtung seines Verhaltens - wird vielfach abgelöst durch eine umgekehrte Vorgehensweise: Das Verhalten wird zunächst formalisiert und modelliert, und das Systemmodell wird daraus anschließend automatisch synthetisiert. Während für Petrinetze entsprechende Syntheseverfahren für Schrittfolgen und Erreichbarkeitsgraphen bekannt sind und in der Praxis eingesetzt werden, fehlen Verfahren für die Synthese von Petrinetzen aus halbgeordneten Verhaltensbeschreibungen. Die Entwicklung derartiger Verfahren, ihre Implementierung und Erprobung ist Gegenstand dieses Vorhabens.
Ausgangspunkt sind jüngere Ergebnisse des Antragstellers, die den für Erreichbarkeitsgraphen bekannten Begriff einer ''Region'' auf halbgeordnete Abläufe verallgemeinert. Damit ist die Synthese von Petrinetzen aus halbgeordneten Abläufen grundsätzlich Regionen-basiert möglich. Das bislang entwickelte theoretische Konzept wird verfeinert und implementiert. Es wird verallgemeinert auf höhere Netzklassen und auf Petrinetze mit Erweiterungen um Zeit, Kosten usw., wie sie in der Praxis eingesetzt werden.
Das Projekt knüpft an die früheren DFG-Projekte VIP und SPECIMEN von Prof. Dr. J. Desel an, in denen Petrinetze in der Geschäftsprozessmodellierung bzw. der Steuerungssynthese eingesetzt wurden. An der Durchführung des Projekts SPECIMEN war der Antragsteller mitverantwortlich als lokaler Koordinator beteiligt. Aus dem Projekt VIP entstand das Werkzeug VIPtool, für dessen Pflege und Weiterentwicklung der Antragsteller verantwortlich ist und auf das die Implementierung der Syntheseverfahren aufbaut. Der direkte Bezug zu diesen Anwendungsfeldern stellt die anwendungsorientierte Ausrichtung des Vorhabens sicher.
nach oben
Prof.Dr.Robert Lorenz
E-Mail: Robert{.}Lorenz{at}informatik{.}uni-augsburg{.}de Telefon: +49 821 598 - 2457 Telefon (weitere): 0176/43029198 Fax: +49 821 598 - 4329 Raum: Raum 1023 Gebäude N Sprechzeiten: Montag, 10:00 - 11:00 Hausanschrift: Universitätsstr. 6a
86159 Augsburg
Wiss.Mitarbeiter:
Kölbl Christian
E-Mail: Christian{.}Koelbl{at}informatik{.}uni-augsburg{.}de Huber Markus
E-Mail: Markus{.}Huber{at}informatik{.}uni-augsburg{.}de
nach oben
Telefon: +49 821 598 - 2447 Fax: +49 821 598 - 4329 Raum: Raum 1026 Gebäude N Hausanschrift: Universitätsstr. 6a
86159 Augsburg
Ziele
Das Gesamtziel dieses Vorhabens ist die Entwicklung effizienter Methoden zur Synthese von Petrinetzen aus Verhaltensbeschreibung bzgl. der Halbordnungssemantik, deren Implementierung und deren exemplarische Anwendung in den Bereichen Geschäftsprozessmodellierung, Webdienste, eingebettete Systeme und Steuerungssysteme. Zur Erreichung dieses Ziels definieren wir die folgenden Teilziele. Die Arbeitspakete, die diesen Teilzielen zugeordnet sind, werden nicht nacheinander, sondern teilweise überlappend durchgeführt, so dass die Erreichung dieser Teilziele sich in verschiedenen Aspekten gegenseitig bedingt.S/T-Netze
Das Syntheseproblem für S/T-Netze aus halbordnungsbasierten Verhaltensbeschreibungen soll, ausgehend von den Ergebnissen der Vorarbeiten des Antragstellers (und der Arbeitsgruppe des Lehrstuhls), vollständig gelöst werden. Dazu sollen sowohl Sprachen-basierte (z.B. basierend auf Termen) als auch Graphen-basierte Darstellungen der Halbordnungssemantik (und einzelner Abläufe) berücksichtigt werden. Insbesondere muss die Schwierigkeit gelöst werden, auch unendliche Abläufe und unendliche Mengen von Abläufen endlich darzustellen. Für die Repräsentation der Menge aller Abläufe gibt es im traditionellen, sequentiellen Fall ebenfalls Graphen-basierte Darstellungen wie z.B. den Erreichbarkeitsgraphen. Dieser definiert zusätzlich eine Äquivalenz auf einzelnen Abläufen (derselbe globale Zustand wird erreicht). Eine entsprechende Notation für Mengen halbgeordneter Ablaufbeschreibungen soll entwickelt werden. Hierbei gehen wir von den bekannten Konzepten der Ereignis-Strukturen und der endlichen Präfixe von Entfaltungen aus, die aber stets mit azyklischen Graphen beschrieben werden, so dass unendliches Verhalten entweder nur indirekt oder durch unendliche Strukturen beschreibbar ist.Implementierung
Die entwickelten Syntheseverfahren für S/T-Netze werden implementiert. Dafür verwenden wir das am Lehrstuhl der Arbeitsgruppe existierende Werkzeug VIPtool, integrieren also die entwickelten Syntheseverfahren in die Funktionalität des VIPtools. Die Algorithmen werden mit Hilfe von aus der Literatur bekannten Fallstudien sowie mit Fallstudien aus den im Projekt betrachteten Anwendungsbereichen evaluiert.Anwendung
Es werden Vorgehensmodelle für den Werkzeug-unterstützten Modellentwurf entwickelt, die an den in den Projekten SPECIMEN und VIP entwickelten Vorgehensmodellen anknüpfen, aber wesentlich auf der Modellsynthese aus halbordnungsbasierten Verhaltensbeschreibungen basieren. Die aus diesen Projekten und aus weiteren Industrieprojekten vorliegenden Beispiele werden exemplarisch mit Hilfe dieses Vorgehensmodells fiktiv nochmals entwickelt. Die dabei auftretenden Schwierigkeiten und Lücken werden dokumentiert, finden aber auch Berücksichtigung bei der Verfeinerung der anderen Teilziele.Erweiterungen um Daten, Zeit, Kosten
(Die Erreichung dieses Teilziels ist Schwerpunkt des Projektes im dritten Projektjahr, das in diesem Projektantrag bereits mitkonzipiert ist, auch wenn zunächst nur die Bewilligung für 24 Monate beantragt werden kann)
S/T-Netze abstrahieren in verschiedener Weise zu stark von Aspekten, die in realen Anwendungen von hoher Relevanz sind. Dazu gehören die Berücksichtigung von Daten, Zeit, Kosten, Einschränkungen der Nebenläufigkeit durch knappe Ressourcen und durch Schreibzugriffe, asymmetrische Synchronisation von Ereignissen (wie sie durch sog. ''Event Arcs'' ausgedrückt wird) usw. Diese Aspekte können in Petrinetzen durch verschiedenartige syntaktische Ergänzungen berücksichtigt werden. Der semantische Bereich dieser syntaktischen Ergänzungen liegt vielfach außerhalb des Bereichs der halbgeordneten Abläufe (z.B.\ Kostenaspekte), hat aber teilweise durchaus Einfluss auf die Abhängigkeitsstrukturen der Ereignisse in Abläufen (z.B.\ Ressourcenzugriffe). Um die im vorigen Teilziel formulierten Anwendungsbeispiele möglichst realitätsnah durchführen zu können, müssen die für die Synthese relevanten Aspekte identifiziert werden und die Syntheseverfahren entsprechend erweitert werden. Diese Erweiterungen, aber teilweise auch Erweiterungen, die keinen unmittelbaren Einfluss auf die Syntheseverfahren haben, werden im Vorgehensmodell, in der Implementierung und in den Anwendungsbeispielen mitberücksichtigt.
Vorträge und Publikationen
2009
- Unfolding Semantics of Petri Nets Based on Token Flows
Robin Bergenthum, Sebastian Mauser, Robert Lorenz, Gabriel JuhasFundamenta Informaticae 94, (2009).- Construction of Process Models from Example Runs
Robin Bergenthum, Jörg Desel, Sebastian Mauser, Robert Lorenz Transactions on Petri Nets and Other Models of Concurrency 2, LNCS 5460 (2009).- Synthesis of Petri Nets from Term Based Representations of Infinite Partial Languages
Robert Lorenz, Robin Bergenthum, Jörg Desel, Sebastian Mauser Fundamenta Informaticae 95, 1 (2009).- Executability of Scenarios in Petri Nets
R. Bergenthum, J. Desel, G. Juhas, R. Lorenz, S. Mauser Theoretical Computer Science, 410 (12-13)2008
- R. Bergenthum, R. Lorenz, S. Mauser: Faster Unfolding of General Petri Nets based on Token Flows. Submitted to 29th international conference on Application and Theory of Petri Nets (ICATPN), 2008.
- R. Lorenz, S. Mauser: Variants of the Language Based Synthesis Problem for Petri Nets. Submitted to 29th international conference on Application and Theory of Petri Nets (ICATPN), 2008.
- R. Bergenthum, J. Desel, R. Lorenz, S. Mauser: Synthesis of Petri Nets with Viptool. Submitted to 29th international conference on Application and Theory of Petri Nets (ICATPN), 2008.
- R. Bergenthum, J. Desel, R. Lorenz, S. Mauser: Synthesis of Petri Nets from Infinite Partial Languages. Submitted to 8th international conference on Application of Concurrency to system Design (ACSD), 2008.
- R. Bergenthum, J. Desel, G. Juhás, R. Lorenz, S. Mauser: Executability of Scenarios in Petri Nets. Submitted to Theoretical Computer Science.
- G. Juhás, R. Lorenz, S. Mauser: Complete Process Semantics of Petri Nets. Submitted to Fundamenta Informaticae.
- R. Lorenz, R. Bergenthum, J. Desel, S. Mauser: Synthesis of Petri nets from finite partial languages. Accepted for Fundamenta Informaticae (2009).
- G. Juhás, R. Lorenz, S. Mauser: Causal Semantics of Algebraic Petri Nets distinguishing Concurrency and Synchronicity. Accepted for Fundamenta Informaticae (2008).
2007
- R. Bergenthum, R. Lorenz, S. Mauser: Towards Applicability of Language Based Synthesis for Process Mining. 14th Workshop Algorithmen und Werkzeuge für Petrinetze (AWPN), Koblenz, 2007.
- R. Bergenthum, R. Lorenz, S. Mauser: Faster Unfolding of General Petri Nets. 14th Workshop Algorithmen und Werkzeuge für Petrinetze (AWPN), Koblenz, 2007.
- G. Juhás, R. Lorenz, S. Mauser: Complete process semantics for inhibitor nets. Proceedings of the 28th international conference on Application and Theory of Petri Nets (ICATPN), 2007.
- G. Juhás, F. Lehocki, R. Lorenz: Semantics of Petri Nets: A Comparison. Proceedings of the Wintersimulation Conference (WSC) 2007.
- R. Lorenz, G. Juhás: How to Synthesize Nets from Languages - a Survey. Proceedings of the Wintersimulation Conference (WSC) 2007, 2007.
- R. Bergenthum, J. Desel, R.Lorenz, S. Mauser: Process Mining based on regions of Languages. Proceedings of the 5th International Conference on Business Process Management (BPM) 2007, 2007.
- R.Lorenz, R. Bergenthum, S. Mauser: Theory of regions for the synthesis of inhibitor nets from scenarios. Proceedings of the 28th international conference on Application and Theory of Petri Nets (ICATPN), 2007.
- R.Lorenz, R. Bergenthum, S. Mauser: Testing the executability of scenarios in general inhibitor nets. Proceedings of the 7th international conference on Application of Concurrency to system Design (ACSD), 2007.
- R.Lorenz, R. Bergenthum, J. Desel, S. Mauser: Synthesis of Petri nets from finite partial languages. Proceedings of the 7th international conference on Application of Concurrency to system Design (ACSD), 2007.
Diplomarbeiten
nach oben
- B. Weixelbaum: Synthese von Petrinetzen aus partiellen Sprachen mit Methoden der linearen Programmierung, aktuell
- K. Mohr: Effizientes Process-Mining mit Hilfe Regionen-basierter Synthese-Methoden, aktuell
Tools
SYNOPS is our software tool which allows the term-based construction of partial languages and the synthesis of Petri nets from partial languages.
SYNOPS supports languages of labeled directed acyclic graphs (LDAGs), labeled partial orders (LPOs), labeled stratified directed acyclic graphs (LSDAGs) and labeled stratified order structures (LSOs) and implements our region based algorithms for the synthesis of place/transition nets and general inhibitor nets from such languages.The software still in a beta phase and is provided AS IS WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
Please use the tool in the moment only for runs with not too much concurrency, because the computation of all prefixes of a run is still not optimal.
If a run is closed, then all of its prefixes are computed as preparation of the synthesis algorithm and this may take some time and still needs too much space in case of much concurrency.
We are working to fix this problem.
There is a log-file _SYNOPS.log storing the sequence of commands sent by the user and messages sent by the program. If any problems occur, please send an email to Robert{.}Lorenz{at}informatik{.}uni-augsburg{.}de attaching this log-file.Downloads
We provide precompiled binaries for Win32 and Win64. The archives contain all libraries needed to run the program.
To start SYNOPS just run Synops.exe.
To start SYNOPS as a commandline tool simply run Synops.exe -gui:off.
Precompiled binaries for Linux and OS X are planned for future releases.
We also provide the example sets of runs we used to evaluate the tool.
nach oben
letzte Änderung am 13/02/2010 05:40:02 Robert Lorenz