Efficient Conformance Checking on Process Trees using A*

 

BSc Thesis Project

Title: Efficient Conformance Checking on Process Trees using A*

Author: Ralf Riesen

1st examiner: Prof. Dr. Wil M.P. van der Aalst

2nd examiner: Prof. Dr. rer. nat. Peter Rossmanith

Daily supervisor: Dr. Sebastiaan J. van Zelst

Summary

Businesses trying to improve their product output need to understand the underlying processes of their product. Process Mining helps businesses to discover and enhance their processes. Process Mining deals with creating process models from collected data of an arbitrary process. These discovered process models have to be validated. An important part of Process Mining is conformance checking. This thesis is concerned with checking the correctness of a process. Currently, conformance checking is mainly applied on Petri nets. However, processes modeled with Petri nets can struggle with anomalies like deadlocks and livelocks. A process model that is per design not affected by deadlocks is a process tree. This thesis deals with applying conformance checking directly on process trees. Computing alignments with a brute force approach for conformance checking is expensive. A more elegant and faster solution approach is the search algorithm A*. We apply A* on the alignment state space of the process tree and the trace to search efficiently for optimal alignments. The algorithm will be implemented in PM4Py, a process mining library for Python, and evaluated with synthetic data sets.