Links

Tools

Export citation

Search in Google Scholar

Weak and Dynamic Controllability of Temporal Problems with Disjunctions and Uncertainty

Journal article published in 2010 by K. Brent Venable, Michele Volpato, Bart Peintner, Neil Yorke-Smith ORCID
This paper was not found in any repository; the policy of its publisher is unknown or unclear.
This paper was not found in any repository; the policy of its publisher is unknown or unclear.

Full text: Unavailable

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

Abstract

The Temporal Constraint Satisfaction Problem with Uncer-tainty (TCSPU) and its disjunctive generalization, the Dis-junctive Temporal Problem with Uncertainty (DTPU), are quantitative models for temporal reasoning that account si-multaneously 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 con-straints; 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 Control-lability. We present two sound and complete algorithms for checking Weak Controllability of DTPUs. The first algorithm needs to examine only a limited number of scenarios, but op-erates only on a restricted class of problems. The second al-gorithm 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.