Introduction

Constraint-based temporal reasoning has been widely used in many applications across many domains. Over the years, different formalisms have been presented to address specific requirements that frequently arise in real-world applications. The most commonly used formalism is probably the Simple Temporal Network (STN), in which a set of real-valued variables, called timepoints, are subject to binary difference constraints [1]. Timepoints represent the occurrence of events: when a timepoint is assigned a value t, the event occurs at instant t, or the timepoint is executed at time t. The binary difference constraints represent the temporal constraint between a pair of timepoints (X-Y ≤ 10 means that X can occur 10-time units after Y at most).

The two main problems for STNs are consistency and dispatchability.

The consistency problem asks whether an STN admits one or more timepoint assignments that satisfy all temporal constraints. In a consistent STN, each timepoint has a range of possible execution instants, called its time-window.

The dispatchability problem asks for a dynamic schedule of the timepoints, i.e., a schedule that, after a timepoint is executed at an allowed instant, updates the time-windows of the remaining unexecuted timepoints while guaranteeing that all timepoints can be executed in order as time flows.

Recently, a significant amount of research has focused on temporal reasoning in the presence of uncertainty.
Temporal uncertainty arises, for example, when the durations of some activities (i.e., some temporal intervals) are not controlled by the executor of the network, but are only observed in real time as the activities complete. In such settings, the executor seeks a dynamic strategy for executing the controllable timepoints so that all relevant constraints are necessarily satisfied, no matter how the uncertain durations turn out. To accommodate this kind of uncertainty, STNs have been augmented to include contingent links, where each contingent link represents an interval whose duration is bounded but uncontrollable; the resulting network is called a Simple Temporal Network with Uncertainty (STNU) [2].
The most important property of an STNU is whether it is dynamically controllable (DC)—that is, whether there exists a strategy for executing the controllable timepoints such that all relevant constraints are guaranteed to be satisfied no matter how the durations of the contingent links turn out.

Although STNUs have been successful in some domains, many domains require a richer set of constraints.
For example, in the healthcare domain, where workflow management systems are being developed to automate medical-treatment processes, medical tests for a given patient frequently generate information in real time that can affect which pathway the patient will follow [3].
The system must guarantee that any possible execution of the workflow strictly satisfies all specified temporal constraints no matter which test outcomes are observed. A set of test outcomes is called a scenario. The Conditional Simple Temporal Network (CSTN) model represents temporal constraints in conjunction with scenarios. In this way, it is possible to specify, for each possible scenario, a proper set of constraints that must be satisfied if the scenario occurs in an execution of the network. For CSTNs, several studies have established results and algorithms for handling CSTNs properly [8], [9], [11], [12], [13], [15] [16].

The Conditional Simple Temporal Network with Uncertainty (CSTNU) model extends the CSTN model by allowing the representation of contingent links. Several works have established properties and possible applications of CSTNUs [5], [6], [7], [10], [14].

The Conditional Simple Temporal Network with Partially Shrinkable Uncertainty (CSTNPSU) model extends the CSTNU model by allowing each contingent link to have a wider range that can be slightly shrunk at design or execution time to obtain a successful execution.

This open-source project provides:

• a Java library for representing and checking temporal constraint networks of the types described above: (C)STN(PS)(U);
• a graphical Java editor for designing and checking (C)STN(PS)(U) networks from scratch.

If you use this tool in your research, please cite this project by including this website and the SoftwareX paper [17].

Benchmarks

Some algorithm implementations in the tool have been tested on benchmark instances. In general, each benchmark consists of temporal networks randomly generated according to specific criteria. For each benchmark, we describe the generation criteria, the characteristics of each random instance, and the DC/NOT-DC property.

An analysis of the benchmarks and the algorithm performance obtained on them is available at Benchmarks.

The directory containing benchmarks is https://profs.scienze.univr.it/~posenato/software/benchmarks/

The articles in which these benchmarks are presented and used are [9] [10] [11] [12] [13] [14] [15] [16].

Bibliography

[1] R. Dechter, I. Meiri, and J. Pearl, “Temporal constraint networks,” Artificial Intelligence, vol. 49, pp. 61–95, 1991.

[2] P. Morris, N. Muscettola, and T. Vidal, “Dynamic control of plans with temporal uncertainty,” in 17th International Joint Conference on Artificial Intelligence (IJCAI-01), Morgan Kaufmann, 2001, pp. 494–499.

[3] C. Combi, M. Gambini, S. Migliorini, and R. Posenato, “Representing business processes through a temporal data-centric workflow modeling language: An application to the management of clinical pathways,” Systems, Man, and Cybernetics: Systems, IEEE Transactions on,  2014. Available online: https://ieeexplore.ieee.org/xpl/abstractReferences.jsp?arnumber=6733362

[4] L. Hunsberger, R. Posenato, and C. Combi, “The Dynamic Controllability of Conditional STNs with Uncertainty,” in Workshop on Planning and Plan Execution for Real-World Systems: Principles and Practices (PlanEx) @ ICAPS-2012, Atibaia, Jun. 2012, pp. 1–8. Available online: https://arxiv.org/abs/1212.2005

[5] C. Combi, L. Hunsberger, and R. Posenato, “An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty,” in Proc. of the 5th Int. Conf. on Agents and Art. Int. (ICAART-2013), vol. 2, pp. 144–156, SCITEPRESS, Feb. 2013

[6] C. Combi, L. Hunsberger, and R. Posenato, “An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty-revisited,” in Agents and Artificial Intelligence, vol. 449 of Communications in Computer and Information Science, pp. 314–331, Springer-Verlag, 2014. Available online: https://doi.org/10.1007/978-3-662-44440-5_19

[7] A. Cimatti, L. Hunsberger, A. Micheli, R. Posenato, and M. Roveri, “Sound and complete algorithms for checking the dynamic controllability of temporal networks with uncertainty, disjunction and observation,” in 21st International Symposium on Temporal Representation and Reasoning (TIME 2014), pp. 27–36, IEEE Computer Society, Sept. 2014. Available online: https://doi.org/10.1109/TIME.2014.21

[8] L. Hunsberger, R. Posenato, and C. Combi, “A Sound-and-Complete Propagation-based Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks,” in 22nd International Symposium on Temporal Representation and Reasoning (TIME 2015), pp. 4–18, IEEE Computer Society, Sept. 2015. Available online: https://doi.org/10.1109/TIME.2015.26

[9] L. Hunsberger and R. Posenato, “Checking the Dynamic Consistency of Conditional Simple Temporal Networks with Bounded Reaction Times”, in ICAPS 2016: International Conference on Automated Planning and Scheduling (ICAPS 2016), pp. 175–183, 2016. Available online: https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13108

[10] A. Cimatti, L. Hunsberger, A. Micheli, R. Posenato, and M. Roveri, ‘Dynamic controllability via Timed Game Automata’, Acta Inform., vol. 53, no. 6–8, pp. 681–722, Oct. 2016. Available online: https://dx.doi.org/10.1007/s00236-016-0257-2

[11] M. Cairo, L. Hunsberger, R. Posenato, and R. Rizzi, ‘A Streamlined Model of Conditional Simple Temporal Networks – Semantics and Equivalence Results’, in 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), 2017, vol. 90, no. 10, pp. 1–10. Available online: https://dx.doi.org/10.4230/LIPIcs.TIME.2017.10

[12] M. Cairo, C. Combi, C. Comin, L. Hunsberger, R. Posenato, R. Rizzi, M. Zavatteri, ‘Incorporating Decision Nodes into Conditional Simple Temporal Networks’, in 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), 2017, vol. 90, p. 9:1–9:18.
Available online: https://dx.doi.org/10.4230/LIPIcs.TIME.2017.9

[13] L. Hunsberger and R. Posenato, ‘Simpler and Faster Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks’, in Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018, pp. 1324–1330. Available online: https://dx.doi.org/10.24963/ijcai.2018/184

[14] L. Hunsberger, R. Posenato, ‘Sound-and-Complete Algorithms for Checking the Dynamic Controllability of Conditional Simple Temporal Networks with Uncertainty, in 25th International Symposium on Temporal Representation and Reasoning (TIME 2018), 2018, vol. 120, no. 14, p. 1–17.
Available online: https://dx.doi.org/10.4230/LIPIcs.TIME.2018.14

[15] L. Hunsberger, R. Posenato, ‘Reducing ε-DC Checking for Conditional Simple Temporal Networks to DC Checking’, in 25th International Symposium on Temporal Representation and Reasoning (TIME 2018), 2018, vol. 120, no. 15, pp. 1–15. Available online: https://dx.doi.org/10.4230/LIPIcs.TIME.2018.15

[16] L. Hunsberger and R. Posenato, ‘Faster Dynamic-Consistency Checking for Conditional Simple Temporal Networks’, in ICAPS 2020: International Conference on Automated Planning and Scheduling (ICAPS 2020), 2020.

[17] R. Posenato, ‘CSTNU Tool: A Java library for checking temporal networks’, SoftwareX 17, 100905. 2022. https://doi.org/10.1016/j.softx.2021.100905