Dynamic controllability of controllable conditional temporal problems with uncertainty

Jing Cui, Patrik Haslum

    Research output: Contribution to journalArticlepeer-review

    2 Citations (Scopus)

    Abstract

    Dynamic Controllability (DC) of a Simple Temporal Problem with Uncertainty (STPU) uses a dynamic decision strategy, rather than a fixed schedule, to tackle temporal uncertainty. We extend this concept to the Controllable Conditional Temporal Problem with Uncertainty (CCTPU), which extends the STPU by conditioning temporal constraints on the assignment of controllable discrete variables. We define dynamic controllability of a CCTPU as the existence of a strategy that decides on both the values of discrete choice variables and the scheduling of controllable time points dynamically. This contrasts with previous work, which made a static assignment of choice variables and dynamic decisions over time points only. We propose an algorithm to find such a fully dynamic strategy. The algorithm computes the “envelope” of outcomes of temporal uncertainty in which a particular assignment of discrete variables is feasible, and aggregates these over all choices. When an aggregated envelope covers all uncertain situations of the CCTPU, the problem is dynamically controllable. However, the algorithm is complete only under certain assumptions. Experiments on an existing set of CCTPU benchmarks show that there are cases in which making both discrete and temporal decisions dynamically it is feasible to satisfy the problem constraints while assigning the discrete variables statically it is not.

    Original languageEnglish
    Pages (from-to)445-495
    Number of pages51
    JournalJournal of Artificial Intelligence Research
    Volume64
    DOIs
    Publication statusPublished - 1 Feb 2019

    Fingerprint

    Dive into the research topics of 'Dynamic controllability of controllable conditional temporal problems with uncertainty'. Together they form a unique fingerprint.

    Cite this