Dynamic Controllability of Temporal Plans in Uncertain and Partially Observable Environments - Archive ouverte HAL
[go: up one dir, main page]

Article Dans Une Revue Journal of Artificial Intelligence Research Année : 2023
Dynamic Controllability of Temporal Plans in Uncertain and Partially Observable Environments
1 LAAS-RIS - Équipe Robotique et InteractionS (France)
"> LAAS-RIS - Équipe Robotique et InteractionS
2 INSA Toulouse - Institut National des Sciences Appliquées - Toulouse (135, avenue de Rangueil - 31077 Toulouse cedex 4 - France)
"> INSA Toulouse - Institut National des Sciences Appliquées - Toulouse
3 ARC - NASA Ames Research Center (Moffett Field, California 94035 - États-Unis)
"> ARC - NASA Ames Research Center

Résumé

The formalism of Simple Temporal Networks (STNs) provides methods for evaluating the feasibility of temporal plans. The basic formalism deals with the consistency of quantitative temporal requirements on scheduled events. This implicitly assumes a single agent has full control over the timing of events. The extension of Simple Temporal Networks with Uncertainty (STNU) introduces uncertainty into the timing of some events. Two main approaches to the feasibility of STNUs involve (1) where a single schedule works irrespective of the duration outcomes, called Strong Controllability, and (2) whether a strategy exists to schedule future events based on the outcomes of past events, called Dynamic Controllability. Case (1) essentially assumes the timing of uncertain events cannot be observed by the agent while case (2) assumes full observability. The formalism of Partially Observable Simple Temporal Networks with Uncertainty (POSTNU) provides an intermediate stance between these two extremes, where a known subset of the uncertain events can be observed when they occur. A sound and complete polynomial algorithm to determining the Dynamic Controllability of POSTNUs has not previously been known; we present one in this paper. This answers an open problem that has been posed in the literature. The approach we take factors the problem into Strong Controllability micro-problems in an overall Dynamic Controllability macro-problem framework. It generalizes the notion of labeled distance graph from STNUs. The generalized labels are expressed as max/min expressions involving the observables. The paper introduces sound generalized reduction rules that act on the generalized labels. These incorporate tightenings based on observability that preserve dynamic viable strategies. It is shown that if the generalized reduction rules reach quiescence without exposing an inconsistency, then the POSTNU is Dynamically Controllable (DC). The paper also presents algorithms that apply the reduction rules in an organized way and reach quiescence in a polynomial number of steps if the POSTNU is Dynamically Controllable. Remarkably, the generalized perspective leads to a simpler and more uniform framework that applies also to the STNU special case. It helps illuminate the previous methods inasmuch as the max/min label representation is more semantically clear than the ad-hoc upper/lower case labels previously used.
Fichier principal
Vignette du fichier
postnu-dc.pdf (547.28 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Licence

Dates et versions

hal-04174986 , version 1 (01-08-2023)

Licence

Identifiants

Citer

Arthur Bit-Monnot, Paul Morris. Dynamic Controllability of Temporal Plans in Uncertain and Partially Observable Environments. Journal of Artificial Intelligence Research, 2023, 77, pp.1311-1369. ⟨10.1613/jair.1.13065⟩. ⟨hal-04174986⟩
78 Consultations
75 Téléchargements

Altmetric

Partager

More