Patent ID: 12190142

DETAILED DESCRIPTION

In process mining, conformance checking is performed to evaluate whether the actual execution of a process conforms to the expected execution of the process. In accordance with embodiments of the present invention, conformance checking is performed by comparing transitions between events in an event log of a process with dependencies between activities in a process model of the process to thereby determine the conformance of the transitions. Advantageously, embodiments of the present invention provide for conformance checking with a lower computational complexity than conventional conformance checking techniques, while also providing an output that can be intuitively visualized for a user in a business setting.

FIG.1shows an illustrative process100on which conformance checking may be performed in accordance with one or more embodiments. Process100may be applied to perform any suitable task, such as, e.g., document processing. In one embodiment, process100may be implemented as a robotic process automation (RPA) workflow for automatically performing a task using RPA robots. However, it should be understood that process100may be any suitable well-structured process that can be modelled as a workflow, such as, e.g., a business workflow. A well-structured process is a process having a single entry and single exit sequence of flows.

Process100comprises activities102-116, which represent predefined steps in process100. As shown inFIG.1, process100is modeled as a directed graph where each activity102-116is represented as a node and each transition between activities102-116is represented as edges linking the nodes. The transition between activities represents the execution of process100from a source activity to a destination activity. Process100starts at start activity102and proceeds to activity A104. Process100then proceeds, in parallel, to a first branch comprising activity B106and activity C108and a second branch comprising activity D110and activity E112. Process100then proceeds to activity F114and ends at end activity116. During execution of process100, events are recorded in an event log. An event refers to the execution of an activity for a certain case at a certain point in time. The event may be represented as a tuple comprising an activity, a case identifier, and a time stamp.

FIG.2shows a method200for visualizing conformance checking of a process, in accordance with one or more embodiments. Method200may be performed by any suitable computing device, such as computer1100ofFIG.11. At step202, conformance checking is performed on a process (e.g., process100ofFIG.1). In one embodiment, step202may be performed according to the steps of method300ofFIG.3, described in detail below. At step204, results of the conformance checking performed on the process are visualized. Visualization of results of the conformance checking is discussed in further detail below with respect toFIGS.7-10.

FIG.3shows a method300for performing conformance checking on a process, in accordance with one or more embodiments. Method300may be performed by any suitable computing device, such as computer1100ofFIG.11. In one embodiment, the steps of method300may be performed at step202ofFIG.2.

At step302, a process model of a process and an event log of an execution of the process are received. The process model is a model representing an expected execution of the process. The event log is a log recording events of the actual execution of the process. An exemplary process model is shown inFIG.4and an exemplary event log is shown inFIG.5, both of which are described in detail below.

FIG.4shows an exemplary process model400, in accordance with one or more embodiments. Process model400may be the process model received at step302ofFIG.3. Process model400is the process model of process100ofFIG.1and will be shown and described herein with reference toFIG.1. Process model400is modeled using BPMN (business process model and notation), however it should be understood that process model400may be modeled using any other suitable notation that can represent exclusive choices and parallelism, such as, e.g., Petri nets or process trees.

In one embodiment, process model400models process100using gateways to represent diversions in process100. The gateways control how the process flows during execution. The gateways may be exclusive gateways or parallel gateways and may split a single path into multiple paths or join multiple paths into a single path. For an exclusive gateway, a single output path (for split gateways) or a single input path (for join gateways) is traversed during execution of the process. For a parallel gateway, multiple output paths (for split gateways) or multiple input paths (for join gateways) are concurrently traversed during execution of the process. As shown inFIG.4, parallel split gateway402represents splitting of the path from activity A104into a first path to activity B106and a second path to activity D110to concurrently execute activity B106and activity D110, and parallel join gateway404represents the joining of a first path from activity C108and a concurrent second path from activity E112into a single path to activity F114.

In one embodiment, process model400is a well-structured process model having a single entry and single exit sequence of flows.

FIG.5shows an exemplary event log500of a process, in accordance with one or more embodiments. Event log500may be the event log received at step302ofFIG.3. Event log500is the event log recording execution of process100ofFIG.1and will be shown and described with reference toFIGS.1and4. Event log500is formatted as a table having rows502and columns504. As shown inFIG.5, rows502of event log500comprises rows502-A through502-F, each corresponding to an event defining execution of a respective activity104-114, with a particular time stamp and with a particular case identifier. Event log500may also include rows502for start activity102and end activity116in some embodiments. Columns504of event log500comprises column504-A identifying the activity, column504-B identifying the time stamp, and column504-C identifying the case identifier. Columns504may include additional columns identifying additional attributes of activities.

At step304ofFIG.3, the process model is divided into one or more control regions. A control region is a region of the process model that has a single entry node, a single exit node, and a set of (possibly empty) interior nodes, wherein the entry node is a gateway node or a start node, the exit node is a gateway node or an end node, and each node in the set of interior nodes are activity nodes.

In one embodiment, the process model is divided into control regions according to the following steps. In a first step, a refined process structure tree (RPST) of the process model is generated, for example, using known techniques. In a second step, for each respective split gateway, a concurrency or exclusivity relationship is defined, based on the type of respective gateway, between all fragments of the RPST in which the respective gateway is the entry node. In a third step, a pre-order tree traversal is performed over the fragments of the RPST. During the traversal, concurrency and exclusivity relations of parent fragments are added to the current fragment to ensure concurrency and exclusivity relations based on ancestors are set. In a fourth step, a post-order tree traversal is performed over the fragments of the RPST initializing one or more control regions for every fragment. In this step, start and end nodes are considered gateway nodes. If a fragment is a leaf node of the RPST (i.e., it has no child fragments), a control region is initialized to include all edges in the fragment. If a fragment is not a leaf node of the RPST, consider all edges of the fragment that are not yet part of a control region. For each of such edges, if a gateway node is its source, a control region is initialized to include all edges between the source gateway node and a next gateway node. In a fifth step, successor relations between control regions are set. Successor relations are set based on the control regions that incoming and outgoing edges of the gateway node belong to. In accordance with an embodiment, every gateway is either splitting or joining (not both) and therefore, only the control regions corresponding to outgoing edges of splitting gateways and incoming edges for joining gateways need to be evaluated.

FIG.6shows an exemplary process model600divided into a plurality of control regions, in accordance with one or more embodiments. Process model600is the process model400(FIG.4) of process100(FIG.1), and will be shown and described with reference toFIGS.1and4. As shown inFIG.6, process model600is divided into control regions602,604,606, and608. Control regions604and606are parallel control regions. Control regions are parallel or exclusive control regions if they or one of their ancestors have the same parallel or exclusive split gateways, respectively.

At step306ofFIG.3, reachable nodes are determined for each particular node of the process model. As used herein, nodes of a process model are reachable from a particular node if the nodes are connected to the particular node through edges and/or gateways only, without traversing through activity nodes. For example, in process model400ofFIG.4, activity B106is reachable from activity A104and activity D110is reachable from activity A104, however activity C108is not reachable from activity A104and activity B106is not reachable from activity D110.

At step308, a conformance of the process is determined by comparing transitions from source activities to destination activities in the event log with the reachable nodes. In some embodiments, the comparison may also be based on the control regions. In one embodiment, the conformance of the process is evaluated for each variant found in the event log. A variant refers to a unique sequence of activities. For each variant, the transitions of the variant are replayed or mapped onto the process model. While replaying the variant, each transition is mapped to the process model based on the structure of the process model (e.g., its control regions, concurrency, exclusivity, etc.) and the activities that have already been mapped while replaying the variant, and the mapped variant is rebuilt. If a transition can be mapped to the process model, the transitions are conforming transitions that occur in both the event log and the process model and are added to the mapped variant. If a transition cannot be mapped to the model, a log-only transition from the source activity to the destination activity is added. Behavior that is observed in the event log but not in the process model (log only behavior) and behavior that is not observed in the event log but is observed in the process model (model only behavior) are nonconforming.

For each transition from a source activity to a destination activity in a variant, one of the following situations occur:The source activity and/or the destination activity are not found in the process model: The transition represents nonconforming log only behavior.The transition exists directly in the process model: The transition conforms to the process model.The destination activity is reachable from the source activity: The transition conforms to the process model and the entire path from the source activity to the destination activity are conforming edges.The source activity and the destination activity have no direct relationship: Evaluate conformance based on the control region of the source activity and the destination activity. The source activity and the destination activity have no direct relationship if there is no direct transition between the activities in the model and the destination activity is not reachable from the source activity. One of the following situations occur:The control regions of the source activity and of the destination activity have an exclusive relationship: The transition represents nonconforming log only behavior.The control regions of the source activity and of the destination activity have a concurrent relationship: To handle parallelism, a variant σ replayed to the current activity is projected to track what event last occurred in a particular control region. A region projection σiof variant σ over control regioniis the last event in variant σ that is mapped to an activity in the set of interior nodes of control regioni. If no event in variant σ is mapped to an activity in the set of interior nodes of control regioni, then the region projection σiis empty (i.e., σi=Ø). If the destination activity is reachable from region projection σdestinationof variant σ over control regiondestination(the control region comprising the destination activity), the transition from σdestinationto the destination activity, or its entire path, is conforming. While the order of events in the event log may suggest there is a transition from the source activity to the destination activity, the actual transition is the found path (due to parallelism). If σdestination=Ø, conformance is evaluated based on the entry gateway of the control region of the destination activitydestination. If the destination activity is not reachable from its entry gateway, the transition from the source activity to the destination activity is nonconforming log only behavior. Otherwise, the transition from the entry gateway to the destination activity is conforming.The control regions of the source activity and of the destination activity have no direct relationship: The transition represents nonconforming log only behavior.

In one embodiment, if a transition is mapped from a parallel join gateway to a following activity or gateway, all proceeding paths (paths that end in the join gateway) are closed. This means that all concurrent control regions that end in this join gateway are looked at. For each of these control regions, it is determined whether the join gateway is reachable from the last executed activity in the control region. If so, that transition or path is added as conforming. If not, a log-only transition is added from the last executed activity in the control region to the above join gateway.

Once a variant has been completely replayed, all transitions in the model that have not been added as conforming transitions are evaluated. If those transitions are not required (i.e., they are part of an exclusive path), they are ignored. Otherwise, they are added to the mapped variant as model-only transitions.

At step310, the conformance of the process is output. For example, the conformance of the process can be output by displaying the conformance of the process on a display device of a computer system, storing the conformance of the process on a memory or storage of a computer system, or by transmitting the conformance of the process to a remote computer system. In one embodiment, the conformance of the process is visualized by mapping variants of conforming and/or nonconforming transitions on the process model.

In one embodiment, the conformance of a process may be visualized using a nested model for visualization design. The nested model for visualization design includes the following four layers, where a lower layer is dependent on all layers above, from highest to lowest: i) characterization of the domain problem: describe the tasks and goals of target users in a particular domain; ii) data/operation abstraction design: abstracting from domain specific problems to generic descriptions of operations in the domain of information visualization; iii) encoding/interaction technique design: designing interactions and visual encoding of information; and iv) algorithm design: create an algorithm to enact the interaction design and visual encoding automatically. Each layer will be discussed in further detail as follows.

Characterization of the domain problem: one problem includes an activity in the process model being skipped or an activity not in the process model being executed, which corresponds to log only behavior or model only behavior, respectively.

Data/operation abstraction design: in abstraction design, the user should be able to execute three different workflows in a simple and intuitive manner, with the first workflow being discovering observations, the second workflow being discovering observations, describing them, and finding attribute values that could be the cause, and the third workflow being discover observations, comparing them, and explaining their differences. To enable these three workflows, five different analysis goals should be supported in the visualization design: discover observation, describe observation (aggregate), identify main cause (aggregate) compare entities, and explain differences. Discover observation, which refers to finding specific deviations, is important as it is present in every workflow.

Encoding/interaction technique design: Information has to be encoded for it to be effectively conveyed to the user. Furthermore, interaction allows users to change what information is displayed, allowing for many different queries. A multiple view system may be employed for the visualization of conformance.FIGS.7and8show examples of multiple view systems for the visualization of conformance, in accordance with one embodiment.

FIG.7shows a user interface700of a multiple view system for showing an overall view of results of conformance checking, in accordance with one or more embodiments. User interface700depicts aggregated information over multiple cases, and comprises a main view702, a context view704, and a history view706. In one embodiment, main view702may be a node-link diagram showing conformance between the process model and the event log on the level of event transitions and events. Context view704shows information about conformance of variants or transitions in the event log. In one embodiment, context view704may depicts a bar chart with some default attributes visualized based on a selected aggregation level. Additional attributes may be added to the bar chart. History view706shows aggregated information about the conformance and frequency of variants, transitions, or events over time. In one embodiment, history view706includes one or more line graphs, which are also dependent on the selected aggregation level.

FIG.8shows a user interface800of a multiple view system for showing a detailed view of results of conformance checking, in accordance with one or more embodiments. User interface800shows information for a specific case. User interface800comprises node-link view802showing conformance between the process model and the event log on the level of event transitions and events, attribute view804, and Gantt view806.

FIG.9shows a user interface900showing an exemplary visualization of conformance for an invoices data set mapped to a process model, and visualized in the visual conformance checking color mode of the process graph. The less frequent behavior was not modeled in the process model and shows up as log-only behavior.

FIG.10shows a user interface1000showing exemplary conformance information of transitions, in accordance with one or more embodiments. User interface1000shows the conformance information as bar charts. The currently selected metric is the number of events, which is used across all charts.

FIG.11is a block diagram illustrating a computing system1100configured to execute the methods described in reference toFIGS.2-3, according to an embodiment of the present invention. In some embodiments, computing system1100may be one or more of the computing systems depicted and/or described herein. Computing system1100includes a bus1102or other communication mechanism for communicating information, and processor(s)1104coupled to bus1102for processing information. Processor(s)1104may be any type of general or specific purpose processor, including a Central Processing Unit (CPU), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), a Graphics Processing Unit (GPU), multiple instances thereof, and/or any combination thereof. Processor(s)1104may also have multiple processing cores, and at least some of the cores may be configured to perform specific functions. Multi-parallel processing may be used in some embodiments.

Computing system1100further includes a memory1106for storing information and instructions to be executed by processor(s)1104. Memory1106can be comprised of any combination of Random Access Memory (RAM), Read Only Memory (ROM), flash memory, cache, static storage such as a magnetic or optical disk, or any other types of non-transitory computer-readable media or combinations thereof. Non-transitory computer-readable media may be any available media that can be accessed by processor(s)1104and may include volatile media, non-volatile media, or both. The media may also be removable, non-removable, or both.

Additionally, computing system1100includes a communication device1108, such as a transceiver, to provide access to a communications network via a wireless and/or wired connection according to any currently existing or future-implemented communications standard and/or protocol.

Processor(s)1104are further coupled via bus1102to a display1110that is suitable for displaying information to a user. Display1110may also be configured as a touch display and/or any suitable haptic I/O device.

A keyboard1112and a cursor control device1114, such as a computer mouse, a touchpad, etc., are further coupled to bus1102to enable a user to interface with computing system. However, in certain embodiments, a physical keyboard and mouse may not be present, and the user may interact with the device solely through display1110and/or a touchpad (not shown). Any type and combination of input devices may be used as a matter of design choice. In certain embodiments, no physical input device and/or display is present. For instance, the user may interact with computing system1100remotely via another computing system in communication therewith, or computing system1100may operate autonomously.

Memory1106stores software modules that provide functionality when executed by processor(s)1104. The modules include an operating system1116for computing system1100and one or more additional functional modules1118configured to perform all or part of the processes described herein or derivatives thereof.

One skilled in the art will appreciate that a “system” could be embodied as a server, an embedded computing system, a personal computer, a console, a personal digital assistant (PDA), a cell phone, a tablet computing device, a quantum computing system, or any other suitable computing device, or combination of devices without deviating from the scope of the invention. Presenting the above-described functions as being performed by a “system” is not intended to limit the scope of the present invention in any way, but is intended to provide one example of the many embodiments of the present invention. Indeed, methods, systems, and apparatuses disclosed herein may be implemented in localized and distributed forms consistent with computing technology, including cloud computing systems.

It should be noted that some of the system features described in this specification have been presented as modules, in order to more particularly emphasize their implementation independence. For example, a module may be implemented as a hardware circuit comprising custom very large scale integration (VLSI) circuits or gate arrays, off-the-shelf semiconductors such as logic chips, transistors, or other discrete components. A module may also be implemented in programmable hardware devices such as field programmable gate arrays, programmable array logic, programmable logic devices, graphics processing units, or the like. A module may also be at least partially implemented in software for execution by various types of processors. An identified unit of executable code may, for instance, include one or more physical or logical blocks of computer instructions that may, for instance, be organized as an object, procedure, or function. Nevertheless, the executables of an identified module need not be physically located together, but may include disparate instructions stored in different locations that, when joined logically together, comprise the module and achieve the stated purpose for the module. Further, modules may be stored on a computer-readable medium, which may be, for instance, a hard disk drive, flash device, RAM, tape, and/or any other such non-transitory computer-readable medium used to store data without deviating from the scope of the invention. Indeed, a module of executable code could be a single instruction, or many instructions, and may even be distributed over several different code segments, among different programs, and across several memory devices. Similarly, operational data may be identified and illustrated herein within modules, and may be embodied in any suitable form and organized within any suitable type of data structure. The operational data may be collected as a single data set, or may be distributed over different locations including over different storage devices, and may exist, at least partially, merely as electronic signals on a system or network.

The foregoing merely illustrates the principles of the disclosure. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the disclosure and are included within its spirit and scope. Furthermore, all examples and conditional language recited herein are principally intended to be only for pedagogical purposes to aid the reader in understanding the principles of the disclosure and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the disclosure, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future.