Current process discovery techniques focus on the derivation of a process model on the basis of the activity relations extracted from an event log. However, there are situations where more knowledge can be provided to the discovery algorithm, thus alleviating the discovery challenge. In particular, the (partial) characterization of the independence or concurrency between a pair of activities may be well-known. In this paper we present POD, a tool for discovery of Petri nets that can incorporate this type of additional information. We believe requiring independence/concurrency information is very natural in many scenarios, e.g., when there is some knowledge of the underlying process. We show with one example how this extra information can e ectively deal with problems such as log incompleteness.
In the last decade several algorithms have been proposed to discover a Petri net
from an event log [
One of the reasons for this low-key industrial adoption of Petri nets, we believe, is that many existing algorithms infer the concurrency relations between transitions exclusively from the information present in the log. This poses two problems. First, the quality of this inference deteriorates with log incompleteness, i.e., when the log does not contain enough information to extract the component's distribution in the architecture of the process. Second, from an information-theoretical perspective, the log simply contains no information to distinguish non-deterministic actions from truly concurrent behaviour, which Copyright c 2015 for this paper by its authors. Copying permitted for private and academic purposes.
Labeled Partial Orders
Event Structure
Occurrence
Net
Fold
Petri Net
Merge implies that most of the aforementioned algorithms can at best be based on probabilistic analysis of limited reliability.
To ll this gap, we present POD, a tool that incorporates this crucial user input: a so-called independence relation, i.e., an explicit, user-provided description of the concurrency relations between the system activities. One example could be the di erent tests that a patient should undergo in order to have a diagnosis: blood test, allergy test, and radiology test. Speci cally, this input is provided under the form of an irre exive, symmetric binary relation on the set of system actions.
One of the few works that considers the concurrency or distribution of the
system as an input is [
The approach of our tool is summarized in Figure 1. Starting from an event log
and a concurrency relation on its set of activities, we construct a collection of
labeled partial orders whose linearizations include both the sequences in the log
as well those that could be obtained via successive permutations of concurrent
activities. We then merge this collection into an event structure [
POD is a command-line tool implemented in Python. It interacts with the Z3
SMT-solver [
The most prominent feature in POD is the ability to generate fully- tting nets
whose transitions exhibit exactly the same independence (concurrency) than the
one stated by the independence relation given as input (POD can also relax this
controlled generalization, i.e., generalizing more). While the underlying theory [
POD is available from http://github.com/cesaro/pod/releases/tag/v0.1. It has been tested in MAC and Linux and the installation requires simply to unpack the les into a directory. Once unpacked, cd to it and run it as ./src/pod.py. The tool can also perform various handy tasks related to process discovery, such as extracting a random log from a Petri net, dumping statistics of a net, a log, etc.
POD reads and writes logs in XES format and Petri nets in PNML format. As for the independence relation, it expects, for the time being, a plain-text le where every line de nes one pair of dependent transitions (i.e., the le contains the complement of an independence relation, usually smaller), cf. POD's website.
Assume that we have a log le log.xes and a dependency le dep.txt. We
instruct POD to do process discovery:
./src/pod.py discover log.xes dep.txt --out result.pnml
By default POD will output the occurrence net mentioned above, i.e., it will
perform no generalization at all. In other words, it will use the identity relation
as a folding equivalence, cf. [
Consider the net in Figure 2 (a), and consider the following log containing only two of its executions (which however re all possible eight transitions): While one could argue that this is a very incomplete log, we show that POD can in fact reconstruct Figure 2 (a) using this log plus some independence relation.4
We supply POD with the best independence relation that an expert would provide. It coincides with the independence relation of the original net. For instance, transitions 1 and 8 are independent, as one can never interfere (neither make possible nor disable) the ring of the other. Similarly, 3 and 4, or even 1 and 2 are independent. Transitions, 4 and 5, or 1 and 3 are however dependent. 1 3 (a) 4 7 (e) 2 6 1 5 8 3 5 1 3 (b) 4 7 6 2 6 5 8 8 2 4
When we run POD with these two inputs (log and independence relation), it will internally construct the event structure depicted in Figure 2 (d). This object tracks in a compact, concurrency-aware fashion the dependencies and 4 Go to http://lipn.fr/~rodriguez/exp/bpm15/ to reproduce this experiment. con icts between the occurrences of transitions (events) of the net, as recorded in the log. POD next transforms it into Figure 2 (e), an occurrence net denoting exactly the same behaviour as the event structure. This net is a tting and 100% precise description of the log (all executions in it but not in the log are provably executions of the original system). Observe that the two events labelled by 3 and 5 (immediately after 1) are concurrent, as requested by the input independence relation. Observe also that there is two occurrences of transition 6 and that this is somehow an unwinded version of the original net.
Finally POD will fold this occurrence net and output the result, depicted in Figure 2 (b), which is identical to the original except for the output places of 7 and 8. We asked POD to use an independence-preserving (option --eq=ip-smt) folding, meaning that the result net should exhibit the same concurrency information expressed in the input independence relation.
By contrast, ILP Miner [
Process discovery is recognized as one of the key enablers of BPM. However, problems like log incompleteness, as exempli ed above, or noise hamper significantly the success of process discovery techniques in industrial scenarios. We believe that the development of tools like POD, which let the user incorporate knowledge that can be used to soundly cope with these challenges, can ll the gap between academic tools and industrial acceptance of process discovery.