Modeling Oracles in Simple Temporal Networks with Uncertainty

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.