Weak and Dynamic Controllability of Temporal Problems with Disjunctions and Uncertainty

Venable, K. B.; Volpato, M.; Peintner, B.; and Yorke-Smith, N. Weak and Dynamic Controllability of Temporal Problems with Disjunctions and Uncertainty. Proceedings of ICAPS'10 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, Toronto, Canada, May 2010.

Abstract: The Temporal Constraint Satisfaction Problem with Uncertainty (TCSPU) and its disjunctive generalization, the Disjunctive Temporal Problem with Uncertainty (DTPU), are quantitative models for temporal reasoning that account simultaneously for disjunctive constraints and for events not under the control of the executing agent. Such a problem is Weakly Controllable if in each possible scenario the agent can find a decision for that scenario that satisfies all the constraints; further, a problem is Dynamically Controllable if the agent can build a consistent decision online, as the scenario is incrementally revealed. We first consider Weak Controllability. We present two sound and complete algorithms for checkingWeak Controllability of DTPUs. The first algorithm needs to examine only a limited number of scenarios, but operates only on a restricted class of problems. The second algorithm is fully general, but is more expensive in terms of space. We then consider Dynamic Controllability. We present a complete algorithm for testing this property for TCSPUs. Complexity results are presented for all three algorithms.

PDF (330K) | Bibtex entry

Workshop homepage