Process models discovered from event logs of multi-agent systems may be complicated and unreadable. To overcome this problem, we suggest using a compositional approach. A system model is composed from agent models w.r.t. an interface. Morphisms guarantee that composition of correct models is correct. This study contributes to the practical implementation of the morphism-based compositional approach. We use interaction patterns to model typical interfaces. Experimental evaluation justifies the practical value of the compositional approach.
To overcome this problem, we suggest using a compositional approach to discover a MAS process model clearly indicating agents as subnets and their interactions through channels. Assume that we know in advance how channels are exploited (sending/receiving messages) by agents. The compositional process discovery is straightforward. Firstly, we discover process models of agents from filtered event logs. Then agent models are composed via channels. Consider the Petri net shown in Fig. 1(b). It can reproduce event sequences from the same event log as the model from Fig. 1(a). What is more important, this model explicitly indicates the agent behavior (left and right subnet) and the channels (gray nodes) used for interaction. t1 t2
s1
t3 t4
Petri net composition has been extensively studied in the literature (e.g. in
[
In [
However, the practical implementation of this approach may require extensive
theoretical knowledge. Our work contributes to solving this problem in practice
by applying service interaction patterns (SIPs). They have been described in
[
In this study, we identify typical patterns describing asynchronous
interaction on the basis of related research analysis. Patterns model agent interaction
protocols at the abstract level. Following the approach proposed in [
Another view on the problem of discovering interactions from event logs has
been discussed in [
The remainder of the paper is organized as follows. The next section provides an informal description of service interaction patterns. Section 3 recalls necessary notions from Petri net theory. Section 4 describes an approach to modeling and refining abstract service interaction patterns. In Section 5, we show experimental results on using patterns for mining MAS models from event logs. Section 6 concludes the paper by discussing results and possible continuations. 2
Service interaction patterns provide a systematic approach to address the
problem of organizing complex and large-scale interactions. They have been used in
different contexts. Among the others, in [
Service interaction patterns are classified according to the number of
interacting entities: (a) bilateral (two) and (b) multilateral (more than two). Also,
service interaction patterns are classified w.r.t. the way entities interact: (a)
single transmission patterns and (b) multiple transmission patterns [
In our work, we study bilateral patterns with both single and multiple transmissions. Table 1 provides a brief informal description of patterns considered in the paper. Short IDs are used to refer to these patterns in the text. Note that patterns SIP-1, SIP-2 and SIP-3 describe rather primitive interaction, since an agent sending a message is not supposed to get a response from another agent. More sophisticated communications are given in patterns SIP-4, SIP-5, SIP-6, when two agents actually exchange messages in different ways. SIP-7 is a multiple transmission pattern, where one agent decides to stop exchanging messages.
The aim of our work is to apply these patterns for compositional discovery of formal multi-agent system models from event logs. That is why, we show how to model these patterns using Petri nets in Section 4. Each pattern corresponds to a specification of a protocol according to which agents agree to communicate. Moreover, these patterns contains only abstract information on agent interaction providing minimal information on an internal agent behavior. We also describe
An agent X sends (receives) a message to (from) an agent Y.
An agent X concurrently sends (receives) several messages (>1) to (from) an agent Y.
An agent X sends (receives) exactly one out of two (or more) alternative message sets to (from) an agent Y.
An agent X sends a message to an agent Y .
Subsequently, Y sends a response to X.
An agent X concurrently sends several messages (>1) to an agent Y. Then Y sends a response to each message received from X.
An agent X sends exactly one out of two (or more) alternative message sets to an agent Y. Subsequently, Y sends a corresponding response to a message received from X.
The iterative implementation of SIP-4, s.t. message exchange process continues till an Agent X does not need responses from an
Agent Y . how to instantiate (refine) patterns with details of each agent behavior to obtain sound and structured models of multi-agent systems with two interacting agents. 3
In this section, we recall definitions from Petri net theory necessary for constructing and refining formal models of service interaction patterns.
N denotes the set of non-negative integers. Let A be a set. The set of all finite non-empty sequences over A is denoted by A+, and A∗ = A+ ∪ {}, where corresponds to the empty sequence. A function m : A → N defines a multiset m over A. Let m1, m2 be a pair of multisets over A. The standard set operations are extended to multisets as well, i.e. (a) m1 ⊆ m2 ⇔ m1(a) ≤ m2(a), (b) m′ = m1 ∪ m2 ⇔ m′(a) = m1(a) + m2(a) and (c) m′′ = m1 \ m2 ⇔ m′′(a) = max(0, m1(a) − m2(a)) for all a ∈ A.
A Petri net is a triple N = (P, T, F ), where where P and T are two disjoint sets of places and transitions, i.e. P ∩ T = ∅, and F ⊆ (P × T ) ∪ (T × P ) is a flow relation, where dom(F ) ∪ cod(F ) = P ∪ T . Graphically, places are shown by circles, transitions — by boxes, and flow relation — by arcs.
Let N = (P, T, F ) be a Petri net, and X = P ∪ T . The set •x = {y ∈ X|(y, x) ∈ F } denotes the preset of x ∈ X. The set x• = {y ∈ X|(x, y) ∈ F } denotes the postset of x ∈ X. Let A ⊆ X, then •A = x∈A •x, A• = x∈A x•. By N (A) we denote a subnet of N generated by A, i.e. N (A) = (P ∩ A, T ∩ A, F ∩ (A × A)). Note that we consider nets, s.t. ∀t ∈ T : |•t| ≥ 1 and |t•| ≥ 1.
A marking (state) of a Petri net N = (P, T, F ) is a function m : P → N. A marking is shown by putting m(p) black dots (tokens) inside a place p ∈ P . A marked Petri net N = (P, T, F, m0) is a Petri net together with its initial marking m0. A marking m enables a transition t ∈ T , denoted m[t〉, if •t ⊆ m. The firing t at m leads to a new marking m′ = (m \ •t) ∪ t•, denoted m[t〉m′.
A sequence w ∈ T ∗ is a firing sequence of N = (P, T, F, m0) if w = t1t2 . . . tn and m0[t1〉m1[t2〉 . . . mn−1[tn〉mn. Then we can write m0[w〉mn. The set of all firing sequences of N is denoted by F S(N ).
A marking m of N = (P, T, F, m0) is reachable if ∃w ∈ F S(N ) : m0[w〉m. Any reachable marking is reachable from itself, i.e. m[〉m. The set of all markings reachable from m is denoted by [m〉. A reachable marking is dead if it does not enable any transition. N is safe if ∀p ∈ P ∀m ∈ [m0〉 : m(p) ≤ 1. In other words, in a safe net N we have ∀m ∈ [m0〉 : m ⊆ P .
A state machine is a connected Petri net N = (P, T, F ), s.t. ∀t ∈ T : |•t| = |t•| = 1. A subnet of a marked Petri net N = (P, T, F, m0) identified by a subset of places A ⊆ P and its neighborhood, i.e. N (A ∪ (•A•)), is a sequential component of N if it is a state machine and has a single token in the initial marking. N is covered by sequential components if every place belongs to at least one sequential component. Then N is state machine decomposable (SMD).
Workflow nets form a special subclass of Petri nets used for modeling processes. They have an explicitly specified initial and final state. The initial state is obviously to correspond with the initial marking. We define generalized workflow nets which initial and final states are expressed in terms of subsets of places. Note that SMD GWF-nets are safe.
A marked Petri net N = (P, T, F, m0, mf ) is a generalized workflow net (GWF-net) if and only if: 1. m0 ⊆ P , s.t. •m0 = ∅ and m0 ∕= ∅. 2. mf ⊆ P , s.t. mf • = ∅ and mf ∕= ∅. 3. ∀x ∈ P ∪ T ∃s ∈ m0 ∃f ∈ mf : (s, x) ∈ F ∗ and (x, f ) ∈ F ∗, where F ∗ is the reflexive transitive closure of F .
The third requirement intuitively means that each node of a GWF-net should lie on a path from a place in the initial state to a place in the final state. The correctness of processes modeled via GWF-nets is considered in terms of their soundness. A GWF-net N = (P, T, F, m0, mf ) is sound if and only if: 1. ∀m ∈ [m0〉 : mf ∈ [m〉. 2. ∀m ∈ [m0〉 : mf ⊆ m ⇒ m = mf . 3. ∀t ∈ T ∃m ∈ [m0〉 : m[t〉. 4
Modeling and Refining Abstract Service Interaction
Patterns
Figure 2 shows seven sound and state machine decomposable GWF-nets
constructed according to the specification of abstract patterns given in Section 2.
Each GWF-net is also a channel-composition of two disjoint GWF-nets.
Channels are places which we add to connect selected transitions of GWF-nets.
Channels model message exchange between two agents. A channel-composition of two
GWF-nets N1 and N2 via a set of channels C is denoted by N1 ⊕C N2, where
C is a parameter. In an abstract pattern N1 ⊕C N2, N1 and N2 are abstract
models of agent behavior. The precise definition of the channel-composition has
been given in [
(b) SIP-2 N1 s N1 s1 r1 r
N2 r2 s2
N2 s1
s2 N1 r1
r2
N2 s11 r11
N1 s12 r12 r21 s21
N2 r22 s22 s1 N1 s11 r11 N1 s2
r1 (c) SIP-3 s12 r12 r21 s21 r22 s22 N2 r2 N2 (d) SIP-4 (e) SIP-5
(f) SIP-6 s12 r11 s11 N1 s21 r21
N2
r22
(g) SIP-7
We refine GWF-nets of abstract interaction patterns with detailed models
of agent behavior following the compositional approach described in [
The α-morphism is a mapping between two state machine decomposable GWF-nets: from a refined model to its abstraction. The α-morphism is a total surjective mapping. It maps nodes of a refined model onto nodes of its ϕ : N1 →
N2, where N2 is an abstract model, and N1 is its refinement. Consider the α-morphism ϕ : N1′ → N1 shown in Fig. 3(a), where N1′ is a refinement of N1 from the abstract pattern SIP-4. The refinement of places is depicted by shaded ovals and by the transition labels explicitly, which can also result in splitting transitions of an abstract model. As shown in Fig. 3(a), the transition r1 of the abstract GWF-net N1 is refined (split) by a pair of transitions r11 and r12 of the detailed GWF-net N1′ , whereas the transition s1 is not refined. s 1 also mapped to this place. In Fig. 3(a), the transition t9 is mapped to the final place of N1. Then its neighborhood is also mapped to the final place of N2.
The main motivation behind α-morphisms is the ability to ensure that
propleft in the subnet ϕ−1(p) of N1′ refining the place p of N1.
erties of an abstract model hold in its refinement (refer to Lemma 1 in [
According to the main result of [
Thus, we can refine interaction patterns with sound GWF-nets corresponding to the detailed models of agent behavior. As a result, we obtain sound GWF-nets of multi-agent systems with two asynchronously interacting agents. Therefore, each pattern defines a class of sound process models for multi-agent systems.
For example, consider the pattern SIP-4 (see Fig. 2(d)). Its refinement is and ϕ2 : N2′ → provided in Fig. 3(b), according to α-morphisms ϕ1 : N1′ → N1 given in Fig. 3(a)
N2 indicated by shaded ovals and transition labels. A possible
refinement of the pattern SIP-7 has been given in [
Let us consider the patterns with conflicts (SIP-3, SIP-6 and SIP-7) in more
detail. A set of transitions is in conflict if the share at least one common
input place. Conflicts of the abstract model should be properly refined (given by
definition of α-morphisms in [
Consider refinements of N1 from the pattern SIP-3 shown in Fig. 4. The refinement shown in Fig. 4(a) is incorrect, since the output places (a, b) of the shaded subnet have only one outgoing transition, whereas the abstract place p has the choice between two transitions. The refinement shown in Fig. 4(b) is valid, since the output places (c, d) of the shaded subnet has “the same choices” the abstract place p does. Moreover, in the case of the place d, the transition s2 is split into two other transitions (s21 and s22) at the detailed level in N1′ .
N'1 t 1 a s 1 t 2 b s 2 s 1 N1 p s 2 t 1 c t 2 d s1 s2 s1 s21 s21 N'1 'v3U+MXGZPwY7E 8gRn>ACcjHLNFD/quQTIKkB5Jo l<atexish1_b64="0fO9rWzmSyd2Vp s 1 N1 p s 2 (a) wrong refinement
(b) correct refinement
our experiments inductive miner [
Main Layout of Experiments The experiments have been conducted according to the plan provided below. Step 1. Take a service interaction pattern which is modeled in terms of the channel-composition N1 ⊕C N2 and refine it by using α-morphisms ϕi : Ni′ → Ni (i = 1, 2). Thus, obtain a sound system model N1′ ⊕ N2′ .
Step 2. Compute an event log L of N1′ ⊕ N2′ by simulating it using the tool
presented in [
Step 3. Discover a GWF-net Nd from the event log L directly.
Step 4. Filter the event log L according to the behavior of individual agents obtaining the two sub-logs LN1′ and LN2′ .
Step 5. Discover two sound GWF-nets N1′ and N2′ from the sub-logs LN1′ and LN2′ computed at the previous step.
Step 6. Having constructed the α-morphism ϕi : Ni′ → compositionally discovered GWF-net Nc = N1′ ⊕C N2′ .
Step 7. Compare quality of Nc with that of Nd constructed at Step 4. Ni (i = 1, 2), get a
The construction of the two α-morphisms at Step 6 is done manually so far. An algorithm for constructing α-morphisms is subject for further investigations.
There are four main quality dimensions used in process discovery: fitness,
precision, simplicity and generalization [
The (structural) complexity of a discovered process model is captured by the simplicity dimension. We express a model simplicity through assessing: – the number of places, transitions and arcs; – the number of neighboring transitions between different agents. The following paragraph explains the main idea behind the notion of neighboring transitions.
Neighboring transitions. Inductive miner produces a sound GWF-net N = (P, T, F, m0, mf ) with transitions labeled by a transition labeling function λ : T → A ∪ {τ }. A is a set of visible event names recorded in an event log from which N is discovered, whereas τ is a special label of a silent transitions. Silent transitions do not correspond to any event from an event log.
We introduce the notion of neighboring transitions as an attempt to measure the extent to which a structure of a discovered model correspond to the actual multi-agent system structure w.r.t. agent interaction. In other words, we expect a structured model of a multi-agent system to explicitly indicate behavior of individual agents as well as the way the communicate by sending/receiving messages (via channels). Below we give precise definitions.
Let N = (P, T, F, m0, mf ) be a GWF-net, and λ : A ∪ {τ } be a transition labeling function. Two transitions t1, t2 ∈ T , s.t. λ(t1) ∕= τ and λ(t2) ∕= τ , are called neighboring iff there exists a path in N connecting t1 and t2, where other transitions are silent. This is expressed symbolically as follows: – (t1, t2) ∈ F ∗, where F ∗ is the reflexive transitive closure of F , and – ∀t ∈ T \ {t1, t2} : ((t1, t) ∈ F ∗ ∧ (t, t2) ∈ F ∗) ⇒ λ(t) = τ.
When N represents a model for a multi-agent system with two asynchronously interacting agents X and Y , T = TX ∪TY , s.t. TX ∩TY = ∅. We are interested in finding neighboring transition pairs involving different agents. NbN denotes the number of neighboring transition pairs of N from (TX × TY ) ∪ (TY × TX ), s.t. two symmetric pairs are counted as a single pair. Intuitively, the bigger the value of NbN is, the less transparent and understandable the structure N is w.r.t. agent interaction. NbN of a “perfect” model of a multi-agent system is minimized up to transitions connected directly via channel places.
Consider two GWF-net fragments shown in Fig. 5, where ti and qi transition labels correspond to actions of different agents. Silent transitions are indicated by black boxes. The fragment shown in Fig. 5(a) has 5 neighboring transitions pairs, whereas NbN of the fragment shown in Fig. 5(b) is 2 corresponding to the only transitions connected via the small channel place.
t1 t2 q1 t3 q2 q3 (a) NbN = 5 t1
t2 t3 q1 q3 q2 q4 (b) NbN = 2
The following conclusions can be made based on the results obtained: 1. Compositionally discovered models are more compact w.r.t. the number of nodes and arcs; 2. Precision of composed models is generally higher in comparison with the precision of directly discovered models (except for SIP-2 and SIP-4);
SIP-1 SIP-2 SIP-3 SIP-4 SIP-5 SIP-6 SIP-7 3. Using compositional approach results in minimizing NbN up to transitions connected only via channel places.
In the case of patterns SIP-2 and SIP-4, precision decrease stems from the structure of the agent models and the lack of event data. Compositionally discovered models with concurrent branches allow for more behavior in comparison with directly discovered models. However, precision of these models will grow, if event logs have more examples (more traces) of the possible observed behavior. 6
This paper deals with the problem of discovering structured and sound models
of multi-agent systems from their event logs. The proposed approach is based on
using asynchronous service interaction patterns. A system model is composed
from two agent models w.r.t. an interaction pattern. We have constructed
formal models of seven typical interaction patterns. They describe communication
between two agents at the abstract level. By using channel-composition and
αmorphisms as described in [
We have conducted the series of experiments on using the proposed interaction patterns for compositional process discovery. Experiment results show that composition allows us to obtain more compact and precise models. Moreover, the structure of compositionally discovered models explicitly indicates agents as subnets and their interaction as channel places. To quantify it, we have introduced the notion of neighboring transitions. The number of neighboring transitions in composed models is exactly the number of transitions connected via channels.
The future research will be focused on working with more general multilateral patterns involving k (more than two) interaction agents. We also plan to conduct more experiments applying other process discovery algorithms provided that discovered models meets necessary requirements. Note also that formal models of the proposed patterns can be regularly composed (sequencing, alternative of parallel composition) producing more complex interaction patterns.