The design of temporal networks typically follows a top-down approach where a designer handcrafts a temporal network to model some concrete plan of interest. Instead, the bottom-up approach of mining is the process of building a temporal network from a set of execution traces of some (typically unknown) underlying process. Recent research showed that, due to the structural properties of temporal networks, such a task can be done in polynomial time. In this paper, we give an overview of the current status of our research and highlight open problems concerning Formal Methods and Artificial Intelligence.
Temporal networks are a possible framework to model temporal plans and check the consistency
of their temporal constraints imposing delays and deadlines between the occurrences of pairs
of events in the plan [
Like any model-based engineering approach, creating a temporal network is a complex,
time-consuming, and error-prone task, where discrepancies between the actual process and
the obtained network might eventually emerge requiring that the designer refines or abstracts
the model being created. This is a top-down, trial-and-error approach. Instead, the opposite,
bottom-up approach is known in the literature under the name of process mining and it aims to
mine (i.e., synthesize) process descriptions (or, more reasonably, model approximations) from
execution traces (i.e., process logs). A trace describes a run of a process, whereas the set of all
available traces can be thought of as a log of a process carried out many times. One of the first
contributions in process mining is that of Agrawal, Gunopulos, and Leymann [
A CSTNUD involves a finite set of time-points , a finite set of booleans ℬ, a finite set of
contingent links ℒ, and a finite set of constraints [
Every CSTNUD admits a graph-based representation in which nodes model time points, whereas directed labeled edges model contingent links (double) and constraints (single). Whenever a node is sufixed by ? or ! it means that its has an uncontrollable or controllable boolean associated respectively (for simplicity identified by the same letter in lower-case). Table 1 shows such core components. ?, !, and are time points, with associated to the uncontrollable boolean and associated to the controllable boolean . is an uncontrollable time point. The contingent link ⇒ models an uncontrollable duration between 2 and 8 time units. Finally, the arc → models the unconditional delay constraint {} : − ≤ − 1 meaning that is always at least 1 after , whereas → models the conditional deadline constraint {, ¬} : − ≤ 10 meaning that if is observed to be true and is decided to be false, then is within 10 after .
We initially proposed an algorithm to mine CSTNUDs in [19] whose extended version appears in [20]. The algorithm processes a set of well-defined and coherent traces and generates a CSTNUD that contains all time points and booleans appearing in the traces and such that all temporal and truth value assignments of each trace satisfy in the CSTNUD all constraints restricted to those subsets of time points and booleans. Each trace is a set of events that happened at their corresponding absolute times plus the truth value assignment to the booleans (if any) (e.g., = 0, = 1, = 2, ¬, . . . , see [19, 20]). Therefore, our mined networks have always a time point (zero-time point) from and to which all constraints are generated. The idea of the algorithm is fairly simple and can be summarized intuitively in these two main points: 1. Add time points, booleans, contingent links, and constraints whenever they are not in the CSTNUD being mined. 2. Weaken specific contingent links and constraints whenever they are already in the
CSTNUD being mined.
Weakening means to make contingent links and constraints more general so that they can model executions coming from the processed traces. For example, if the current CSTNUD contains a contingent link (, ℓ, , ) and in the next trace the duration of such link is fixed to be , then we modify the CSTNUD so that the “updated” contingent link is (, min(ℓ, ), max(, ), ). Likewise, consider a constraint → labeled by : in the CSTNUD, where either or is . Assume that the next trace entails a constraint → labeled by ′ : ′. If ⊆ ′, then we replace the label : of the original constraint with : max(, ′) (i.e., we operate on the numeric value only). Instead, if ′ ⊂ , we replace the label : of the original constraint with ′ : max(, ′) (i.e., we operate on both the set of literals and numeric value). Of course, if more constraints satisfy the applicability condition of the rule they will be modified all together. Table 2 provides some intuitive examples.
The last step of our algorithm applies a final condition that further relaxes numeric values on constraints to impose a coherence on those constraints whose union of preconditions is a consistent set of literals. We need this last step because we process traces that might be partial. We do not discuss it here for simplicity. Overall, the take-home message is simple:
Always keep the most general constraint.
Since we deal with temporal constraints that are interval bounds, we can work with min/max numeric values. Likewise, since the preconditions on the applications of constraints are sets, we can work with sub/supersets. The asymptotic complexity of our algorithm is upper bounded by (|ℐ|2 × ( + | |)) where ℐ is the set of input traces and is the length of the longest trace in it. We also developed cstnud-miner an open-source software prototype that is available at https://github.com/matteozavatteri/cstnud-miner.
We exploited the well-defined monotone mathematical structure of temporal networks, and we succeeded in the design of a correct algorithm to mine CSTNUDs with a property of interest that we called significance . Roughly, a CSTNUD is significant whenever it contains all time points and booleans appearing in the traces and the temporal and truth value assignments arising from each processed trace satisfy the constraints restricted to these variables in the mined CSTNUD. This is what our theory achieved so far. We outline here some future directions. 1. There exist three main kinds of controllability of temporal networks subject to uncontrollable parts: weak, strong, and dynamic. Weak controllability is when all uncontrollable temporal and truth value assignments are known before starting the execution. Strong controllability is the dual case in which no uncontrollable part will be known during execution. Dynamic controllability is when we make our execution decisions in real-time depending on which uncontrollable temporal and truth value assignments we are observing. All three kinds of controllability boil down to consistency whenever there is no uncontrollable part. In [20] we carried out an experimental evaluation by generating sets of traces belonging to all subformalisms of CSTNUDs. Afterwards, we tested for consistency (if no uncontrollable parts were present), weak, strong and dynamic controllability otherwise. We found that our algorithm mines CSTNUDs which are not strongly controllable (we provided a counter example). Regarding consistency, weak, and dynamic controllability (depending on the type of network) we could not find a counter example. This makes us believe that our algorithm mines CSTNUDs which are weakly and also dynamically controllable (and thus mines consistent networks when all time points and booleans are controllable). However, a formal proof of this statement is still missing and requires to prove the existence of an execution strategy for the mined network. 2. If the aim of (1) would lead to a negative result, and worse still, to a proof that mining controllable CSTNUDs (whose set of constraints is not, of course, empty) is a hard problem, then an attempt toward Machine Learning techniques would be justified to obtain an algorithm to mine (hopefully) controllable temporal networks. Of course, since such AI approaches may fail, particular attention should be devoted to its “success rate”. 3. Assuming to have (2), it remains to be understood if it might (in practice) be more competitive than our current algorithm on huge sets of input traces. 4. Last but not least, several extensions of the algorithm are needed to mine networks such as, for example, those in [21, 22, 23] to handle both time and resource constraints together.
In conclusion these open problems call for a fruitful synergy between Formal Methods and Machine Learning techniques from Artificial Intelligence.
This work was partially supported by MIUR, Project Italian Outstanding Departments, 2018-2022 and by INdAM, GNCS 2020, Project Strategic Reasoning and Automated Synthesis of Multi-Agent Systems. [18] W. M. P. van der Aalst, A. Weijters, L. Maruster, Workflow mining: Which processes can be rediscovered?, in: Eindhoven University of Technology, 2002, pp. 1–25. [19] G. Sciavicco, M. Zavatteri, T. Villa, Mining Significant Temporal Networks Is Polynomial, in: TIME 2020, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 11:1–11:12. [20] G. Sciavicco, M. Zavatteri, T. Villa, Mining cstnuds significant for a set of traces is polynomial, Information and Computation (in press) (2021). [21] M. Zavatteri, R. Rizzi, T. Villa, Dynamic Controllability and (J, K)-Resiliency in Generalized
Constraint Networks with Uncertainty, in: ICAPS 2020, AAAI Press, 2020, pp. 314–322. [22] M. Zavatteri, C. Combi, L. Vigano, Resource controllability of business processes under conditional uncertainty, Journal on Data Semantics (2021) 1–21. [23] C. Combi, R. Posenato, L. Viganò, M. Zavatteri, Conditional simple temporal networks with uncertainty and resources, Journal of Artificial Intelligence Research 64 (2019) 931–985.