AAAI Publications, Twenty-Fifth International Conference on Automated Planning and Scheduling

Font Size: 
Optimising Bounds in Simple Temporal Networks with Uncertainty under Dynamic Controllability Constraints
Jing Cui, Peng Yu, Cheng Fang, Patrik Haslum, Brian C Williams

Last modified: 2015-04-08


Dynamically controllable simple temporal networks with uncertainty (STNU) are widely used to represent temporal plans or schedules with uncertainty and execution flexibility. While the problem of testing an STNU for dynamic controllability is well studied, many use cases — for example, problem relaxation or schedule robustness analysis — require optimising a function over STNU time bounds subject to the constraint that the network is dynamically controllable. We present a disjunctive linear constraint model of dynamic controllability, show how it can be used to formulate a range of applications, and compare a mixed-integer, a non-linear programming, and a conflict-directed search solver on the resulting optimisation problems. Our model also provides the first solution to the problem of optimisation over a probabilistic STN subject to dynamic controllability and chance constraints.


Temporal reasoning with uncertainty; optimization under dynamic controllability constraints; schedule robustness; optimization under chance-constraints

Full Text: PDF