Анализ структурной сложности сетей потоков работ для моделирования асинхронного взаимодействия агентов

Структура модели процесса, полученной на основе журнала событий многoагентной системы, часто не отражает архитектуру системы с точки зрения взаимодействий между агентами. Существующие метрики проверки соответствия в основном оценивают степень соответствия поведения обнаруженной модели последовательностям событий, зафиксированным в журнале. Однако такие поведенческие метрики могут оказаться недостаточными для того, чтобы отличить модели процессов, извлеченные из журнала одной и той же многoагентной системы, с учетом степени независимости агентов и сложности их взаимодействий. В данной работе предлагается теоретически обоснованный подход к измерению структурной сложности модели процесса, представляющей многoагентную систему с асинхронным взаимодействием агентов. Также представлены ключевые результаты серии экспериментов, направленных на оценку чувствительности предложенного подхода к структурным изменениям в моделях процессов.

1. W. van der Aalst, Process Mining: Data Science in Action. Springer Heidelberg, 2016. URL: https://link.springer.com/book/10.1007/978-3-662-49851-4.

2. A. Augusto, R. Conforti, M. Dumas, M. L. Rosa, F. M. 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. URL: https://ieeexplore.ieee.org/document/8368306.

3. W. Reisig, Understanding Petri nets. Modeling techniques, analysis methods, case studies. Springer Heidelberg, 2013. URL: https://link.springer.com/book/10.1007/978-3-642-33278-4.

4. A. Kalenkova, A. Burattin, and M. a. de Leoni, Discovering high-level BPMN process models from event data, Business Process Management Journal, vol. 25, pp. 995–1019, 2019. URL: https://www.emerald.com/bpmj/article/25/5/995/256745/Discovering-high-level-BPMN-process-models-from.

5. J. Carmona, B. van Dongen, A. Solti, and M. Weidlich, Conformance Checking: Relating Processes and Models. Springer Heidelberg, 2018. URL: https://link.springer.com/book/10.1007/978-3-319-99414-7.

6. A. Adriansyah, J. Munoz-Gama, J. Carmona, B. van Dongen, and W. van der Aalst, Alignment based precision checking, in Business Process Management Workshops, ser. LNBIP, vol. 132. Springer Heidelberg, 2013, pp. 137–149. URL: https://link.springer.com/chapter/10.1007/978-3-642-36285-9_15.

7. S. Leemans, D. Fahland, and W. van der Aalst, Discovering block- structured process models from event logs – a constructive approach, in PETRI NETS, ser. LNCS, J. Colom and J. Desel, Eds., vol. 7927. Springer Heidelberg, 2013, pp. 311–329.

8. URL: https://link.springer.com/chapter/10.1007/978-3-642-38697-8_17.

9. W. M. van der Aalst, Relating process models and event logs – 21 conformance propositions, in ATAED@Petri Nets/ACSD, 2018. [Online]. URL: https://api.semanticscholar.org/CorpusID:49303433

10. W. van der Aalst, Workflow verification: Finding control-flow errors using petri-net-based techniques, in Business Process Management: Models, Techniques, and Empirical Studies, ser. LNCS, vol. 1806. Springer, Heidelberg, 2000, pp. 161–183.

11. URL: https://link.springer.com/chapter/10.1007/3-540-45594-9_11.

12. L. Bernardinello, I. Lomazova, R. Nesterov, and P. L., Soundness-preserving composition of synchronously and asynchronously interacting workflow net components, Journal of Parallel and Distributed Computing, vol. 179, Article 104704, 2023. URL: https://www.sciencedirect.com/science/article/pii/S0743731523000679.

13. R. Nesterov, L. Bernardinello, I. Lomazova, and P. L., Discovering architecture-aware and sound process models of multi-agent systems: a compositional approach, Software and Systems Modeling, vol. 22, pp. 351–375, 2023. URL: https://link.springer.com/article/10.1007/s10270-022-01008-x.

14. L. Bernardinello, E. Mangioni, and L. Pomello, Local state refinement and composition of elementary net systems: An approach based on morphisms, in Transactions on Petri Nets and Other Models of Concurrency VIII, ser. LNCS, vol. 8100. Springer, Heidelberg, 2013, pp. 48–70. URL: https://link.springer.com/chapter/10.1007/978-3-642-40465-8_3.

15. E. Zemlyanoy, Structural complexity of workflow nets [Online]. URL: https://github.com/egorz734/ structural-complexity-of-workflow-nets.

16. C. Gunther and W. van der Aalst, Fuzzy mining – adaptive process simplification based on multi-perspective metrics, in Business Process Management, ser. LNCS, G. Alonso, P. Dadam, and M. Rosemann, Eds., vol. 4714. Springer Heidelberg, 2007, pp. 328–343. URL: https://link.springer.com/chapter/10.1007/978-3-540-75183-0_24.

17. J. van der Werf, B. van Dongen, C. Hurkens, and A. Serebrenik, Process discovery using integer linear programming, in PETRI NETS, ser. LNCS, K. van Hee and R. Valk, Eds., vol. 5062. Springer Heidelberg, 2008, pp. 368–387. URL: https://link.springer.com/chapter/10.1007/978-3-540-68746-7_24.

18. T. McCabe, A complexity measure, IEEE Transactions on Software Engineering, vol. SE-2, no. 4, pp. 308-320, 1976. URL: https://ieeexplore.ieee.org/document/1702388.

19. L. Gang Soo and Y. Jung-Mo, An empirical study on complexity metrics of petri nets, Microelectronics Reliability, vol. 32, no. 9, pp. 1215–1221, 1992. URL: https://www.sciencedirect.com/science/article/pii/002627149290061O.

20. A. Kalenkova, A. Lomazova, and W. van der Aalst, Process model discovery: A method based on transition system decomposition, in PETRI NETS, ser. LNCS, G. Ciardo and E. Kindler, Eds., vol. 8489. Springer Heidelberg, 2014, pp. 71–90.

21. URL: https://link.springer.com/chapter/10.1007/978-3-319-07734-5_5.

22. A. Kalenkova and I. Lomazova, Discovery of cancellation regions within process mining techniques, Fundamenta Informaticae, vol. 133, pp. 197–209, 2014. URL: https://journals.sagepub.com/doi/abs/10.3233/FI-2014-1071.

23. W. van der Aalst, A. Kalenkova, V. Rubin, and E. Verbeek, Process discovery using localized events, in PETRI NETS, ser. LNCS, R. Devillers and A. Valmari, Eds., vol. 9115. Springer Heidelberg, 2015, pp. 287–308. URL: https://link.springer.com/chapter/10.1007/978-3-319-19488-2_15.

24. A. Begicheva, I. Lomazova, and R. Nesterov, Discovering hierarchical process models: an approach based on events partitioning, Modeling and Analysis of Information Systems, vol. 31, no. 3, pp. 294–315, 2024. URL: https://www.mais-journal.ru/jour/article/view/1879.

25. 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. URL: https://www.mais-journal.ru/jour/article/view/504.

26. W. van der Aalst and A. Berti, Discovering object-centric petri nets, Fundamenta Informaticae, vol. 175, pp. 1–40, 2020. URL: https://journals.sagepub.com/doi/10.3233/FI-2020-1946.