Published by De Gruyter (O) February 5, 2022

Learning Petri net models from sensor data of conveying systems based on the merging of prefix and postfix trees

Lernen von Petri-Netzen aus den Sensordaten industrieller Transportsysteme durch das Mergen von Prefix- und Postfix-Trees

Stefan Windmann

Stefan Windmann received the Dipl.-Ing. and Dipl.-Inf. degrees in electrical engineering and technical computer sciences from University of Paderborn, Germany, in 2004, where he received the Ph.D. degree in electrical engineering in 2008. He is currently employed as senior scientist at Fraunhofer IOSB-INA in Lemgo, Germany. His current research interests include machine learning algorithms and methods for diagnosis and optimization of automated production systems.

From the journal at - Automatisierungstechnik

https://doi.org/10.1515/auto-2021-0101

Showing a limited preview of this publication:

Abstract

Petri nets are a common modeling approach for parallel processes such as transport operations in conveying systems. In industrial applications, the Petri net models are usually created manually, which involves a lot of effort, especially if the modeled systems change frequently. This paper introduces a new learning method to automatically generate Petri nets from sensor data acquired in conveying systems. The underlying approach is to create prefix and postfix trees of possible event sequences and to merge them into a compact graph, which can be transformed into a deterministic Petri net model of the conveying system. Experimental results show that the proposed method produces realistic Petri net models even for conveying systems with ambiguous events.

Zusammenfassung

Petri-Netze sind ein gängiger Modellierungs-Ansatz für parallele Prozesse wie z. B. Transportvorgänge in Fördersystemen. In industriellen Anwendungen werden die verwendeten Petri-Netz-Modelle in der Regel manuell erstellt, was mit hohem Engineering-Aufwand verbunden ist, insbesondere wenn sich die modellierten Systeme häufig ändern. In diesem Beitrag wird eine neue Lernmethode zur automatischen Erzeugung von Petri-Netzen aus Sensordaten vorgestellt. In dem vorgeschlagenen Ansatz werden Prefix- und Postfix-Trees möglicher Ereignisfolgen generiert und zu einem kompakten Graphen verschmolzen, welcher in ein deterministisches Petri-Netz-Modell des Transportsystems transformiert werden kann. Experimentelle Ergebnisse zeigen, dass die vorgeschlagene Methode auch für Fördersysteme mit mehrdeutigen Ereignissen realitätsnahe Petri-Netz-Modelle erzeugt.

Keywords: conveying systems; Petri net; model learning

Schlagwörter: industrielle Transportsysteme; Petri Netze; Modell-Lernen

About the author

Stefan Windmann

Stefan Windmann received the Dipl.-Ing. and Dipl.-Inf. degrees in electrical engineering and technical computer sciences from University of Paderborn, Germany, in 2004, where he received the Ph.D. degree in electrical engineering in 2008. He is currently employed as senior scientist at Fraunhofer IOSB-INA in Lemgo, Germany. His current research interests include machine learning algorithms and methods for diagnosis and optimization of automated production systems.

AppendixMerge operations

Fig. 9 illustrates the effects of merge operations.

Before merging two nodes v 1 and v 2 of a graph G, event sequences independently pass through these nodes, which are denoted by

(20) E = { ( e 1 − , e 1 + ) | e 1 − ∈ E 1 − , e 1 + ∈ E 1 + } ∪ { ( e 2 − , e 2 + ) | e 2 − ∈ E 2 − , e 2 + ∈ E 2 + } ,

where E i ( − ) , i ∈ { 1 , 2 } is the set of event sequences e i − that lead from the root node v 0 of G to the node v i , and E i + , i ∈ { 1 , 2 } is the set of event sequences e i + that lead from the node v i to a final node v f ∈ { V f }. After merging v 1 and v 2 , the event sequences

(21) E ′ = { ( e 1 − , e 1 + ) | e 1 − ∈ E 1 − , e 1 + ∈ E 1 + } ∪ { ( e 2 − , e 2 + ) | e 2 − ∈ E 2 − , e 2 + ∈ E 2 + } ∪ { ( e 1 − , e 2 + ) | e 1 − ∈ E 1 − , e 2 + ∈ E 2 + } ∪ { ( e 2 − , e 1 + ) | e 2 − ∈ E 2 − , e 1 + ∈ E 1 + }

are contained in the graph, which include the new combinations in line 3 and 4 of (21). Generally, the condition E ⊆ E ′ fulfilled, i. e., with each merge operation the event sequences represented by the graph either remain unchanged or new event sequences are added. For E 1 − = E 2 − or E 1 + = E 2 + , the equality E = E ′ holds, i. e., the merging does not result in new event sequences. This is exploited in the learning procedures for the prefix tree and the postfix tree, where only nodes with E 1 − = E 2 − resp. E 1 + = E 2 + are merged.

$Figure 9 Nodes v 1 {v_{1}} and v 2 {v_{2}} before the merging operation.$

Figure 9

Nodes v 1 and v 2 before the merging operation.

References

1. Carrasco, R.C. and J. Oncina. 1994. Learning stochastic regular grammars by means of a state merging method. In: Grammatical Inference and applications. Springer, Berlin, Heidelberg, pp. 139–152.10.1007/3-540-58473-0_144Search in Google Scholar

2. Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301): 13–30.10.1080/01621459.1963.10500830Search in Google Scholar

3. Klein, S., L. Litz and J.-J. Lesage. 2005. Fault detection of discrete event systems using an identification approach. In: 16th IFAC world congress.10.3182/20050703-6-CZ-1902.01440Search in Google Scholar

4. Ladiges, J., A. Fuelber, E. Arroyo, A. Fay, C. Haubeck and W. Lamersdorf. 2015. Learning material flow models for manufacturing plants from data traces. In: 2015 IEEE 13th International Conference on Industrial Informatics (INDIN), pp. 294–301.10.1109/INDIN.2015.7281750Search in Google Scholar

5. Maier, A. 2014. Online passive learning of timed automata for cyber-physical production systems. In: 12th IEEE International Conference on Industrial Informatics (INDIN). Porto Alegre, Brazil.10.1109/INDIN.2014.6945484Search in Google Scholar

6. Meda-Campana, M.E. and S. Medina-Vazquez. 2011. Synthesis of timed petri net models for on-line identification of discrete event systems. In: 2011 9th IEEE International Conference on Control and Automation (ICCA), pp. 1201–1206.10.1109/ICCA.2011.6137968Search in Google Scholar

7. Niggemann, O., B. Stein, A. Vodenčarević, A. Maier and H.K. Büning. 2012. Learning behavior models for hybrid timed systems. In: Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), Toronto, Ontario, Canada, pp. 1083–1090.Search in Google Scholar

8. Pandalai, D.N. and L.E. Holloway. 2000. Template languages for fault monitoring of timed discrete event processes. IEEE Trans. Autom. Control 45(5): 868–882.10.1109/9.855548Search in Google Scholar

9. Thollard, F., P. Dupont and C. de la Higuera. 2000. Probabilistic DFA inference using Kullback-Leibler divergence and minimality. In: Proc. of the 17th International Conf. on Machine Learning, pp. 975–982. Morgan Kaufmann.Search in Google Scholar

10. Verwer, S. 2010. Efficient identification of timed automata: theory and practice. PhD thesis, Delft University of Technology.Search in Google Scholar

11. Vogel-Heuser, B., C. Diedrich, A. Fay, S. Jeschke, S. Kowalewski, M. Wollschlaeger and P. Goehner. 2014. Challenges for software engineering in automation. JSEA 7(5): 440–451.10.4236/jsea.2014.75041Search in Google Scholar

12. Windmann, S., D. Lang and O. Niggemann. 2017. Learning parallel automata of plcs. In: 2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), pp. 1–7.Search in Google Scholar

Received: 2021-07-14

Accepted: 2021-11-03

Published Online: 2022-02-05

Published in Print: 2022-02-23