Handling contingency in temporal constraint networks: from consistency to controllabilities
Titel:
Handling contingency in temporal constraint networks: from consistency to controllabilities
Auteur:
Vidal, Thierry
Verschenen in:
Journal of experimental & theoretical artificial intelligence
Paginering:
Jaargang 11 (1999) nr. 1 pagina's 23-45
Jaar:
1999-01-01
Inhoud:
Temporal Constraint Networks (TCN) allow one to express minimal and maximal durations between time-points. Although being used in many research areas, this model disregards the contingent nature of some constraints, whose effective duration cannot be decided by the system but is provided by the external world. We propose an extension of TCN based on the definition of the Simple Temporal Problem under Uncertainty (STPU) in which the classical network consistency property must be redefined in terms of controllability: intuitively, we would like to say that a network is controllable iff it is consistent in any situation (i.e. any assignment of the whole set of contingent intervals) that may arise in the external world. Three levels of controllability must be distinguished, namely the Strong, the Weak and the Dynamic ones. This paper provides a full characterization of those properties and their usefulness in practice, and proposes algorithms for checking them. Complexity issues and tractable equivalence classes are only partially tackled, since it is still the topic of on-going work. All the same, hardness is discussed and argued, giving evidence for the general intractability of Dynamic controllability, which is the most commonly required property in domains such as planning or scheduling.
Tijdschrift beschrijving