Simple temporal networks with uncertainty (STNUs) have achieved wide attention and are the basis of many applications requiring the representation of temporal constraints and checking whether they are conflicting. Dynamic controllability is currently the most studied notion to check whether a system can be controlled without violating temporal constraints despite uncertainties. However, dynamic controllability assumes that the actual duration of a contingent activity is known only when the end event of that activity occurs. The recently introduced notion of agile controllability considers the case where this duration is known earlier, leading to a more relaxed notion of temporal feasibility. We extend the definition of STNUs to STNUOs (Simple Temporal Networks with Uncertainty and Oracles) to represent the point in time at which information about a contingent duration is available. We formally define agile controllability as a generalization of dynamic controllability considering the timepoints of information availability. We propose a set of constraint propagation rules for STNUOs, leading to an algorithm for checking agile controllability.

A Simple Temporal Network with Uncertainty (STNU) is a structure for representing and reasoning about time constraints on actions that may have uncertain durations. An STNU is dynamically controllable (DC) if there exists a dynamic strategy for executing the network that guarantees that all of its constraints will be satisfied no matter how the uncertain durations turn out---within their specified bounds. However, such strategies typically require exponential space. Therefore, converting a DC STNU into a so-called dispatchable form for practical applications is essential. The relevant portions of a real-time execution strategy for a dispatchable STNU can be incrementally constructed during execution, requiring only O(n²) space, while also providing maximum flexibility and minimal computation during the execution of the network. Although existing algorithms can generate equivalent-dispatchable STNUs, they do not guarantee a minimal number of edges in the STNU graph. Since the number of edges directly impacts the computations during execution, this paper presents a novel algorithm for converting any dispatchable STNU into an equivalent dispatchable network having a minimal number of edges. The complexity of the algorithm is O(k n³), where k is the number of actions with uncertain durations, and n is the number of timepoints in the network. The paper also provides an empirical evaluation of the reduction of edges obtained by the impact of the new algorithm.

A Probabilistic Simple Temporal Network (PSTN) is a formalism for representing and reasoning about actions subject to temporal constraints, where some action durations may be uncontrollable, modeled using continuous probability density functions. Recent work aims to manage this kind of uncertainty during execution by approximating a PSTN by a Simple Temporal Network with Uncertainty (STNU) (for which well-known execution strategies exist) and using an STNU execution strategy to execute the PSTN, hoping that its probabilistic action durations will not cause any constraint violations. This paper presents significant improvements to the robust execution of PSTNs. Our approach is based on a recent, faster algorithm for finding negative cycles in non-DC STNUs. We also formally prove that many of the constraints included in others' work are unnecessary and that our algorithm can take advantage of a flexible real-time execution algorithm to react to observations of contingent durations that may fall outside the fixed STNU bounds. The paper presents an empirical evaluation of our approach that provides evidence of its effectiveness in robustly executing PSTNs derived from a publicly available benchmark.

A Simple Temporal Network with Uncertainty (STNU) is a data structure for reasoning about time constraints on actions that may have uncertain durations. An STNU is dispatchable if it can be executed in real-time with minimal computation 1) satisfying all constraints no matter how the uncertain durations play out and 2) retaining maximum flexibility. The fastest known algorithm for converting STNUs into dispatchable form runs in O(n3) time, where n is the number of timepoints. This paper presents a faster algorithm that runs in O(mn+kn2+n2log⁡n) time, where m is the number of edges and k is the number of uncertain durations. This performance is particularly meaningful in fields like Business Process Management, where sparse STNUs can represent temporal processes or plans. For sparse STNUs, our algorithm generates dispatchable forms in time O(n2log⁡n), a significant improvement over the O(n3)-time previous fastest algorithm.

Managing temporal process constraints in modularized processes is an important task, both during the design, as it allows the reuse of temporal (child) process models, and during the checking of temporal properties of processes, as it avoids the necessity of “unfolding” child processes within the main process model. Taking into account the capability of providing modular solutions, modeling and checking temporal features of processes is still an open problem in the context of process-aware information systems. In this paper, we present and discuss a novel approach to represent flexible temporal constraints in modularized time-aware BPMN process models. To support temporal flexibility, allowed task durations are represented through guarded ranges that allow a limited (guarded) restriction of task durations during process execution if it is necessary to guarantee the satisfaction of all temporal constraints. We, then, propose how to derive a compact representation of the overall temporal behavior of such time-aware BPMN models. Such compact representation of child processes allows us to check the dynamic controllability (DC) of a parent time-aware process model without “unfolding” the child process models. Dynamic controllability guarantees that process models can have process instances (i.e., executions) satisfying all the temporal constraints for any possible combination of allowed durations of tasks and child processes. Possible approaches for even more flexibility by solving some kinds of DC violations are then introduced. We use a real process model from a healthcare domain as a motivating example, and we also present a proof-of-concept prototype confirming the concrete applicability of the solutions we propose, followed by an experimental evaluation.

A Simple Temporal Network with Uncertainty (STNU) includes real-valued variables, called time-points; binary difference constraints on those time-points; and contingent links that represent actions with uncertain durations. STNUs have been used for robot control, web-service composition, and business processes. The most important property of an STNU is called dynamic controllability (DC); and algorithms for checking this property are called DC-checking algorithms. The DC-checking algorithm for STNUs with the best worst-case time-complexity is the RUL¯ algorithm due to Cairo, Hunsberger and Rizzi. Its complexity is O(mn + k²n + kn log n), where n is the number of time-points, m is the number of constraints, and k is the number of contingent links. It is expected that this worst-case complexity cannot be improved upon. However, this paper provides a new algorithm, called RUL2021, that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation.

A Flexible Simple Temporal Network with Uncertainty (FTNU) represents temporal constraints between time-points. Time-points are variables that must be set (executed) satisfying all the constraints. Some time-points are contingent. It means that they are set by the environment and only observed by the system executing the network. The ranges representing temporal constraints associated with contingent time-points (guarded ranges) can be shrunk during execution only to some extent to have more flexibility in the execution of the network. Subsets of time-points/constraints may be executed/considered in different contexts according to some observed conditions. The main issue here consists of determining whether all the time-points, under the control of the system, are executable in a way that all the specified constraints are satisfied for any possible occurrence of contingent time-points and any possible context. Such property is called controllability. Even though an algorithm was proposed for checking the controllability of such networks, we show that such an algorithm has a limit. Indeed, it does not determine the right bounds for guarded links, and, therefore, it doesn’t permit the system to exploit the potential flexibility of the network. We then propose a new constraint-propagation algorithm for checking controllability, prove that such a new algorithm determines the right guarded ranges, and it is sound-and-complete. Thus, it can be used also for executing the network, by leveraging its flexibility.

Since Simple Temporal Networks (STNs) were first introduced in 1991, there have been numerous theoretic and algorithmic advances that have made them practical for a wide variety of applications. However, the presentation of most of the important advances have been scattered across numerous conference papers and journal articles. As a result, it is too easy for even experienced researchers to be unaware of results that could positively impact their work. In this talk we review the most important results about STNs for researchers in Artificial Intelligence who are interested in incorporating the management of time and temporal constraints into their projects.

Conditional simple temporal networks with uncertainty (CSTNUs) allow for the representation of temporal plans subject to both conditional constraints and uncertain durations. Dynamic controllability (DC) of CSTNUs ensures the existence of an execution strategy able to execute the network in real time (i.e., scheduling the time points under control) depending on how these two uncontrollable parts behave. However, CSTNUs do not deal with resources. In this paper, we define conditional simple temporal networks with uncertainty and resources (CSTNURs) by injecting resources and runtime resource constraints (RRCs) into the specification. Resources are mandatory for executing the time points and their availability is represented through temporal expressions, whereas RRCs restrict resource availability by further temporal constraints among resources. We provide a fully-automated encoding to translate any CSTNUR into an equivalent timed game automaton in polynomial time for a sound and complete DC-checking.

Recent work on Conditional Simple Temporal Networks (CSTNs) has focused on checking the dynamic consistency (DC) property assuming that execution strategies can react instantaneously to observations. Three alternative semantics---IR-DC, 0-DC, and π-DC---have been presented. The most practical DC-checking algorithm for CSTNs has only been analyzed with respect to the IR-DC semantics, while the 0-DC semantics was shown to have a serious flaw that the π-DC semantics fixed. Whether the IR-DC semantics had the same flaw and, if so, what the consequences would be for the DC-checking algorithm remained open questions. This paper (1) shows that the IR-DC semantics is also flawed; (2) shows that one of the constraint-propagation rules from the IR-DC-checking algorithm is not sound with respect to the IR-DC semantics; (3) presents a simpler algorithm, called the π-DC-checking algorithm; (4) proves that it is sound and complete with respect to the π-DC semantics; and (5) empirically evaluates the new algorithm.

The proper handling of temporal constraints is crucial in many domains. As a particular challenge, temporal constraints must be also handled when different specific situations happen (conditional constraints) and when some event occurrences can be only observed at run time (contingent constraints). In this paper we introduce Conditional Simple Temporal Networks with Partially Shrinkable Uncertainty (CSTNPSUs), in which contingent constraints are made more flexible (guarded constraints) and they are also specified as conditional constraints. It turns out that guarded constraints require the ability to reason on both kinds of constraints in a seamless way. In particular, we discuss CSTNPSU features through a motivating example and, then, we introduce the concept of controllability for such networks and the related sound checking algorithm.

A Conditional Simple Temporal Network with Uncertainty (CSTNU) is a data structure for representing and reasoning about time. CSTNUs incorporate observation time-points from Conditional Simple Temporal Networks (CSTNs) and contingent links from Simple Temporal Networks with Uncertainty (STNUs). A CSTNU is dynamically controllable (DC) if there exists a strategy for executing its time-points that guarantees the satisfaction of all relevant constraints no matter how the uncertainty associated with its observation time-points and contingent links is resolved in real time. This paper presents the first sound-and-complete DC-checking algorithms for CSTNUs that are based on the propagation of labeled constraints and demonstrates their practicality.

Recent work on Conditional Simple Temporal Networks (CSTNs) has introduced the problem of checking the dynamic consistency (DC) property for the case where the reaction time of an execution strategy to observations is bounded below by some fixed epsilon > 0, the so-called epsilon-DC-checking problem. This paper proves that the epsilon-DC-checking problem for CSTNs can be reduced to the standard DC-checking problem for CSTNs - without incurring any computational cost. Given any CSTN S with k observation time-points, the paper defines a new CSTN S_0 that is the same as S, except that for each observation time-point P? in S: (i) P? is demoted to a non-observation time-point in S_0; and (ii) a new observation time-point P_0?, constrained to occur exactly epsilon units after P?, is inserted into S_0. The paper proves that S is epsilon-DC if and only if S_0 is (standard) DC, and that the application of the epsilon-DC-checking constraint-propagation rules to S is equivalent to the application of the corresponding (standard) DC-checking constraint-propagation rules to S_0. Two versions of these results are presented that differ only in whether a dynamic strategy for S_0 can react instantaneously to observations, or only after some arbitrarily small, positive delay. Finally, the paper demonstrates empirically that building S_0 and DC-checking it incurs no computational cost as the sizes of the instances increase.

We define Access-Controlled Temporal Networks (ACTNs) as an extension of Conditional Simple Temporal Networks with Uncertainty (CSTNUs). CSTNUs are able to handle features such as contingent durations and conditional constraints, and have thus been used to model the temporal constraints of workflows underlying business processes. However, CSTNUs are unable to model users and authorization constraints, and thus cannot model "who can do what, when". ACTNs solve this problem by adding users and authorization constraints that must be considered together with temporal constraints. Dynamic controllability (DC) of ACTNs ensures the existence of an execution strategy, able to assign tasks to authorized users dynamically, satisfying all the relevant authorization constraints no matter what contingent durations turn out to be or what conditional constraints have to be considered. We show that the DC checking can be done via Timed Game Automata and provide experimental results using UPPAAL-TIGA on a concrete real-world case study.

A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network (STN) to include special time-points, called observation time-points. In a CSTN, the agent executing the network controls the execution of every time-point. However, each observation time-point has a unique propositional letter associated with it and, when the agent executes that time-point, the environment assigns a truth value to the corresponding letter. Thus, the agent observes but, does not control the assignment of truth values. A CSTN is dynamically consistent (DC) if there exists a strategy for executing its time-points such that all relevant constraints will be satisfied no matter which truth values the environment assigns to the propositional letters. Alternatively, in a Labeled Simple Temporal Network (Labeled STN) - also called a Temporal Plan with Choice - the agent executing the network controls the assignment of values to the so-called choice variables. Furthermore, the agent can make those assignments at any time. For this reason, a Labeled STN is equivalent to a Disjunctive Temporal Network. This paper incorporates both of the above extensions by augmenting a CSTN to include not only observation time-points but also decision time-points. A decision time-point is like an observation time-point in that it has an associated propositional letter whose value is determined when the decision time-point is executed. It differs in that the agent - not the environment - selects that value. The resulting network is called a CSTN with Decisions (CSTND). This paper shows that a CSTND generalizes both CSTNs and Labeled STNs, and proves that the problem of determining whether any given CSTND is dynamically consistent is PSPACE-complete. It also presents algorithms that address two sub-classes of CSTNDs: (1) those that contain only decision time-points; and (2) those in which all decisions are made before execution begins.

A Simple Temporal Network (STN) consists of time points modeling temporal events and constraints modeling the minimal and maximal temporal distance between them. A Simple Temporal Network with Decisions (STND) extends an STN by adding decision time points to model temporal plans with decisions. A decision time point is a special kind of time point that once executed allows for deciding a truth value for an associated Boolean proposition. Furthermore, STNDs label time points and constraints by conjunctions of literals saying for which scenarios (i.e., complete truth value assignments to the propositions) they are relevant. Thus, an STND models a family of STNs each obtained as a projection of the initial STND onto a scenario. An STND is consistent if there exists a consistent scenario (i.e., a scenario such that the corresponding STN projection is consistent). Recently, a hybrid SAT-based consistency checking algorithm (HSCC) was proposed to check the consistency of an STND. Unfortunately, that approach lacks experimental evaluation and does not allow for the synthesis of all consistent scenarios. In this paper, we propose an incremental HSCC algorithm for STNDs that (i) is faster than the previous one and (ii) allows for the synthesis of all consistent scenarios and related early execution schedules (offline temporal planning). Then, we carry out an experimental evaluation with KAPPA, a tool that we developed for STNDs. Finally, we prove that STNDs and disjunctive temporal networks (DTNs) are equivalent.

A Conditional Simple Temporal Network (CSTN) is a data structure for representing and reasoning about time-points and temporal constraints, some of which may apply only in certain scenarios. The scenarios in a CSTN are represented by conjunctions of propositional literals whose truth values are not known in advance, but instead are observed in real time, during execution. The most important property of a CSTN is whether it is dynamically consistent (DC), that is, whether there exists a strategy for executing its time-points such that all relevant constraints are guaranteed to be satisfied no matter which scenario is incrementally revealed during execution. Prior approaches to determining the dynamic consistency of CSTNs (a.k.a., solving the Conditional Simple Temporal Problem) are primarily of theoretical interest, they have not been realized in practical algorithms. This paper presents a sound-and-complete DC-checking algorithm for CSTNs that is based on the propagation of constraints labeled by propositions. The paper also presents an empirical evaluation of the new algorithm that demonstrates that it may be practical for a variety of applications. This is the first empirical evaluation of any DC-checking algorithm for CSTNs ever reported in the literature.

Temporal networks are data structures for representing and reasoning about temporal constraints on activities. Many kinds of temporal networks have been defined in the literature, differing in their expressiveness. The simplest kinds of networks have polynomial algorithms for determining their consistency or controllability, but corresponding algorithms for more expressive networks (e.g., Those that include observation nodes or disjunctive constraints) have so far been unavailable. However, recent work has introduced a new approach to such algorithms based on translating temporal networks into Timed Game Automata (TGAs) and then using off-the-shelf software to synthesize execution strategies -- or determine that none exist. So far, that approach has only been used on Simple Temporal Networks with Uncertainty, for which polynomial algorithms already exist. This paper extends the temporal-network-to-TGA approach to accommodate observation nodes and disjunctive constraints. Insodoing the paper presents, for the first time, sound and complete algorithms for checking the dynamic controllability of these more expressive networks. The translations also highlight the theoretical relationships between various kinds of temporal networks and the TGA model. The new algorithms have immediate applications in the workflow models being developed to automate business processes, including in the health-care domain.

Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables. We introduce Hyper Temporal Networks (HyTNs), a strict generalization of STNs, to overcome the limitation of considering only conjunctions of constraints. In a Hyper Temporal Network a single temporal constraint may be defined as a set of two or more maximum delay constraints which is satisfied when at least one of these delay constraints is satisfied. As in STNs, a HyTN is consistent when a real value can be assigned to each temporal variable satisfying all the constraints. We show the computational complexity for this generalization and propose effective reduction algorithms for checking consistency of HyTNs unveiling the link with the field of Mean Payoff Games. HyTNs are meant as a light generalization of STNs offering an interesting compromise. On one side, as we show, there exist practical pseudo-polynomial time algorithms for checking consistency and computing feasible schedules for HyTNs. On the other side, HyTNs allow to express natural constraints that cannot be expressed by HySTNs like "trigger off an event exactly d min after the occurrence of the last event in a set".

Workflow technology has emerged as one of the leading technologies in modeling, redesigning, and executing business processes in several different application domains. Among them, the representation and management of health and clinical processes have been attracting a growing interest. Such processes are in general related to the way each health organization provides the required healthcare services. Health and clinical processes underlie the specification and application of clinical protocols, clinical guidelines, clinical pathways, and the most common clinical/administrative procedures. Current workflow systems are lacking in effective management of three general key aspects that are common (not only) in the clinical/health context: data dependencies, exception handling, and temporal constraints. For example, a laparoscopic intervention may need the results of the concurrent bioptic analysis to be properly concluded while exceptional recovery activities have to be performed in case of emergency evidence during standard treatment; however, the successful application of a fibrinolytic therapy requires a maximum delay of 30 min after the admission into the emergency department. In this paper, we propose TNest, a new advanced, structured, and highly modular workflow modeling language that allows one to easily express data dependencies and time constraints during process design, in addition to exception handling and compensation activities. As for temporal constraints, we focus here on temporal controllability which is the capability of executing a workflow for all possible durations of all tasks satisfying all temporal constraints. Moreover, we analyze the computational complexity of the temporal controllability problem in TNest, and we propose a general algorithm to check the controllability. All the features of TNest that have been considered to model clinical pathways from classical clinical guidelines, i.e., those features for the management of STEMI patients, published by the American College of Cardiology/American Heart Association, will be used throughout the paper as a motivating scenario.

Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of minimum and maximum distance constraints between pairs of temporal variables. During construction of an STN, it is possible that the network presents some constraint violations that need to be resolved. One way to solve such violations is to remove a minimal number of constraints, already shown to be an APX-hard problem. Another way is relaxing some constraints in different ways till violations are solved and choosing the best configuration according to one or more criteria. In this paper, assuming that it is possible to increase any constraint bound of an STN paying a constraint-specific cost, we exhibit a polynomial-time algorithm that repairs an STN eliminating all constraint violations at minimum global cost.

Workflow technology has emerged as one of the leading technologies in modeling, redesigning, and executing business processes. The management of temporal aspects in the definition of a workflow process has been considered only recently in the literature. Currently available Workflow Management Systems ( WfMS ) and research prototypes offer a very limited support for the definition, detection, and management of temporal constraints over business processes. In this article, we propose a new advanced workflow conceptual model for expressing time constraints in business processes and we present a general technique to check different levels of temporal consistency for workflow schemata at process design time: since a time constraint can be satisfied in different ways, we propose a classification of temporal workflows according to the way time constraints are satisfied. Such classification can be used to successfully manage flexible workflows at runtime.

The modelling and management of temporal constraints over business processes has received some attention in the past years. Recently, we have introduced and discussed the concept of "controllability" for workflow schemata modelling real world business processes: controllability, originally introduced in the AI community for temporal constraint networks, refers to the capability of executing a workflow for all possible durations of all tasks. In this paper, we first extend the execution strategy proposed by Morris, Muscettola and Vidal in the context of temporal constraint networks, to deal with the execution of business processes in a more suitable way. Then, we discuss and propose a new algorithm to deal with the (dynamic) controllability of an overall workflow schema, where several, possibly disjoint, execution paths are possible, due to the presence of alternative paths in the workflow schema. We show that the presence of several controllable alternative execution paths in a workflow schema does not guarantee that the overall workflow schema is controllable.