Discovering Process Models from Event Logs of Multi-Agent Systems Using Event Relations
https://doi.org/10.15514/ISPRAS-2023-35(3)-1
Abstract
The structure of a process model directly discovered from an event log of a multi-agent system often does not reflect the behavior of individual agents and their interactions. We suggest analyzing the relations between events in an event log to localize actions executed by different agents and involved in their asynchronous interaction. Then, a process model of a multi-agent system is composed from individual agent models between which we add channels to model the asynchronous message exchange. We consider agent interaction within the acyclic and cyclic behavior of different agents. We develop an algorithm that supports the analysis of event relations between different interacting agents and study its correctness. Experimental results demonstrate the overall improvement in the quality of process models discovered by the proposed approach in comparison to monolithic models discovered directly from event logs of multiagent systems.
Keywords
Multi-agent systems,
event logs,
process discovery,
Petri nets,
event relations,
asynchronous interaction.This work is supported by the Basic Research Program at the HSE University, Russia.
Supporting agencies: This work is supported by the Basic Research Program at the HSE University, Russia.
About the Authors
Anastasiya SHERSTYUGINA
HSE University
Russian Federation
Russian Federation
Bachelor student at the faculty of computer science in HSE University, a research assistant at the Laboratory for Process-Aware Information Systems (PAIS Lab), HSE University.
Roman NESTEROV
HSE University
Russian Federation
Russian Federation
Senior lecturer at the faculty of computer science in HSE University, junior researcher at the PAIS Lab, HSE University.
References
1. W. van der Aalst. Process Mining: Data Science in Action. Springer, Heidelberg, 2016. DOI: 10.1007/978-3-662-49851-4.
2. W. Reisig. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies. Springer, Heidelberg, 2013. DOI: 10.1007/978-3-642-33278-4.
3. W. van der Aalst and A. Berti. Discovering Object-Centric Petri Nets. Fundamenta Informaticae, vol. 175, pp. 1–40, 2020. DOI: 10.3233/FI-2020-1946.
4. A. Begicheva and I. Lomazova. Discovering High-Level Process Models from Event Logs. Modeling and Analysis of Information Systems, vol. 24, no. 2, pp. 125–140, 2017. DOI: 10.18255/1818-1015-2017-2-125-140.
5. C. Li, S. van Zelst, and W. van der Aalst. An Activity Instance Based Hierarchical Framework for Event Abstraction. In 2021 3rd International Conference on Process Mining (ICPM), 2021, pp. 160–167. DOI: 10.1109/ICPM53251.2021.9576868.
6. R. Nesterov, L. Bernardinello, I. Lomazova, and L. Pomello. Discovering architecture-aware and sound process models of multi-agent systems: a compositional approach. Software & Systems Modeling, vol. 22, pp. 351–375, 2023. DOI: 10.1007/s10270-022-01008-x.
7. A. Augusto, R. Conforti, M. Dumas, M. Rosa, F. Maggi, A. Marrella, M. Mecella, and A. Soo. Automated Discovery of Process Models from Event Logs: Review and Benchmark. IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 4, pp. 686–705, 2019. DOI: 10.1109/TKDE.2018.2841877.
8. J. Carmona, B. van Dongen, A. Solti, and M. Weidlich, Conformance Checking: Relating Processes and Models. Springer, Cham, 2018. DOI: 10.1007/978-3-319-99414-7.
9. W. van der Aalst. Workflow Verification: Finding Control-Flow Errors Using Petri-Net-Based Techniques. In Business Process Management: Models, Techniques, and Empirical Studies. Lecture Notes in Computer Science, vol. 1806. Springer, Heidelberg, 2000, pp. 161–183. DOI: 10.1007/3-540-45594-9_11.
10. S. Leemans, D. Fahland, and W. van der Aalst. Discovering Block-Structured Process Models from Event Logs – A Constructive Approach. In Application and Theory of Petri Nets and Concurrency (PETRI NETS 2013). Lecture Notes in Computer Science, vol. 7927. Springer, Heidelberg, 2013, pp. 311–329. DOI: 10.1007/978-3-642-38697-8_17.
11. R. Nesterov, “Compositional discovery of architecture-aware and sound process models of multi-agent systems: experimental: data experimental data. (version 1) [data set].” [Online]. Available: https://doi.org/10.5281/zenodo.5830863.
12. A. Barros, M. Dumas, and A. ter Hofstede. Service Interaction Patterns. In Business Process Management (BPM 2005). Lecture Notes in Computer Science, vol. 3649. Springer, Heidelberg, 2005, pp. 302–318. DOI: 10.1007/11538394_20.
13. J. Munoz-Gama and J. Carmona. A Fresh Look at Precision in Process Conformance. In Business Process Management (BPM 2010). Lecture Notes in Computer Science, vol. 6336. Springer Heidelberg, 2010, pp. 211–226. DOI: 10.1007/978-3-642-15618-2_16.
14. “ProM Tools,” [Online]. Available: https://www.promtools.org/doku.php.
15. C. Gunther and W. van der Aalst. Fuzzy Mining – Adaptive Process Simplification Based on Multi-Perspective Metrics. In Business Process Management (BPM 2007). Lecture Notes in Computer Science, vol. 4714. Springer, Heidelberg, 2007, pp. 328–343. DOI: 10.1007/978-3-540-75183-0_24.
16. R. Bergenthum, J. Desel, R. Lorenz, and S. Mauser. Process Mining Based on Regions of Languages. In Business Process Management (BPM 2007). Lecture Notes in Computer Science, vol. 4714. Springer, Heidelberg, 2007, pp. 375–383. DOI: 10.1007/978-3-540-75183-0_27.
17. W. van der Aalst, A. de Medeiros, and A. Weijters. Genetic Process Mining. In Applications and Theory of Petri Nets (ICATPN 2005). Lecture Notes in Computer Science, vol. 3536. Springer, Heidelberg, 2005, pp. 48–69. DOI: 10.1007/11494744_5.
18. W. van der Aalst. Relating Process Models and Event Logs – 21 Conformance Propositions. In Proceedings of the International Workshop ATAED-2018. CEUR Workshop Proceedings, vol. 2115. CEURWS.org, 2018, pp. 56–74.
19. A. Kalenkova, I. Lomazova, and W. van der Aalst. Process model discovery: A method based on transition system decomposition. In Application and Theory of Petri Nets and Concurrency (PETRI NETS 2014). Lecture Notes in Computer Science, vol. 8489. Springer, Cham, 2014, pp. 71–90. DOI: 10.1007/978-3-319-07734-5_5.
20. A. Kalenkova and I. Lomazova. Discovery Of Cancellation Regions Within Process Mining Techniques. Fundamenta Informaticae, vol. 133, pp. 197–209, 2014. DOI: 10.3233/FI-2014-1071.
21. W. van der Aalst, A. Kalenkova, V. Rubin, and E. Verbeek. Process Discovery Using Localized Events. In Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science, vol. 9115. Springer, Cham, 2015, pp. 287–308. DOI: 10.1007/978-3-319-19488-2_15.
22. E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional, 1994.
23. W. van der Aalst, A. ter Hofstede, B. Kiepuszewski, and A. Barros. Workflow Patterns. Distributed and Parallel Databases, vol. 14, pp. 5–51, 2003. DOI: 10.1023/A:1022883727209.
24. D. Campagna, C. Kavka, and L. Onesti. BPMN 2.0 And The Service Interaction Patterns: Can We Support Them All? In Software Technologies (ICSOFT 2014). Communications in Computer and Information Science, vol. 555. Springer, Cham, 2015, pp. 3–20. DOI: 10.1007/978-3-319-25579-8_1.
25. S. Suriadi, R. Andrews, A. ter Hofstede, and M. Wynn. Event logs imperfection patterns for process mining: towards a systematic approach to cleaning event logs. Information Systems, vol. 34, pp. 132–150, 2017. DOI: 10.1016/j.is.2016.07.011.
26. M. Acheli, D. Grigori, and M. Weidlich. Discovering and Analyzing Contextual Behavioral Patterns from Event Logs. IEEE Transactions on Knowledge and Data Engineering, vol. 34, no. 12, pp. 5708–5721, 2022. DOI: 10.1109/TKDE.2021.3077653.
27. W. van der Aalst, T. Weijters, and L. Maruster. Workflow mining: discovering process models from event logs. IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1128–1142, 2004. DOI: 10.1109/TKDE.2004.47.
28. K. Artamonov and I. Lomazova. What Has Remained Unchanged in Your Business Process Model? In 2019 IEEE 21st Conference on Business Informatics (CBI), 2019, pp. 551¬–558. DOI: 10.1109/CBI.2019.00070.
Review
For citations:
SHERSTYUGINA A., NESTEROV R. Discovering Process Models from Event Logs of Multi-Agent Systems Using Event Relations. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2023;35(3):11-32. https://doi.org/10.15514/ISPRAS-2023-35(3)-1
Email this article 