Abstract
A process model discovered from an event log of a multi-agent system often does not fully cover certain viewpoints of its architecture. We consider those concerned with the structure of a model explicitly reflecting agent behavior and interactions. The direct discovery from an event log of a multi-agent system may result in an unclear model structure and over-generalizations of agent behavior. We suggest applying a compositional approach that yields architecture-aware process models of multi-agent systems. An event log of a multi-agent system is filtered by the behavior of individual agents. Then, a multi-agent system model is a composition of agent models discovered from filtered logs. We use an intermediate model, called an interface pattern, specifying agent interactions and representing the architecture of a multi-agent system. We design a collection of specific interface patterns modeling typical agent interactions. An interface pattern provides an abstract specification of interactions and has a part corresponding to the behavior of each agent. We use structural transformations to map agent models discovered from filtered logs on the respective parts in an interface pattern. If such a map** exists, we guarantee that a composition of agent models preserves their soundness. We conduct a series of experiments to evaluate the compositional approach. Experimental results confirm the improvement in the structure of process models discovered using the compositional approach compared to those discovered directly from event logs.
Similar content being viewed by others
References
van der Aalst, W.: Process Mining: Data Science in Action. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49851-4
Augusto, A., Conforti, R., Dumas, M., Rosa, M., Maggi, F., Marrella, A., Mecella, M., Soo, A.: Automated discovery of process models from event logs: review and benchmark. IEEE Trans. Knowl. Data Eng. 31(4), 686–705 (2019). https://doi.org/10.1109/TKDE.2018.2841877
Reisig, W.: Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-33278-4
Kalenkova, A., van der Aalst, W., Lomazova, I., Rubin, V.: Process mining using BPMN: relating event logs and process models. Softw. Syst. Model. 16, 1019–1048 (2017). https://doi.org/10.1007/s10270-015-0502-0
Carmona, J., van Dongen, B., Solti, A., Weidlich, M.: Conformance Checking: Relating Processes and Models. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99414-7
van der Aalst, W.: Workflow verification: finding control-flow errors using petri-net-based techniques. In: van der Aalst, W., Desel, J., Oberweis, A. (eds.) Business Process Management: Models, Techniques, and Empirical Studies. Lecture Notes in Computer Science, vol. 1806, pp. 161–183. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45594-9_11
van der Aalst, W., van Hee, K., ter Hofstede, A., Sidorova, N., Verbeek, H., Voorhoeve, M., Wynn, M.: Soundness of workflow nets: classification, decidability, and analysis. Form. Asp. Comput. 23, 333–363 (2011). https://doi.org/10.1007/s00165-010-0161-4
Barros, A., Dumas, M., ter Hofstede, A.: Service interaction patterns. In: van der Aalst, W., Benatallah, B., Casati, F., Curbera, F. (eds.) Business Process Management. Lecture Notes in Computer Science, vol. 3649, pp. 302–318. Springer, Heidelberg (2005). https://doi.org/10.1007/11538394_20
Bernardinello, L., Lomazova, I., Nesterov, R., Pomello, L.: Soundness-preserving composition of synchronously and asynchronously interacting workflow net components (2020). https://arxiv.org/pdf/2001.08064.pdf
Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional, Boston (1994)
van der Aalst, W., ter Hofstede, A., Kiepuszewski, B., Barros, A.: Workflow patterns. Distrib. Parallel Databases 14, 5–51 (2003). https://doi.org/10.1023/A:1022883727209
de Alfaro, L., Henzinger, T.: Interface-based design. In: Broy, M., Grünbauer, J., Harel, D., Hoare, T. (eds.) Engineering Theories of Software Intensive Systems, pp. 83–104. Springer, Dordrecht (2005). https://doi.org/10.1007/1-4020-3532-2_3
Leemans, S., Fahland, D., van der Aalst, W.: Discovering block-structured process models from event logs-a constructive approach. In: Colom, J., Desel, J. (eds.) Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science, vol. 7927, pp. 311–329. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38697-8_17
Bernardinello, L., Mangioni, E., Pomello, L.: Local state refinement and composition of elementary net systems: an approach based on morphisms. In: Koutny, M., van der Aalst, W., Yakovlev, A. (eds.) Transactions on Petri Nets and Other Models of Concurrency VIII. Lecture Notes in Computer Science, vol. 8100, pp. 48–70. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40465-8_3
Bernardinello, L., Lomazova, I., Nesterov, R., Pomello, L.: Property-preserving transformations of elementary net systems based on morphisms. In: Transactions on Petri Nets and Other Models of Concurrency XVI (ToPNoC). Springer (2022, to appear)
Nesterov, R., Mitsyuk, A., Lomazova, I.: Simulating behavior of multi-agent systems with acyclic interactions of agents. Proceed. Inst. Syst. Program. RAS 30(3), 285–302 (2018). https://doi.org/10.15514/ISPRAS-2018-30(3)-20
Buijs, J., van Dongen, B., van der Aalst, W.: On the role of fitness, precision, generalization and simplicity in process discovery. In: On the Move to Meaningful Internet Systems: OTM 2012. Lecture Notes in Computer Science, vol. 7565, pp. 305–322. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33606-5_19
Adriansyah, A.: Aligning observed and modeled behavior. Ph.D. thesis, Mathematics and Computer Science (2014). https://doi.org/10.6100/IR770080
van Dongen, B., de Medeiros, A., Verbeek, H., Weijters, A., van der Aalst, W.: The ProM framework: a new era in process mining tool support. In: Ciardo, G., Darondeau, P. (eds.) Applications and Theory of Petri Nets 2005. Lecture Notes in Computer Science, vol. 3536, pp. 444–454. Springer, Heidelberg (2005). https://doi.org/10.1007/11494744_25
Nesterov, R.: Compositional discovery of architecture-aware and sound process models from event logs of multi-agent systems: experimental data. (Version 1) [Data set]. Zenodo (2021). https://doi.org/10.5281/zenodo.5830863
Günther, C., van der Aalst, W.: Fuzzy mining - adaptive process simplification based on multi-perspective metrics. In: Alonso, G., Dadam, P., Rosemann, M. (eds.) Business Process Management. Lecture Notes in Computer Science, vol. 4714, pp. 328–343. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75183-0_24
Weijters, A., Ribeiro, J.: Flexible heuristics miner (FHM). In: 2011 IEEE Symposium on Computational Intelligence and Data Mining (CIDM), pp. 310–317. IEEE (2011). https://doi.org/10.1109/CIDM.2011.5949453
van der Werf, J., van Dongen, B., Hurkens, C., Serebrenik, A.: Process discovery using integer linear programming. Fundam. Inform. 94(3–4), 387–412 (2009). https://doi.org/10.3233/FI-2009-136
Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Process mining based on regions of languages. In: Alonso, G., Dadam, P., Rosemann, M. (eds.) Business Process Management. Lecture Notes in Computer Science, vol. 4714, pp. 375–383. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75183-0_27
van der Aalst, W., de Medeiros, A., Weijters, A.: Genetic process mining. In: Ciardo, G., Darondeau, P. (eds.) Applications and Theory of Petri Nets. Lecture Notes in Computer Science, vol. 3536, pp. 48–69. Springer, Heidelberg (2005). https://doi.org/10.1007/11494744_5
Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47967-4
Badouel, E., Darondeau, P.: Theory of regions. In: Reisig, W., Rozenberg, G. (eds.) Lectures on Petri Nets I: Basic Models: Advances in Petri Nets. Lecture Notes in Computer Science, vol. 1491, pp. 529–586. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-65306-6_22
van der Aalst, W.: Relating process models and event logs – 21 conformance propositions. In: Proceedings of the International Workshop on Algorithms and Theories for the Analysis of Event Data 2018, CEUR Workshop Proceedings, vol. 2115, pp. 56–74. CEUR-WS.org (2018)
van der Aalst, W., Gunther, C.: Finding structure in unstructured processes: The case for process mining. In: Seventh International Conference on Application of Concurrency to System Design (ACSD 2007), pp. 3–12. IEEE (2007). https://doi.org/10.1109/ACSD.2007.50
Buijs, J.: Flexible evolutionary algorithms for mining structured process models. Ph.D. thesis, Eindhoven University of Technology (2014)
De Smedt, J., De Weerdt, J., Vanthienen, J.: Multi-paradigm process mining: retrieving better models by combining rules and sequences. In: On the Move to Meaningful Internet Systems: OTM 2014 Conferences. Lecture Notes in Computer Science, vol. 8841, pp. 446–453. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45563-0_26
de San Pedro, J., Cortadella, J.: Mining structured petri nets for the visualization of process behavior. In: Proceedings of the 31st Annual ACM Symposium on Applied Computing, p. 839–846. ACM (2016). https://doi.org/10.1145/2851613.2851645
Kalenkova, A., Lomazova, I., van der Aalst, W.: Process model discovery: a method based on transition system decomposition. In: Ciardo, G., Kindler, E. (eds.) Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science, vol. 8489, pp. 71–90. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07734-5_5
Kalenkova, A., Lomazova, I.: Discovery of cancellation regions within process mining techniques. Fundam. Inform. 133, 197–209 (2014). https://doi.org/10.3233/FI-2014-1071
van der Aalst, W., Kalenkova, A., Rubin, V., Verbeek, E.: Process discovery using localized events. In: Devillers, R., Valmari, A. (eds.) Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science, vol. 9115, pp. 287–308. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19488-2_15
van der Aalst, W., Berti, A.: Discovering object-centric petri nets. Fundam. Inform. 175, 1–40 (2020). https://doi.org/10.3233/FI-2020-1946
Stierle, M., Zilke, S., Dunzer, S., Tenscher, J., Karagegova, G.: Design principles for comprehensible process discovery in process mining. In: ECIS 2020 Proceedings. Research Papers. AIS eLibrary (2020)
Best, E., Devillers, R., Koutny, M.: Petri Net Algebra. In: Brauer, W., Rozenberg, G., Salomaa, A. (eds.) Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2001). https://doi.org/10.1007/978-3-662-04457-5
Girault, C., Rüdiger, V.: Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-662-05324-9
de Alfaro, L., Henzinger, T.: Interface theories for component-based design. In: Henzinger, T., Kirsch, C. (eds.) Embedded Software. Lecture Notes in Computer Science, vol. 2211, pp. 148–165. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45449-7_11
Bednarczyk, M., Bernardinello, L., Caillaud, B., Pawłowski, W., Pomello, L.: Modular system development with pullbacks. In: van der Aalst, W., Best, E. (eds.) Applications and Theory of Petri Nets. Lecture Notes in Computer Science, vol. 2679, pp. 140–160. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-44919-1_12
Bernardinello, L., Monticelli, E., Pomello, L.: On preserving structural and behavioral properties by composing net systems on interfaces. Fundam. Inform. 80(1–3), 31–47 (2007)
Padberg, J., Urbášek, M.: Rule-based refinement of petri nets: a survey. In: Ehrig, H., Reisig, W., Rozenberg, G., Weber, H. (eds.) Petri Net Technology for Communication-Based Systems: Advances in Petri Nets. Lecture Notes in Computer Science, vol. 2472, pp. 161–196. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40022-6_9
Winskel, G.: Petri nets, algebras, morphisms, and compositionality. Inform. Comput. 72(3), 197–238 (1987). https://doi.org/10.1016/0890-5401(87)90032-0
Decker, G., Barros, A.: Interaction modeling using BPMN. In: ter Hofstede, A., Benatallah, B., Paik, H.Y. (eds.) Business Process Management Workshops. Lecture Notes in Computer Science, vol. 4928, pp. 208–219. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78238-4_22
Campagna, D., Kavka, C., Onesti, L.: BPMN 2.0 and the service interaction patterns: can we support them all? In: Software Technologies. Communications in Computer and Information Science, vol. 555, pp. 3–20. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25579-8_1
Decker, G., Puhlmann, F., Weske, M.: Formalizing service interactions. In: Dustdar, S., Fiadeiro, J.L., Sheth, A.P. (eds.) Business Process Management. Lecture Notes in Computer Science, vol. 4102, pp. 414–419. Springer, Heidelberg (2006). https://doi.org/10.1007/11841760_32
van der Aalst, W., Mooij, A., Stahl, C., Wolf, K.: Service interaction: patterns, formalization, and analysis. In: Bernardo, M., Padovani, L., Zavattaro, G. (eds.) SFM 2009: Formal Methods for Web Services. Lecture Notes in Computer Science, vol. 5569, pp. 42–88. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01918-0_2
Bernardinello, L., Lomazova, I., Nesterov, R., Pomello, L.: Compositional discovery of workflow nets from event logs using morphisms. In: Proceedings of the International Workshop on Algorithms and Theories for the Analysis of Event Data 2018, CEUR Workshop Proceedings, vol. 2115, pp. 23–38. CEUR-WS.org (2018)
Nesterov, R., Lomazova, I.: Asynchronous interaction patterns for mining multi-agent system models from event logs. In: Proceedings of the MACSPro Workshop 2019, CEUR Workshop Proceedings, vol. 2478, pp. 62–73. CEUR-WS.org (2019)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Tony Clark.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work is supported by MIUR, Italy and the Basic Research Program at HSE University, Russia.
Rights and permissions
About this article
Cite this article
Nesterov, R., Bernardinello, L., Lomazova, I. et al. Discovering architecture-aware and sound process models of multi-agent systems: a compositional approach. Softw Syst Model 22, 351–375 (2023). https://doi.org/10.1007/s10270-022-01008-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10270-022-01008-x