Using automatic planning to find the most probable alignment: A history-based approach

  • Matheus P. Almeida USP
  • Karina V. Delgado USP
  • Sarajane M. Peres USP
  • Marcelo Fantinato USP


In many organizational contexts, the existence of a normative process model makes it possible to verify if the actual execution of activities of a business process conforms to that model. Non-conforming behavior can be detected by aligning the actions recorded in the event log with a related normative process model. The alignment approach uses a cost-function to build an execution path that shows which actions do not conform to the model, and which are the expected activities for that trace. In this paper, we are interested on finding the optimal probable alignment using a history-base cost-function, i.e. a function based on the process execution history. For that, we use as a base implementation the planning-based approach, previously proposed in the literature, which demonstrates to find large processes faster when compared to A* for standard cost-functions. We incorporate in this tool the automatic generation of an history-base cost-function to find an optimal probable alignment. In addition, we evaluated our approach using data from both synthetic event logs and a real-life event log.


Adriansyah, A., van Dongen, B. F., and van der Aalst, W. M. (2013). Memory-efficient alignment of observed and modeled behavior. Technical Report 3, BPM Center Report.

Aeronautiques, C., Howe, A., Knoblock, C., McDermott, I. D., Ram, A., Veloso, M., Weld, D., SRI, D. W., Barrett, A., et al. (1998). PDDL - the planning domain definition language. Technical Report CVC TR-98-003/DCS TR-1165, Yale Center for Computational Vision and Control.

Alizadeh, M., de Leoni, M., and Zannone, N. (2015). History-based construction of alignments for conformance checking: Formalization and implementation. In Data-Driven Process Discovery and Analysis, pages 58-78. Springer International Publishing.

Bloemen, V., van Zelst, S., van der Aalst, W., van Dongen, B., and van de Pol, J. (2022). Aligning observed and modelled behaviour by maximizing synchronous moves and using milestones. Information Systems, 103:101456.

Boltenhagen, M., Chatain, T., and Carmona, J. (2021). A discounted cost function for fast alignments of business processes. In Polyvyanyy, A., Wynn, M. T., Van Looy, A., and Reichert, M., editors, Business Process Management, pages 252-269. Springer International Publishing.

Burattin, A. (2015). PLG2: Multiperspective processes randomization and simulation for online and offline settings. preprint arXiv:1506.08415.

Dunzer, S., Stierle, M., Matzner, M., and Baier, S. (2019). Conformance checking: A state-of-the-art literature review. In 11th Int'l Conf on Subject-Oriented Business Process Management, pages 1-10.

Helmert, M. (2006). The fast downward planning system. J Artif Intell Res, 26:191-246.

Koorneef, M., Solti, A., Leopold, H., and Reijers, H. A. (2018). Automatic root cause identification using most probable alignments. 13th Int'l Workshop on Business Process Intelligence, pages 204-215.

Leoni, M., Lanciano, G., and Marrella, A. (2017). A tool for aligning event logs and prescriptive process models through automated planning. In BPM (Demos).

Leoni, M., Lanciano, G., and Marrella, A. (2018). Aligning partially-ordered process-execution traces and models using automated planning. Int'l Conf on Automated Planning and Scheduling, 28(1):321-329.

Leoni, M. and Marrella, A. (2017). Aligning real process executions and prescriptive process models through automated planning. Expert Syst Appl, 82:162-183.

Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. In Soviet Physics Doklady, volume 10, pages 707-710.

Mannhardt, F., Leoni, M., Reijers, H., and Aalst, W. V. D. (2016). Balanced multi-perspective checking of process conformance. Computing, 98(4):407-437.

Valk, R. and Vidal-Naquet, G. (1981). Petri nets and regular languages. Journal of Computer and System Sciences, 23(3):299-325.

Van der Aalst, W., Adriansyah, A., and van Dongen, B. (2012). Replaying history on process models for conformance checking and performance analysis. WIREs Data Mining and Knowl Discov, 2(2):182-192.

van der Aalst W. (2016). Process Mining - Data Science in Action. Springer.
ALMEIDA, Matheus P.; DELGADO, Karina V.; PERES, Sarajane M.; FANTINATO, Marcelo. Using automatic planning to find the most probable alignment: A history-based approach. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 19. , 2022, Campinas/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 234-245. ISSN 2763-9061. DOI:

Artigos mais lidos do(s) mesmo(s) autor(es)

1 2 > >>