# Cross-Organization Emergency Response Process Mining: An Approach Based on Petri Nets

Authors: Cong Liu; Huiling Li; Qingtian Zeng; Ting Lu; Caihong Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

To support effective emergency disposal, organizations need to collaborate with each other to complete the emergency mission that cannot be handled by a single organization. In general, emergency disposal that involves multiple organizations is typically organized as a group of interactive processes, known as cross-organization emergency response processes (CERPs). The construction of CERPs is a time-consuming and error-prone task that requires practitioners to have extensive experience and business background. Process mining aims to construct process models by analyzing event logs. However, existing process mining techniques cannot be applied directly to discover CERPs since we have to consider the complexity of various collaborations among different organizations, e.g., message exchange and resource sharing patterns. To tackle this challenge, a CERP model mining method is proposed in this paper. More specifically, we first extend classical Petri nets with resource and message attributes, known as resource and message aware Petri nets (RMPNs). Then, intra-organization emergency response process (IERP) models that are represented as RMPNs are discovered from emergency drilling event logs. Next, collaboration patterns among emergency organizations are formally defined and discovered. Finally, CERP models are obtained by merging IERP models and collaboration patterns. Through comparative experimental evaluation using the fire emergency drilling event log, we illustrate that the proposed approach facilitates the discovery of high-quality CERP models than existing state-of-the-art approaches.


---

## Body

## 1. Introduction

Since the 9/11 terrorist attack, there have been considerable efforts to improve the effectiveness and efficiency to respond to emergencies. Generally speaking, an emergency is a situation that imposes immediate risk to life, property, and environment, which requires urgent disposal and intervention to prevent its worsening [1]. To support effective emergency disposal, organizations need to collaborate with each other to complete the emergency mission that cannot be handled by one single organization. In general, emergency disposal that involves multiple organizations are typically organized as a group of loosely-coupled interactive processes, known as cross-organization emergency response processes (CERPs) [2]. The construction of CERPs can improve the efficiency and effectiveness of emergency decision-making. However, the design of CERPs is typically a time-consuming and error-prone task that requires modelers to have extensive experience and business background.During the execution of emergency responses, event logs are recorded and stored by emergency management systems [3]. Process mining aims to construct process models by analyzing event logs collected from various information systems [4, 5]. However, existing process mining techniques cannot be applied to discover CERPs since we have to consider the complexity of various collaborations among different organizations, e.g., message exchange and resource sharing patterns. Therefore, an automated method to mine CERP models from emergency drilling event logs is urgently needed to improve the efficient model construction.To this end, we present a CERP model mining method that takes as input an emergency drilling event log. The contributions of this paper are summarized as follows: (1) Petri nets are extended with resource and message attributes, denoted as RMPNs, to model CERPs. (2) For each organization, a novel algorithm is proposed to discover the intra-organization emergency response process (IERP) model. (3) Three kinds of collaboration patterns, including message exchange pattern, resource sharing pattern, and task synchronization pattern, are formalized based on RMPNs. In addition, the corresponding discovery techniques are presented; and (4) CERP models are discovered by merging all involved IERP models and collaboration patterns.The remainder of the paper is organized as follows. Section2 presents a review of the related work. Section 3 introduces some terminologies and notations used throughout the paper. A fire emergency response process case is introduced to be used as a case study in Section 4. Section 5 introduces the mining method for CERP models. Section 6 performs comparative evaluation. Finally, Section 7 concludes the paper.


## 2. Related Work

In this paper, we summarize work related to cross-organization business process modeling, process mining and cross-organization process mining, and emergency response process modeling and mining.


### 2.1. Cross-Organization Business Process Modeling

Van Der Aalst extended traditional workflow nets to a cross-organization scenario to model cross-organizational workflows and verify the correctness from a structure perspective in [6]. In [7], Mo et al. proposed a cross-organization business process modeling approach that applies finite state machine and asynchronous communication model. In [8], existing cross-organizational modeling methods are classified from the interorganizational angle and qualitative and quantitative analysis on the correctness and effectiveness are performed. Jiang et al. [9] described a timed colored Petri net and process-view combined approach to construct cross-organization business processes and a three-layered framework is proposed to support the interoperability.In our previous work, we introduced four kinds of collaboration patterns, including message interaction, resource interaction, task collaboration, and service out-sourcing patterns, based on which a cross-organization collaborative medical business process is modeled and its correctness is verified via reachability analysis of Petri nets in [10]. More recently, we investigated the modeling and correctness verification of cross-organizational business processes that interact through task synchronization patterns in [11].


### 2.2. Process Mining and Cross-Organization Process Mining

Process mining can extract useful information from event logs commonly generated by information systems. This technology provides new means for process discovery, monitoring, and improvement in various applications [12]. As an often cited example, the a-Algorithm [4] first defines four kinds of ordering relations. Then, a workflow net is derived from these task dependency relations. To further its application for less-structured event log and overcome the spaghetti-like models which contain all details without any hierarchies, Christian and Wil proposed the fuzzy mining approach in [13]. Leemans et al. proposed the inductive miner to handle infrequence and incomplete event logs, and the discovered Petri net-based process model is guaranteed to be correct in [14].In [5], four coordination patterns among different organizations are first defined and process mining approaches are used to discover the process model of each organization and corresponding coordination patterns based on which the whole cross-organization process is obtained by integration. In our recent work, the privacy problem of cross-organizational business process mining is investigated and a privacy-preservation mining method is proposed to construct the organization-specific cross-organization collaborative process model in [15]. In [16], a top-down process mining approach is proposed to construct the cross-organization model in service out-sourcing scenario from heterogeneous logs collected from distributed environment. Petri net refinement technique is used to merge the main process and the out-sourced ones.


### 2.3. Emergency Response Process Modeling and Mining

In [1, 17], we investigated the modeling and analysis methods for an emergency response process constrained by resources and uncertain durations. The number of available resources and minimum resource demand for an emergency response process is analyzed. Moreover, resource conflict detection and resolution strategies are also investigated to optimize the universal process performance. Li et al. proposed Petri net-based modeling techniques for subway station fire emergency response processes in [15]. A hierarchical Petri net that includes a logic net, a semantic net, and a set of case models is introduced for modeling and verification of emergency response processes in [18]. The applicability of this approach is validated by an emergency treatment process of highways under snow/ice weather conditions. More recently, we proposed a top-down approach for model construction and correctness verification of cross-organization emergency response processes in [19]. To support efficient emergency resource management, Zeng et al. [20] proposed an approach to support emergency resource management including both intra-organization private resource management and cross-organization public resource management.In the emergency response process mining area, He et al. applied process mining techniques to uncover emergency rescue process of coal mine gas explosion accidents from the historical event logs in [3]. However, this approach focuses on single emergency response process and does not consider interactions and collaborations among different emergency organizations, and the resource attributes and message attributes are not considered.


## 2.1. Cross-Organization Business Process Modeling

Van Der Aalst extended traditional workflow nets to a cross-organization scenario to model cross-organizational workflows and verify the correctness from a structure perspective in [6]. In [7], Mo et al. proposed a cross-organization business process modeling approach that applies finite state machine and asynchronous communication model. In [8], existing cross-organizational modeling methods are classified from the interorganizational angle and qualitative and quantitative analysis on the correctness and effectiveness are performed. Jiang et al. [9] described a timed colored Petri net and process-view combined approach to construct cross-organization business processes and a three-layered framework is proposed to support the interoperability.In our previous work, we introduced four kinds of collaboration patterns, including message interaction, resource interaction, task collaboration, and service out-sourcing patterns, based on which a cross-organization collaborative medical business process is modeled and its correctness is verified via reachability analysis of Petri nets in [10]. More recently, we investigated the modeling and correctness verification of cross-organizational business processes that interact through task synchronization patterns in [11].


## 2.2. Process Mining and Cross-Organization Process Mining

Process mining can extract useful information from event logs commonly generated by information systems. This technology provides new means for process discovery, monitoring, and improvement in various applications [12]. As an often cited example, the a-Algorithm [4] first defines four kinds of ordering relations. Then, a workflow net is derived from these task dependency relations. To further its application for less-structured event log and overcome the spaghetti-like models which contain all details without any hierarchies, Christian and Wil proposed the fuzzy mining approach in [13]. Leemans et al. proposed the inductive miner to handle infrequence and incomplete event logs, and the discovered Petri net-based process model is guaranteed to be correct in [14].In [5], four coordination patterns among different organizations are first defined and process mining approaches are used to discover the process model of each organization and corresponding coordination patterns based on which the whole cross-organization process is obtained by integration. In our recent work, the privacy problem of cross-organizational business process mining is investigated and a privacy-preservation mining method is proposed to construct the organization-specific cross-organization collaborative process model in [15]. In [16], a top-down process mining approach is proposed to construct the cross-organization model in service out-sourcing scenario from heterogeneous logs collected from distributed environment. Petri net refinement technique is used to merge the main process and the out-sourced ones.


## 2.3. Emergency Response Process Modeling and Mining

In [1, 17], we investigated the modeling and analysis methods for an emergency response process constrained by resources and uncertain durations. The number of available resources and minimum resource demand for an emergency response process is analyzed. Moreover, resource conflict detection and resolution strategies are also investigated to optimize the universal process performance. Li et al. proposed Petri net-based modeling techniques for subway station fire emergency response processes in [15]. A hierarchical Petri net that includes a logic net, a semantic net, and a set of case models is introduced for modeling and verification of emergency response processes in [18]. The applicability of this approach is validated by an emergency treatment process of highways under snow/ice weather conditions. More recently, we proposed a top-down approach for model construction and correctness verification of cross-organization emergency response processes in [19]. To support efficient emergency resource management, Zeng et al. [20] proposed an approach to support emergency resource management including both intra-organization private resource management and cross-organization public resource management.In the emergency response process mining area, He et al. applied process mining techniques to uncover emergency rescue process of coal mine gas explosion accidents from the historical event logs in [3]. However, this approach focuses on single emergency response process and does not consider interactions and collaborations among different emergency organizations, and the resource attributes and message attributes are not considered.


## 3. Terminologies

Given a setS, where S denotes the number of elements in S. x∈S denotes that x is an element of S. We use ∅ to denote the empty set. f:X⟶Y is a function, i.e., domf=X is the domain and rngf=fx|x∈domf⊆Y is the range. If σ1=a1andσ2=a2,…σn=an, we write σ=a1,a2,…,an. σ=n represents the length of sequence σ is n(n is a natural number). The set of all finite sequences over S is denoted as S∗.This work is based on Petri nets, and some basic concepts are reviewed below [21–24].Definition 1.
(Petri nets). A Petri net is defined as a 4-tupleΣ=P,T,F,M0, such that (1) P∩T=∅ and P∪T≠∅, where P is a finite set of places and T is a finite set of transitions; (2) F⊆P×T∪T×P is a finite set of arcs; and (3) M0:P⟶0,1,2,3,…,n is the initial marking.
For anyx∈P∪T, •x=y|y,x∈F is the preset of x and x•=y|x,y∈F is its postset. M0 denotes the initial marking, and RM0 is the set of reachable markings of Σ. For any t∈T, t is enabled under M, denoted as Σ,Mt>, if ∀p∈•t:Mp≥1. If Σ,Mt> holds, t may fire, resulting in a new marking M′, denoted as Σ,Mt>Σ,M′ such that M′p=Mp−1 if p∈t•/t•, M′p=Mp+1 if p∈t•/t•, and otherwise M′p=Mp.
A Petri net that describes a process is called workflow net (or WF-net). Its definition is reviewed below [25].Definition 2.
(workflow nets). A Petri netΣ=P,T,F,M0 is a WF-net if the following conditions hold: (1) there exists a source place i∈P such that •i=∅; (2) there exists a sink place o∈P such that o•=∅; and (3) each node is on a path from i to o; and (4) for each p∈P, M0p=1 if p=i, and otherwise M0p=0.
Because a process is created once it enters the workflow engine and destroyed when completed, we use a source place and a sink place to explicitly denote the initial and final states. Transitions are used to represent tasks in a process.


## 4. A Fire Emergency Response Process Case

When a fire emergency occurs, its disposal usually involves multiple emergency organizations. A typical fire emergency response process usually involves the following organizations: police station, emergency command center (ECC), explosive ordnance disposal (EOD) team, fire brigade, and hospital. Figure1 shows the overall cross-organization fire emergency response process and an overview of the main emergency tasks for each organization.Figure 1
Cross-organization fire emergency response collaboration diagram.This emergency response scenario includes the following steps. (1) The police station first receives a fire alarm and then reports the information to ECC. (2) The police rushes to the fire site and performs its detailed disposal missions and then reports the site conditions to ECC. (3) After receiving the fire information, ECC first establishes the temporary emergency command group and then makes and issues emergency plans to its subordinate organizations, i.e., medical rescue instruction to the hospital, search EOD instruction to the EOD team, and fire rescue instruction to the fire brigade. (4) The EOD team rushes to the site once it receives the search EOD instruction from ECC, conducts its specific disposal tasks according to the emergency plan, and finally reports the EOD search results. (5) The fire brigade rushes to the site once it receives the fire rescue instruction from ECC, conducts its specific disposal tasks according to the emergency plan, and finally reports the fire rescue results. (6) The hospital personnel rushes to the site once it receives the medical rescue instruction from ECC, conducts its specific disposal tasks according to the plan, and finally reports the results. (7) After receiving all the feedback information from the hospital, EOD team, and fire brigade, ECC makes a summary and finally does the file archive. (8) ECC arranges the media coverage for this emergency response; and (9) Finally, ECC, hospital, and the fire brigade do the media coverage together.During the execution of the fire emergency response processes, emergency drilling event logs are recorded and stored by the emergency management systems. In general, the collected fire emergency drilling event log, denoted asfirelog1, contains 126 cases, 3528 events, and 28 emergency tasks in total. This log will be used in the next sections to explain our concepts and techniques, and every event in the emergency drilling event logs have the resource attributes, message attributes, and timestamp.


## 5. Cross-Organization Emergency Response Process Mining

This section details the cross-organization emergency response process (CERP) model mining from emergency drilling event logs.


### 5.1. Emergency Drilling Event Logs

The event logs captured during the execution of emergency response processes are essentially a collection of events such that each event refers to an emergency task and includes a group of attributes, such as timestamp, resources, and sent and received messages. Formal definition of events and attributes are given below.Definition 3.
(events and attributes). Letξ be the event universe, i.e., the set of all possible event identifiers and N be the attribute universes, i.e., the set of all possible event attributes. For any event e∈ξ and n∈N, #ne represents the value of attribute n for e.
For an arbitrary evente∈ξ, the following attributes are involved in the emergency drilling event logs:(i)
#casee represents the case to which e belongs to, and each event belongs to only one independent case(ii)
#acte represents the task name of e(iii)
#mRe represents the messages received by e(iv)
#mSe represents the messages sent by e(v)
#rRe represents the resource set of e(vi)
#orge represents the organization name of e(vii)
#timee represents the timestamp of eDefinition 4.
(case, event log). A case over some event universeξ is a finite sequence of events σ∈ξ∗ such that each event appears only once and all events have the same case id, i.e., 1≤i<j≤σ: σi≠σj∧#caseσi=#caseσj. An event log is defined as a finite set of cases, i.e., L⊆ξ∗.
Table1 depicts a fragment of the fire emergency drilling event log firelog. It contains one case that records all events generated during one run of the process. In total, 30 events are included and they are fully ordered by the timestamp. For example, we have the following observation for e2: (1) #casee2=1 means that the event belongs to case with ID 1; (2) #acte2=t2 means that the task name of this event is t2; (3) #mRe2=∅ means that no message is sent after the event finished; (4) #mSe2=pm1 means that this event needs to receive message pm1 before execution; (5) #rRe2=∅ means that the event does not use resources; and (6) #timee2=14:21Jan022014 is the time that this event ends.Table 1
A fragment of the fire emergency drilling event log.
Emergency organizationEvent#case#act#mR#mS#rR#time∗Police statione11t1∅∅∅14 : 20 Jan 02 2014e21t2∅pm1∅14 : 21 Jan 02 2014e31t3∅∅∅14 : 26 Jan 02 2014e41t4∅∅∅14 : 30 Jan 02 2014e51t5∅∅∅14 : 32 Jan 02 2014e61t6∅∅∅14 : 32 Jan 02 2014e71t7∅pm2∅14 : 35 Jan 02 2014e81t8∅∅∅14 : 45 Jan 02 2014∗ECCe91t9pm1∅∅14 : 23 Jan 02 2014e101t10pm2pm3,pm4,pm5∅14 : 36 Jan 02 2014e111t11pm6,pm7,pm8∅∅17 : 05 Jan 02 2014e121t12∅∅∅17 : 10 Jan 02 2014e131t13∅∅∅17 : 20 Jan 02 2014e141t14∅∅∅17 : 25 Jan 02 2014∗EOD teame151t15pm3∅pr14 : 38 Jan 02 2014e161t16∅∅∅14 : 43 Jan 02 2014e171t17∅pm6∅15 : 00 Jan 02 2014∗Fire brigadee181t18pm4∅pr14 : 37 Jan 02 2014e191t19∅∅∅15 : 30 Jan 02 2014e201t20∅∅∅16 : 40 Jan 02 2014e211t21∅∅∅16 : 40 Jan 02 2014e221t22∅pm7∅17 : 00 Jan 02 2014e231t14∅∅∅17 : 25 Jan 02 2014∗Hospitale241t23pm5∅pr14 : 39 Jan 02 2014e251t24∅∅∅14 : 55 Jan 02 2014e261t25∅∅∅15 : 50 Jan 02 2014e271t26∅∅∅15 : 50 Jan 02 2014e281t27∅∅∅16 : 40 Jan 02 2014e291t28∅pm8∅17 : 00 Jan 02 2014e301t14∅∅∅17 : 25 Jan 02 2014


### 5.2. Intra-Organization Emergency Response Process Model Mining

Different from traditional business processes, CERPs are more complex and typically involve various elements, e.g., messages and resources. Therefore, we first extend classical Petri nets with message and resource attributes as follows.Definition 5.
(RMPN).Σ=P,T,F,M0 is a RMPN if (1) P=PL∪PR∪PM, PL∩PR=∅, PL∩PM=∅, PM∩PR=∅, and PL⊆P represent the logic place set, PM⊆P represents the message place set, and PR⊆P represents resource place set; (2) F=FL∪FR∪FM, where FL represents the control-flow, FR represents the resource flow, and FM represents the message flow; and (3) ∀p∈P if p∈PR∪i, i∈PL∧•i=∅, and M0p=1, and otherwise M0p=0.
RMPNs are used to represent CERPs, and the mining methods are all based on this model. We first introduce how to mine IERP models. To this end, we need to obtain the emergency drilling event logs of each organization by projecting the whole event log based on the organization attribute. Taking event log in Table1, the emergency drilling event log of the police station includes e1, e2, e3, e4, e5, e6, e7, and e8.
Then, the following algorithm is presented to discover the IERP model represented by an RMPN by taking as input the event log of single organization.
Algorithm1 extends the existing inductive miner [14] that mines the control-flow model with message sending and receiving information as well as resource accessing information and finally returns an RMPN. Considering the police station as an example, task t2 sends message pm1 and task t7 sends message pm2 when finished. By taking as input the firelog, the obtained RMPN for each organization is shown in Table 2.Algorithm 1: IERP model mining.
(i)
INTPUT: event log of a single emergency organization(ii)
OUTPUT: IERP modelΣ=P,T,F,M0(1)
P⟵∅, PL⟵∅, PR⟵∅, PM⟵∅, F⟵∅, FL⟵∅, FR⟵∅, FM⟵∅,T⟵∅,M0⟵∅; //initialization(2)
PL,T,FL⟵inductive minerL; //mining the control flow(3)
For eacht∈T(4)
For eachσ∈L(5)
For eache∈σ(6)
Ift = = #acte(7)
If#mSe!=∅; //mining sending message places(8)
PM⟵PM∪#mSe;(9)
FM⟵FM∪t,#mSe;(10)
End if(11)
If#mRe!=∅; //mining receiving message places(12)
PM⟵PM∪#mRe;(13)
FM⟵FM∪#mRe,t;(14)
End if(15)
If#rRe!=∅; //mining resource places(16)
PR⟵PR∪#rRe(17)
FR⟵FR∪#rRe,t,t,#rRe(18)
End if(19)
End if(20)
End for(21)
End for(22) End for(23)P⟵PR∪PL∪PM,F⟵FR∪FL∪FM,M0⟵i∪PR;(24)
ReturnΣ=P,T,F,M0. //output the RMPN.Table 2
Discovered RMPN of each emergency organization.
Emergency organizationDiscovered RMPNPolice stationECCEOD teamFire brigadeHospital


### 5.3. Cross-Organization Collaboration Pattern Mining

After obtaining the RMPN for each emergency organization, we introduce how to discover collaboration patterns. To this end, three kinds of patterns, including message exchange pattern, resource sharing pattern, and task synchronization pattern, are formalized as follows.Definition 6.
(message exchange pattern). LetΣ1=P1,T1,F1,M01 and Σ2=P2,T2,F2,M02 be the RMPNs of two emergency organizations. Message exchange pattern exists between them if (1) PL1∩PL2=∅; (2) PM1∩PM2≠∅; (3) PR1∩PR2=∅; and (4) T1∩T2=∅.Definition 7.
(resource sharing pattern). LetΣ1=P1,T1,F1,M01 and Σ2=P2,T2,F2,M02 be the RMPNs of the two emergency organizations. Resource sharing pattern exists between them if (1) PL1∩PL2=∅; (2) PM1∩PM2=∅; (3) PR1∩PR2≠∅; and (4) T1∩T2=∅.Definition 8.
(task synchronization pattern). LetΣ1=P1,T1,F1,M01 and Σ2=P2,T2,F2,M02 be the RMPNs of two emergency organizations. Task synchronization pattern exists between them: (1) P1∩P2=∅; (2) T1∩T2≠∅.
Then, Algorithm2 is presented to discover collaboration patterns between any two arbitrary organizations. Algorithm 2 takes as input RMPNs of two emergency organizations and returns all collaborations patterns between them. All collaboration patterns involved in the fire emergency response process are discovered and shown in Table 3. For example, there exists message exchange pattern between the police station and the ECC via message places pm1 and pm2.Algorithm 2: Collaboration patterns mining.
INPUT: two RMPNsΣ1=P1,T1,F1,M01 and Σ2=P2,T2,F2,M02OUTPUT: collaboration pattern modelΣ=P,T,F,M0(1)
P⟵∅, PL⟵∅, PR⟵∅, PM⟵∅, F⟵∅, FL⟵∅, FR⟵∅, FM⟵∅, T⟵∅, M0⟵∅; //initialization(2)
IfPM1∩PM2≠∅ //mining messages exchange pattern(3)
For eachp∈PM1∩PM2(4)
PM⟵PM∪p;(5)
Ifp•!=∅(6)
T⟵T∪p•;(7)
For eacht∈p•(8)
FM⟵FM∪p,t;(9)
End for(10)
End if(11)
Ifp•!=∅(12)
T⟵T∪•p;(13)
For eacht∈•p(14)
FM⟵FM∪t,p;(15)
End for(16)
End if(17)
End for(18)
End if(19)
IfPR1∩PR2≠∅ //mining resource sharing pattern(20)
For eachp∈PR1∩PR2(21)
PR⟵PR∪p;(22)
T⟵T∪p•∪•p;(23)
For eacht∈p•∪•p(24)
FM⟵FM∪p,t,t,p;(25)
End for(26)
End for(27)
End if(28)
IfT1∩T2≠∅ //mining task synchronization pattern(29)
T⟵T∪T1∩T2;(30)
End if(31)
P⟵PR∪PL∪PM,F⟵FR∪FL∪FM,M0⟵PR;(32)
ReturnΣ=P,T,F,M0.    //return mined collaboration patternsTable 3
Discovered collaboration patterns.
Emergency organizationDiscovered collaboration patternsPolice station and ECCEOD team and ECCFire brigade and ECCHospital and ECCFire brigade and EOD teamHospital and EOD teamHospital and fire brigade


### 5.4. Cross-Organization Emergency Response Process Model Mining

After mining IERP models and collaboration patterns among different emergency organizations, the whole CERP model comes into reach. In general, the CERP model is obtained by merging all IERP models and the collaboration patterns based on Petri net composition technique. Detailed steps are shown in Algorithm3.Algorithm 3: CERP model mining.
INPUT:Ξ=Σx|Σxis the RMP Noforganizationx,Ψ=Σx,y|Σx,y is the collaboration model between organizations x and y}OUTPUT: CERP modelΣ=P,T,F,M0(1)
P⟵∅, PL⟵∅, PR⟵∅, PM⟵∅, F⟵∅, FL⟵∅, FR⟵∅, FM⟵∅, T⟵∅,M0⟵∅,Ps⟵∅;    //initialize the integration model(2)
For eachΣx∈Ξ   //merging RMPN model(3)
PM⟵PM∪PMx;(4)
PR⟵PR∪PRx;(5)
PL⟵PL∪PLx;(6)
For eachp∈PLx(7)
Ifp•==∅(8)
Ps⟵Ps∪p;(9)
End if(10)
End for(11)
FL⟵FL∪FLx;(12)
FM⟵FM∪FMx;(13)
FR⟵FR∪FRx;(14)
T⟵T∪Tx;(15)
End for(16)
For eachΣx,y∈Ψ //merging collaboration patterns(17)
PM⟵PM∪PMx,y;(18)
PR⟵PR∪PRx,y;(19)
PL⟵PL∪PLx,y;(20)
FL⟵FL∪FLx,y;(21)
FM⟵FM∪FMx,y;(22)
FR⟵FR∪FRx,y;(23)
T⟵T∪Tx,y;(24)
End for(25)
P⟵PR∪PL∪PM,F⟵FR∪FL∪FM,M0⟵Ps∪PR;(26)
ReturnΣ=P,T,F,M0.    //output the integrated RMPNBy taking as input the IERP models in Table2 and the collaboration patterns in Table 3, the CERP model of the cross-organization fire emergency response process model is obtained and shown in Figure 2.Figure 2
CERP model discovered by our approach.Note that the model discovered by our approach is correct, and therefore, it can be used for further conformance checking, e.g., fitness and precision measure. However, the approach does not guarantee that all discovered models by our approach are correct. Actually, we are working on extending existing correctness verification and correction techniques, such as [26, 27], to be applicable for the discovered cross-organization process models by our approach.


## 5.1. Emergency Drilling Event Logs

The event logs captured during the execution of emergency response processes are essentially a collection of events such that each event refers to an emergency task and includes a group of attributes, such as timestamp, resources, and sent and received messages. Formal definition of events and attributes are given below.Definition 3.
(events and attributes). Letξ be the event universe, i.e., the set of all possible event identifiers and N be the attribute universes, i.e., the set of all possible event attributes. For any event e∈ξ and n∈N, #ne represents the value of attribute n for e.
For an arbitrary evente∈ξ, the following attributes are involved in the emergency drilling event logs:(i)
#casee represents the case to which e belongs to, and each event belongs to only one independent case(ii)
#acte represents the task name of e(iii)
#mRe represents the messages received by e(iv)
#mSe represents the messages sent by e(v)
#rRe represents the resource set of e(vi)
#orge represents the organization name of e(vii)
#timee represents the timestamp of eDefinition 4.
(case, event log). A case over some event universeξ is a finite sequence of events σ∈ξ∗ such that each event appears only once and all events have the same case id, i.e., 1≤i<j≤σ: σi≠σj∧#caseσi=#caseσj. An event log is defined as a finite set of cases, i.e., L⊆ξ∗.
Table1 depicts a fragment of the fire emergency drilling event log firelog. It contains one case that records all events generated during one run of the process. In total, 30 events are included and they are fully ordered by the timestamp. For example, we have the following observation for e2: (1) #casee2=1 means that the event belongs to case with ID 1; (2) #acte2=t2 means that the task name of this event is t2; (3) #mRe2=∅ means that no message is sent after the event finished; (4) #mSe2=pm1 means that this event needs to receive message pm1 before execution; (5) #rRe2=∅ means that the event does not use resources; and (6) #timee2=14:21Jan022014 is the time that this event ends.Table 1
A fragment of the fire emergency drilling event log.
Emergency organizationEvent#case#act#mR#mS#rR#time∗Police statione11t1∅∅∅14 : 20 Jan 02 2014e21t2∅pm1∅14 : 21 Jan 02 2014e31t3∅∅∅14 : 26 Jan 02 2014e41t4∅∅∅14 : 30 Jan 02 2014e51t5∅∅∅14 : 32 Jan 02 2014e61t6∅∅∅14 : 32 Jan 02 2014e71t7∅pm2∅14 : 35 Jan 02 2014e81t8∅∅∅14 : 45 Jan 02 2014∗ECCe91t9pm1∅∅14 : 23 Jan 02 2014e101t10pm2pm3,pm4,pm5∅14 : 36 Jan 02 2014e111t11pm6,pm7,pm8∅∅17 : 05 Jan 02 2014e121t12∅∅∅17 : 10 Jan 02 2014e131t13∅∅∅17 : 20 Jan 02 2014e141t14∅∅∅17 : 25 Jan 02 2014∗EOD teame151t15pm3∅pr14 : 38 Jan 02 2014e161t16∅∅∅14 : 43 Jan 02 2014e171t17∅pm6∅15 : 00 Jan 02 2014∗Fire brigadee181t18pm4∅pr14 : 37 Jan 02 2014e191t19∅∅∅15 : 30 Jan 02 2014e201t20∅∅∅16 : 40 Jan 02 2014e211t21∅∅∅16 : 40 Jan 02 2014e221t22∅pm7∅17 : 00 Jan 02 2014e231t14∅∅∅17 : 25 Jan 02 2014∗Hospitale241t23pm5∅pr14 : 39 Jan 02 2014e251t24∅∅∅14 : 55 Jan 02 2014e261t25∅∅∅15 : 50 Jan 02 2014e271t26∅∅∅15 : 50 Jan 02 2014e281t27∅∅∅16 : 40 Jan 02 2014e291t28∅pm8∅17 : 00 Jan 02 2014e301t14∅∅∅17 : 25 Jan 02 2014


## 5.2. Intra-Organization Emergency Response Process Model Mining

Different from traditional business processes, CERPs are more complex and typically involve various elements, e.g., messages and resources. Therefore, we first extend classical Petri nets with message and resource attributes as follows.Definition 5.
(RMPN).Σ=P,T,F,M0 is a RMPN if (1) P=PL∪PR∪PM, PL∩PR=∅, PL∩PM=∅, PM∩PR=∅, and PL⊆P represent the logic place set, PM⊆P represents the message place set, and PR⊆P represents resource place set; (2) F=FL∪FR∪FM, where FL represents the control-flow, FR represents the resource flow, and FM represents the message flow; and (3) ∀p∈P if p∈PR∪i, i∈PL∧•i=∅, and M0p=1, and otherwise M0p=0.
RMPNs are used to represent CERPs, and the mining methods are all based on this model. We first introduce how to mine IERP models. To this end, we need to obtain the emergency drilling event logs of each organization by projecting the whole event log based on the organization attribute. Taking event log in Table1, the emergency drilling event log of the police station includes e1, e2, e3, e4, e5, e6, e7, and e8.
Then, the following algorithm is presented to discover the IERP model represented by an RMPN by taking as input the event log of single organization.
Algorithm1 extends the existing inductive miner [14] that mines the control-flow model with message sending and receiving information as well as resource accessing information and finally returns an RMPN. Considering the police station as an example, task t2 sends message pm1 and task t7 sends message pm2 when finished. By taking as input the firelog, the obtained RMPN for each organization is shown in Table 2.Algorithm 1: IERP model mining.
(i)
INTPUT: event log of a single emergency organization(ii)
OUTPUT: IERP modelΣ=P,T,F,M0(1)
P⟵∅, PL⟵∅, PR⟵∅, PM⟵∅, F⟵∅, FL⟵∅, FR⟵∅, FM⟵∅,T⟵∅,M0⟵∅; //initialization(2)
PL,T,FL⟵inductive minerL; //mining the control flow(3)
For eacht∈T(4)
For eachσ∈L(5)
For eache∈σ(6)
Ift = = #acte(7)
If#mSe!=∅; //mining sending message places(8)
PM⟵PM∪#mSe;(9)
FM⟵FM∪t,#mSe;(10)
End if(11)
If#mRe!=∅; //mining receiving message places(12)
PM⟵PM∪#mRe;(13)
FM⟵FM∪#mRe,t;(14)
End if(15)
If#rRe!=∅; //mining resource places(16)
PR⟵PR∪#rRe(17)
FR⟵FR∪#rRe,t,t,#rRe(18)
End if(19)
End if(20)
End for(21)
End for(22) End for(23)P⟵PR∪PL∪PM,F⟵FR∪FL∪FM,M0⟵i∪PR;(24)
ReturnΣ=P,T,F,M0. //output the RMPN.Table 2
Discovered RMPN of each emergency organization.
Emergency organizationDiscovered RMPNPolice stationECCEOD teamFire brigadeHospital


## 5.3. Cross-Organization Collaboration Pattern Mining

After obtaining the RMPN for each emergency organization, we introduce how to discover collaboration patterns. To this end, three kinds of patterns, including message exchange pattern, resource sharing pattern, and task synchronization pattern, are formalized as follows.Definition 6.
(message exchange pattern). LetΣ1=P1,T1,F1,M01 and Σ2=P2,T2,F2,M02 be the RMPNs of two emergency organizations. Message exchange pattern exists between them if (1) PL1∩PL2=∅; (2) PM1∩PM2≠∅; (3) PR1∩PR2=∅; and (4) T1∩T2=∅.Definition 7.
(resource sharing pattern). LetΣ1=P1,T1,F1,M01 and Σ2=P2,T2,F2,M02 be the RMPNs of the two emergency organizations. Resource sharing pattern exists between them if (1) PL1∩PL2=∅; (2) PM1∩PM2=∅; (3) PR1∩PR2≠∅; and (4) T1∩T2=∅.Definition 8.
(task synchronization pattern). LetΣ1=P1,T1,F1,M01 and Σ2=P2,T2,F2,M02 be the RMPNs of two emergency organizations. Task synchronization pattern exists between them: (1) P1∩P2=∅; (2) T1∩T2≠∅.
Then, Algorithm2 is presented to discover collaboration patterns between any two arbitrary organizations. Algorithm 2 takes as input RMPNs of two emergency organizations and returns all collaborations patterns between them. All collaboration patterns involved in the fire emergency response process are discovered and shown in Table 3. For example, there exists message exchange pattern between the police station and the ECC via message places pm1 and pm2.Algorithm 2: Collaboration patterns mining.
INPUT: two RMPNsΣ1=P1,T1,F1,M01 and Σ2=P2,T2,F2,M02OUTPUT: collaboration pattern modelΣ=P,T,F,M0(1)
P⟵∅, PL⟵∅, PR⟵∅, PM⟵∅, F⟵∅, FL⟵∅, FR⟵∅, FM⟵∅, T⟵∅, M0⟵∅; //initialization(2)
IfPM1∩PM2≠∅ //mining messages exchange pattern(3)
For eachp∈PM1∩PM2(4)
PM⟵PM∪p;(5)
Ifp•!=∅(6)
T⟵T∪p•;(7)
For eacht∈p•(8)
FM⟵FM∪p,t;(9)
End for(10)
End if(11)
Ifp•!=∅(12)
T⟵T∪•p;(13)
For eacht∈•p(14)
FM⟵FM∪t,p;(15)
End for(16)
End if(17)
End for(18)
End if(19)
IfPR1∩PR2≠∅ //mining resource sharing pattern(20)
For eachp∈PR1∩PR2(21)
PR⟵PR∪p;(22)
T⟵T∪p•∪•p;(23)
For eacht∈p•∪•p(24)
FM⟵FM∪p,t,t,p;(25)
End for(26)
End for(27)
End if(28)
IfT1∩T2≠∅ //mining task synchronization pattern(29)
T⟵T∪T1∩T2;(30)
End if(31)
P⟵PR∪PL∪PM,F⟵FR∪FL∪FM,M0⟵PR;(32)
ReturnΣ=P,T,F,M0.    //return mined collaboration patternsTable 3
Discovered collaboration patterns.
Emergency organizationDiscovered collaboration patternsPolice station and ECCEOD team and ECCFire brigade and ECCHospital and ECCFire brigade and EOD teamHospital and EOD teamHospital and fire brigade


## 5.4. Cross-Organization Emergency Response Process Model Mining

After mining IERP models and collaboration patterns among different emergency organizations, the whole CERP model comes into reach. In general, the CERP model is obtained by merging all IERP models and the collaboration patterns based on Petri net composition technique. Detailed steps are shown in Algorithm3.Algorithm 3: CERP model mining.
INPUT:Ξ=Σx|Σxis the RMP Noforganizationx,Ψ=Σx,y|Σx,y is the collaboration model between organizations x and y}OUTPUT: CERP modelΣ=P,T,F,M0(1)
P⟵∅, PL⟵∅, PR⟵∅, PM⟵∅, F⟵∅, FL⟵∅, FR⟵∅, FM⟵∅, T⟵∅,M0⟵∅,Ps⟵∅;    //initialize the integration model(2)
For eachΣx∈Ξ   //merging RMPN model(3)
PM⟵PM∪PMx;(4)
PR⟵PR∪PRx;(5)
PL⟵PL∪PLx;(6)
For eachp∈PLx(7)
Ifp•==∅(8)
Ps⟵Ps∪p;(9)
End if(10)
End for(11)
FL⟵FL∪FLx;(12)
FM⟵FM∪FMx;(13)
FR⟵FR∪FRx;(14)
T⟵T∪Tx;(15)
End for(16)
For eachΣx,y∈Ψ //merging collaboration patterns(17)
PM⟵PM∪PMx,y;(18)
PR⟵PR∪PRx,y;(19)
PL⟵PL∪PLx,y;(20)
FL⟵FL∪FLx,y;(21)
FM⟵FM∪FMx,y;(22)
FR⟵FR∪FRx,y;(23)
T⟵T∪Tx,y;(24)
End for(25)
P⟵PR∪PL∪PM,F⟵FR∪FL∪FM,M0⟵Ps∪PR;(26)
ReturnΣ=P,T,F,M0.    //output the integrated RMPNBy taking as input the IERP models in Table2 and the collaboration patterns in Table 3, the CERP model of the cross-organization fire emergency response process model is obtained and shown in Figure 2.Figure 2
CERP model discovered by our approach.Note that the model discovered by our approach is correct, and therefore, it can be used for further conformance checking, e.g., fitness and precision measure. However, the approach does not guarantee that all discovered models by our approach are correct. Actually, we are working on extending existing correctness verification and correction techniques, such as [26, 27], to be applicable for the discovered cross-organization process models by our approach.


## 6. Comparative Evaluation

In this section, we compare the quality of existing process mining approaches with our approach to discover the CERP model using thefirelog. A laptop with a 2.40 GHz CPU, Windows 8.1, and Java SE 1.7.0 67 (64 bit) with 16 GB of allocated RAM is used.


### 6.1. Setup

The following three mining approaches are compared.(i)
By taking as input the wholefirelog, the inductive miner that is known as the state-of-the-art process discovery technique is directly used. This approach is denoted as A1.(ii)
By taking as input the wholefirelog, we first project the whole log to each emergency organization based on the organization attribute in the firelog. Then, the inductive miner is used to discover a submodel for each organization. Finally, all discovered submodels are merged in a parallel manner. This approach is denoted as A2. In addition, the model discovered by approach A2 is essentially a workflow net-like structure with dedicate source and sink places and transitions.(iii)
Our proposed CERP model discovery approach is applied on thefirelog. This approach is denoted as A3.To quantify the effectiveness of different approaches, the well-defined metrics, e.g., fitness and precision, are applied to measure the quality of the discovered CERP models with respect to inputfirelog.Fitness quantifies the extent to which the discovered model can accurately reproduce the traces recorded in the event log. Low fitness indicates that the event log allows for much more behaviour that is not allowed by the model. The paper applies the fitness defined in [28]. Precision quantifies the fraction of the behavior allowed by the model which is not seen in the event log. Low precision means that the model allows for much more behaviour compared to the event log. The paper applies the precision defined in [29].Note that there is a trade off between fitness and precision [30]. Therefore, we introduce the F-measure. The F-measure is defined as the harmonic mean of the fitness and precision metrics as shown in the following equation:(1)F−measure=2×fitness×precisionfitness+precision.


### 6.2. Experimental Results

By taking as input thefirelog, A1 is first applied. This approach does not consider the organization information and collaboration patterns and only discovers the control flow of all emergency tasks directly by the inductive miner. The discovered CERP model represented as a classical Petri net is shown in Figure 3. Then, by taking as input the firelog and discovered model, the fitness, precision, and F-measure values are obtained and depicted in Table 4.Figure 3
CERP model discovered by A1.Table 4
Evaluation results.
ApproachFitnessPrecisionF-measureA110.390.56A210.440.58A310.620.76Then, by taking as input thefirelog, A2 is applied. This approach first projects the whole log to each emergency organization based on the organization attribute in the firelog. Then, the inductive miner is used to discover a submodel for each organization. Finally, all discovered submodels are merged in a parallel manner. The discovered CERP model is shown in Figure 4 where two transitions colored as black form the parallel relation among all organizations. By taking as input the firelog and discovered model, the fitness, precision, and F-measure values are obtained and depicted in Table 4. Note that the organization information is supported by A2, but the collaboration patterns are not discovered.Figure 4
CERP model discovered by A2.Finally, by taking as input thefirelog, our proposed approach, denoted as A3, is applied. This approach first projects the whole log to each emergency organization based on the organization attribute. This step is same to A2. Then, Algorithm 1 is applied to perform IERP mining where an RMPN is used to represent the discovered IERP model. Next, collaboration patterns are discovered using Algorithm 2. Finally, all discovered IERP models and collaboration patterns are merged according to Algorithm 3. The discovered CERP model is shown in Figure 2. By taking as input the firelog and discovered model, the fitness, precision, and F-measure values are obtained and depicted in Table 4. Note that both the organization information and collaboration patterns are properly discovered.According to Table4, we can see that (1) all three approaches can guarantee that the discovered CERP model with perfect fitness. The rationale behind is that they all rely on the inductive miner that guarantees fitness is 1; (2) the precision of the CERP model discovered by A3 is the highest while the precision of the CERP model discovered by that the A1 is the lowest. A high precision value normally indicates the discovered model is more precise than that with a low precision value. This is because both A2 and A3 use the organization information to localize the discovery scope within a single organization, and therefore, its precision is higher than A1. Different from A2 that simply connects all submodels in a parallel way, A3 can discover collaboration patterns that indicate cross-organization task dependencies; and (3) the F-measure of the CERP model discovered by A3 is the highest, which indicates that the quality of the CERP model discovered by A3 is better than that discovered by A1 and A2.As a conclusion, our proposed approach (A3) can discover more precise cross-organization emergency response process models compared with existing approaches.


## 6.1. Setup

The following three mining approaches are compared.(i)
By taking as input the wholefirelog, the inductive miner that is known as the state-of-the-art process discovery technique is directly used. This approach is denoted as A1.(ii)
By taking as input the wholefirelog, we first project the whole log to each emergency organization based on the organization attribute in the firelog. Then, the inductive miner is used to discover a submodel for each organization. Finally, all discovered submodels are merged in a parallel manner. This approach is denoted as A2. In addition, the model discovered by approach A2 is essentially a workflow net-like structure with dedicate source and sink places and transitions.(iii)
Our proposed CERP model discovery approach is applied on thefirelog. This approach is denoted as A3.To quantify the effectiveness of different approaches, the well-defined metrics, e.g., fitness and precision, are applied to measure the quality of the discovered CERP models with respect to inputfirelog.Fitness quantifies the extent to which the discovered model can accurately reproduce the traces recorded in the event log. Low fitness indicates that the event log allows for much more behaviour that is not allowed by the model. The paper applies the fitness defined in [28]. Precision quantifies the fraction of the behavior allowed by the model which is not seen in the event log. Low precision means that the model allows for much more behaviour compared to the event log. The paper applies the precision defined in [29].Note that there is a trade off between fitness and precision [30]. Therefore, we introduce the F-measure. The F-measure is defined as the harmonic mean of the fitness and precision metrics as shown in the following equation:(1)F−measure=2×fitness×precisionfitness+precision.


## 6.2. Experimental Results

By taking as input thefirelog, A1 is first applied. This approach does not consider the organization information and collaboration patterns and only discovers the control flow of all emergency tasks directly by the inductive miner. The discovered CERP model represented as a classical Petri net is shown in Figure 3. Then, by taking as input the firelog and discovered model, the fitness, precision, and F-measure values are obtained and depicted in Table 4.Figure 3
CERP model discovered by A1.Table 4
Evaluation results.
ApproachFitnessPrecisionF-measureA110.390.56A210.440.58A310.620.76Then, by taking as input thefirelog, A2 is applied. This approach first projects the whole log to each emergency organization based on the organization attribute in the firelog. Then, the inductive miner is used to discover a submodel for each organization. Finally, all discovered submodels are merged in a parallel manner. The discovered CERP model is shown in Figure 4 where two transitions colored as black form the parallel relation among all organizations. By taking as input the firelog and discovered model, the fitness, precision, and F-measure values are obtained and depicted in Table 4. Note that the organization information is supported by A2, but the collaboration patterns are not discovered.Figure 4
CERP model discovered by A2.Finally, by taking as input thefirelog, our proposed approach, denoted as A3, is applied. This approach first projects the whole log to each emergency organization based on the organization attribute. This step is same to A2. Then, Algorithm 1 is applied to perform IERP mining where an RMPN is used to represent the discovered IERP model. Next, collaboration patterns are discovered using Algorithm 2. Finally, all discovered IERP models and collaboration patterns are merged according to Algorithm 3. The discovered CERP model is shown in Figure 2. By taking as input the firelog and discovered model, the fitness, precision, and F-measure values are obtained and depicted in Table 4. Note that both the organization information and collaboration patterns are properly discovered.According to Table4, we can see that (1) all three approaches can guarantee that the discovered CERP model with perfect fitness. The rationale behind is that they all rely on the inductive miner that guarantees fitness is 1; (2) the precision of the CERP model discovered by A3 is the highest while the precision of the CERP model discovered by that the A1 is the lowest. A high precision value normally indicates the discovered model is more precise than that with a low precision value. This is because both A2 and A3 use the organization information to localize the discovery scope within a single organization, and therefore, its precision is higher than A1. Different from A2 that simply connects all submodels in a parallel way, A3 can discover collaboration patterns that indicate cross-organization task dependencies; and (3) the F-measure of the CERP model discovered by A3 is the highest, which indicates that the quality of the CERP model discovered by A3 is better than that discovered by A1 and A2.As a conclusion, our proposed approach (A3) can discover more precise cross-organization emergency response process models compared with existing approaches.


## 7. Conclusion

This paper proposes a cross-organization emergency response process model mining method to support effective emergency disposal process construction. More specifically, we first extend classical Petri nets with resource and message attributes, known as RMPN. Then, IERP models are discovered as RMPNs. Next, collaboration patterns among emergency organizations are formally defined and discovered. Finally, CERP models are obtained by merging IERP models and the collaboration patterns. Through the comparative evaluation using the fire emergency drilling event log, we illustrate that the proposed approach facilitates the discovery of the high-quality CERP model than existing approaches.This paper also opens the door for the following research area that needs to be investigated in our future work. (1) More complex collaboration patterns, e.g., business out-sourcing, need to be explored for more accurate process discovery. (2) Evaluation techniques to quantify the quality of the mined CERP model against the input emergency drilling event logs are urgently required to consider not only control-flow conformance but also message and resource conformance. (3) Considering the volume of emergency response process event logs, log sampling techniques, e.g., [31, 32], maybe useful for efficient mining.



---

*Source: 8836007-2020-11-17.xml*