A core component of AI-Augmented Business Process Management Systems (ABPMS) is framing which gives the system process-awareness and defines the boundaries in which the system must operate. When developing an ABPMS, framing can be created manually based on domain knowledge or automatically discovered from prior process executions. Existing process discovery approaches work well for the latter, assuming the individual processes can be identified and analyzed in isolation. However, this is not guaranteed if prior executions were recorded by a system that was not process-aware. In such cases, the bare minimum requirements for process discovery, namely ordered activity sequences grouped by a case identifier, may still be met. For example, treatment activities in a hospital can still be grouped by the patient identifier regardless of how many individual treatment processes (e.g., due to comorbidities) the patient underwent in the same time frame. In this paper, we present a process discovery approach for the above setting. Our focus is on discovering concurrently executed procedural processes, in the presence of shared activities, while the approach itself relies on interpreting declarative process discovery results.
A recent research manifesto on AI-Augmented Business Process Management Systems (ABPMS)
outlines a vision in which traditional BPMS lifecycle is augmented with AI technologies to
allow the system to “reason about the current state of the process (or across several processes) to
determine a course of action that improves the performance of the process” [
Despite the importance of framing, little indication of how it would be created for an ABPMS
is given in [
In general, event logs are only required to contain sequences of activity executions grouped
by case identifiers, where each unique case identifier is assumed to distinguish separate
executions of the same underlying process. For example, each treatment instance of a heart attack
(regardless of the variance between instances) is required to have a unique case identifier and
is assumed to be in an event log containing only instances of other a heart attack treatments.
We refer to the latter as the process uniqueness assumption, and it can be easily met if process
executions have been recorded by a Process-Aware Information System (PAIS) [
In this paper we present a process discovery approach that can handle separately defined processes being seemingly executed with the same case identifier, thus foregoing the process uniqueness assumption. Furthermore, this approach can handle semi-concurrent process executions (e.g., one process being paused to address an immediate concern in another process) and interdependencies between processes (e.g., one process requiring input from another process or a single activity progressing multiple processes simultaneously). The former means that we can no longer rely on directly-follows relations, which are the basis of most current process discovery algorithms, while the latter necessitates handling of synchronizations between otherwise separate processes. In contrast to existing approaches, the proposed approach first discovers a constraint-based declarative representation of the behavior in the given event log, which is then processed to provide a procedural model of the underlying processes and their interactions.
In the context of ABPMS, the proposed approach enables the automated discovery of (at least partial) framing based on past activity executions recorded by non-process-aware systems. While the discovery of the complete framing cannot be guaranteed from the past executions alone (e.g., some currently allowed behavior might not be executed in the past), the proposed approach should nevertheless be a valuable tool for the analysis and development of ABPMS.
In the remainder of this paper, Section 2 outlines our proposed approach and demonstrates its output in a multi-process setting. Section 3 provides a comparison to two existing process discovery approaches. Sections 4 and 5 highlight limitations and related works respectively. Finally, Section 6 concludes the paper by outlining directions for future work.
Our approach relies on two modeling languages, namely, Declare [
As the first step, we use Declare Miner [
Intuitively, Succession identifies potentially optional activities that always occur in the same order, Response identifies mandatory followers of potentially optional activities, and Precedence identifies prerequisite activities of potentially optional activities. Additionally, Not Co-Existence identifies mutually exclusive activities, Co-Existence without (Not) Succession identifies parallel activities, and Not Succession together with Co-Existence identifies any fixed activity orders.
All aforementioned relations are discovered between all pairs of activities assuming there is
at least one positive example and no counter examples for the given relation with the given
activity pair. Additionally, to simplify processing, an artificial start and end activity is added to
each execution trace, ensuring the discovery of at least one Response and one Precedence (or
Succession in case of a mandatory activity) per each activity. Finally, the discovered relations
are pruned [
Our approach uses four pairs of patterns, each of which corresponds to the manifestation of
some procedural behavior (e.g., sequence flow, choice, etc.) in the Declare modeling language.
All pairs are symmetric (similarly to Alpha Miner [
(b) Pattern 1b. parallelism (i.e., AND-split), while multiple Succession relations leading to the same activity are interpreted as the end of parallelism (i.e., AND-join).
Exclusive choice. Patterns 2a and 2b (Fig. 2) are used for mutually exclusive choices. The beginning of a mutually exclusive choice (i.e., XOR-split) is matched by pattern 2a, where the relations intuitively mean that B, C, ... can be executed only if A has occurred some time before (due to the Precedence relations), and at most one of B, C, ... can be chosen (due to Not Co-Existence relations). Meanwhile, pattern 2b matches the end of a mutually exclusive choice (i.e., XOR-join), with the intuition being that B, C, ... must be eventually followed by D (due to the Response relations). By default, both patterns add a silent transition into to the corresponding Petri net fragments to allow all of the mutually exclusive activities to be skipped. However, if the frequency of the mutually exclusive activities is equivalent to the frequency of A in pattern 2a or D in pattern 2b, then the silent transition is omitted.
Optional parallelism. Patterns 3a and 3b (Fig. 3) match a special case of parallelism where the entire parallel structure may be skipped. The intuitive meaning of Precedence and Response relations is the same as in patterns 2a and 2b, however, the Co-Existence relation (instead of Not Co-Existence) means that if any of B, C, ... is executed, then all of them must be executed. We note that, activity frequencies do not need to be considered here, since equivalent frequencies, would lead to Succession relations instead of Precedence and Response relations. Inclusive choice. Patterns 4a and 4b (Fig. 4) are used, efectively as fallback patterns, for cases where a single activity has multiple outgoing Precedence or incoming Response relations, but patterns 2a, 2b, 3a, and 3b do not apply. Intuitively, pattern 4a corresponds to the beginning of an inclusive choice (OR-split), while pattern 4b corresponds to the end of an inclusive choice (OR-split). In both patterns, the activities B, C, ... are placed in parallel together with an option to skip each individually, thus also allowing cases where none of B, C, ... are executed. (a) Pattern 3a.
(b) Pattern 3b.
The procedural behavior of a given event log can be reconstructed, given the eventually-follows relations from Section 2.1 and the patterns from Section 2.2. The basic idea is to begin with a Petri net containing only the artificial start (cf. Section 2.1) and then applying the patterns to it in a specific order. In doing so, additional transitions are added to the net, each of which will be processed in the same way, until one transition is created (and processed) per each activity. This results in a single Petri net representing the behavior of the underlying processes and the interactions between them. The corresponding procedure is summarized in Algorithm 1.
As an example, we use an event log containing the executions of Fig. 5(a) (with no violations and at least one occurrence of each activity). From this log, the Declare Miner will discover the relations presented in Fig. 5(b). To construct a corresponding procedural process model we start with an empty Petri net, into which we add a transition start with one input place. This leads to processing the relations of the activity start, which has only the relation Succession(start, A). Therefore, we can directly apply pattern 1a to add a transition A into the Petri net, together with a place that gets a token from transition start and provides it to transition A.
Next, we move to processing activity A. For this activity, we have multiple outgoing relations: • Succession(A, D) matches pattern 1a directly and would lead to correct placement of D in the Petri net; • Relations between A, C1, and C2 are a direct match to pattern 2a, but would lead an incorrect placement of the corresponding XOR-split directly after A. • Relations between A, B1, and B2 are a direct match to pattern 2a, but B2 is also in a Not
Co-Existence relation with B3, which also matches pattern 2a; We employ the following three additional rules to handle this situation:
Rule 1. If the outgoing relations of an activity match multiple patterns, then this is solved through parallelism. In the given example, A would get one output place providing a token for D (as per pattern 1a), and one additional output place per each application of pattern 4a. Furthermore, the patterns are considered in the order of 1a, 1b, 2a, 3a, 4a, 2b, 3b, 4b. The main purpose of this ordering is to apply more specific patterns first (for example, the Co-Existence relations in pattern 3a make it a more specific version of pattern 4a);
Rule 2. If there is any fixed order between outgoing or incoming activities, then only the relations to temporally “closest” activities are considered. In the given example, if any of B1, B2 or B3 occurs, then it must be before either C1 or C2 occurs. This is determined based the existence of Not Succession and Not Co-Existence between the pairs of activities. For example, the Declare Miner would find a relation Not Succession(C1, B1) (omitted from Fig. 5(b)) without ifnding relation Not Co-Existence(C1, B1). This indicates that B1 and C1 may occur in the same trace, and, if they do, then C1 must occur after B1. As a result, we can ignore outgoing relations to C1, and also to C2, while processing A, as both will transitively appear at some point after B1. An analogous comparison is later also required for the incoming activities of E;
Rule 3. If pattern 2a (or 2b) can be applied to sets of partially overlapping activities, then
pattern 2a (or 2b) will be applied once per each of these sets. This rule is necessary because of
the non-transitive nature of the Not Co-Existence relation, meaning that Not Co-Existence must
be observed between all pairs of activities to be placed after XOR-split (or before XOR-join).
Given Fig. 5(b), the pattern 2a could be applied to { A, B1, B2 } and { A, B2, B3 }, with B2 being
the overlapping activity. In this case, pattern 2a must be applied to both sets of activities, such
that A produces a token into a place providing it to B1 and B2 (first application of pattern 2a),
and A also produces a token into a place providing it to B2 and B3 (second application of pattern
2a). In more complex cases, this can be solved by finding all maximal Not Co-Existence cliques
among the activities (e.g., by using [
This leads to transitions B1, B2, B3, and D being added to the Petri net, all of which will be processed one by one based on the above rules and the corresponding patterns.
Finally, the Petri net ( ) returned by Algorithm 1 is post-processed to handle optional behavior. More specifically, all patterns, except for 1a and 1b, can produce silent transitions, which either do not have any output places (indicating the start of some optional behavior, i.e., skip start) or do not have any input places (indicating the end of some optional behavior, i.e., skip end). For each skip start, we first find all outgoing activities from places that may provide a token for that skip start. For each of these activities, we then find the outgoing Precedence relations. This indicates all the activities that must also be skipped if the given skip start transition is fired. Then, we do the same for each skip end while finding the incoming activities from all places into which the skip end produces a token. For each of these activities, we find the incoming Response relations, which gives a set of activities that must also be skipped if the given skip end transition is fired. Then, each skip start is merged with the skip end for which the sets of skipped activities are equivalent.
Algorithm 1 Petri net construction from activity relations. input : relations ℛ // as discovered in Section 2.1 output : Petri net 1 Θ := (1, 1, 2, 3, 4, 2, 3, 4) // see Section 2.2 and Rule 1 in Section 2.3 2 Σ := {start} // initialize Σ with the artificial activity ‘start’ 3 := {0 ∧ 0∙ = start} // initialize with place 0 and transition start 4 while Σ ̸= ∅ do 5 := ∈ Σ // choose random activity from Σ 76 ℛℛ ←:{=ℛ{ℛ||ℛ(ℛ )∋}//consider on}l/y/tsheeerreullaeti2onisncSoencttaiionnin2g.3 89 for each ∈:=Θ d(o, ℛ ) // instantiate pattern using and ℛ 10 Σ ← Σ ∪ {( ) ∖ ( )} // add activities not yet in to Σ 11 ← ∪ // extend (merging same-labeled transitions) 12 ℛ ← {ℛ |ℛ } // remove relations added to 13 14 15 16 end 17 ← { ∪ | ∙ = end} // add final place 18 return // Petri net of activity relations end Σ ← Σ ∪ {(ℛ ) ∖ ( )} // if any remaining relations refer to activities not in ( ) then add these activities to Σ Σ ← Σ ∖ // finished processing ( now in ( ))
Given the relations in Fig. 5(b), Algorithm 1 together with the rules outlined in in this section will precisely reconstruct the the Petri net shown in Fig. 5(a).
To demonstrate the result of Algorithm 1 in multi-process setting, we use a prototype implementation of our approach (publicly available at: https://github.com/antialman/multi-model-miner/).
For input we use [
The behavior of the discovered model is correct, and, furthermore, the individual input processes (Figs. 5(a) and 6(a)) are fairly well recognizable in the resulting model (Fig. 7), especially when ignoring the artificial start and end events (highlighted by number 1). In that case, the (a) Additional Petri net.
(b) Interplay refinement. two processes would only be connected by the transition C2 (highlighted by number 2), and the place 30 (highlighted by number 3). The transition C2 is correctly placed to represent that the corresponding activity is shared between the input processes. Meanwhile, place 30 represents the additional interplay refinement Response(C3, D) in Fig. 6(b).
With regards to the latter, it must be noted that there is a silent transition that is connected to place 30 and does not have any input places. This silent transition is caused by Response(C3, D) enforcing behavior which matches pattern 4b, without there being any corresponding match for pattern 4a (i.e., pattern 4b created a silent transition to end optional behavior, but no start for that optional behavior was created). As a result an unbounded number of tokens can be produced into place 30, which, while undesirable, does not enable any unintended behavior. Nevertheless, such cases of declarative behavior are something we plan to handle in the future.
In this section we demonstrate that contemporary process discovery approaches are likely to
give incorrect results in our setting, when considering shared activities and other relations
between processes. More specifically, we reuse the event log generated in Section 2.4 for
discovering process models with Flexible Heuristics Miner [
The model discovered by Flexible Heuristics Miner (Fig. 8) is relatively close in terms of the its behavior, but not in terms of structure. The overlapping XOR between B1, B2 and B3, while dificult to see, is captured correctly. The relation between activities C1, C2, and C3 is also identified; however, this results in the inability to execute, for example, both C3 and B1 without deadlocking the model. Furthermore, the interplay relation between C3 and D is not captured.
The Split Miner (Fig. 9) achieves better results, coming fairly close to the structure of the initial models. The overlapping XOR between B1, B2 and B3 is captured correctly and easy to see. Also, C3 does lead into D, thus accurately reflecting the corresponding interplay relation. However, this model has two main drawbacks. First, it is dificult to interpret the gateways and thus the behavior of the model. For example, the AND-splits after A and C3 seemingly lead to the same XOR-join. Secondly, the initial input models, while relatively accurately represented, are also relatively strongly intertwined, making it dificult to disentangle the individual processes.
We also note that, while not presented in this paper, both Flexible Heuristics Miner and Split Miner performed well when the individual processes did not have shared activities and there were no interplay refinements (such as Fig. 6(b)) between the processes. In these cases, the individual processes were discovered as parallel branches of a single larger process model.
The approach presented in this paper has some limitations we plan to tackle as future work. The most important among these are handling of repetitions and improving tolerance to noise.
Repetitions (i.e., self-loops, short-loops, long-loops) were not considered in this paper, however, we note that, almost all patterns presented in Section 2.2 be used within larger outer-loops with little to no adjustments. Furthermore, given that a loop can be viewed as a choice between executing an iteration or continuing beyond the loop, patterns 2a and 2b will match the entry and exit points of loops, respectively.
Our approach, as presented in this paper, is likely to be sensitive to noise in the event log. For
example, a single counter example to Succession(A, B) would lead to discovering Co-Existence(A,
B) instead. Here, we could consider adopting the causality measure of Heuristics Miner [
Finally, the approach could be simplified by using target-branched Declare discovery [
We are not aware of any approaches that explicitly address business process discovery in multi-process setting nor that forego the process uniqueness assumption.
However, a similar setting can be found in the context of local processes [
In relation to local processes, we also highlight region-based discovery techniques, which
use region theory for discovering characteristic regions that match the behavior seen in the
log. These regions, formulated as Petri nets, represent partial views of the behavior captured in
the log that are integrated to a complete process model [
There are also some parallels with multi-agent systems (MAS), where larger systems are
modeled through decentralized decision units referred to as agents. While the focus of MAS is
more on the behavioral rules of the agents rather than the related business processes, there is
some research on integrating MAS with process discovery techniques, e.g., the work in [
The combination of Petri nets and Declare is also used in some other hybrid process discovery
approaches, such as [
It is feasible that the approach presented in this paper, and the discovery of ABPMS framing
in general, could be further enhanced by leveraging additional domain knowledge. This idea
is underexplored thus far, but ontological domain knowledge has been leveraged in process
discovery to, for example, guide event abstraction [
Finally, we highlight that a core part of our approach is (partially) transforming (patterns of)
Declare constraints into Petri nets. A more general version of this transformation has already
been explored in the literature, with [
In this paper, we focused on the discovery of ABPMS framing in a multi-process setting. More specifically, we proposed a process discovery approach that can handle interleaved executions of multiple processes based on some shared identifier (e.g., patient id). This enables automated discovery of (at least partial) ABPMS framing based on the activity executions recorded in non-process-aware systems. The proposed approach makes it possible to discover the individual processes as well as the relations between them in a single model. While the approach currently has some limitations related to process repetitions and noise tolerance, we nevertheless believe it is a solid foundation for future works in the same direction, especially given that, in this paper, we rely only on the temporal orderings of activities in the given event log.
The next major extension of the work presented in this paper will be incorporating the core
ideas of the recently proposed multi-model paradigm for BPM [
In addition, we plan to explore the inclusion of domain knowledge and data perspective in our approach. This could be used to further guide the process discovery towards better separating the individual processes. For instance, knowing ontological relations between activities and which resources execute them may provide hints about the nature of the underlying processes. Finally, our approach would benefit from an empirical evaluation based on real-life datasets.
A. Alman was supported by the Estonian Research Council grant PRG1226. F.M. Maggi was supported by the UNIBZ project PRISMA.