Uncertainty in Soft Temporal Constraint Problems:A General Framework and Controllability Algorithms for the Fuzzy Case

In real-life temporal scenarios, uncertainty and preferences are often essential and coexisting aspects. We present a formalism where quantitative temporal constraints with both preferences and uncertainty can be defined. We show how three classical notions of controllability (that is, strong, weak,...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2011-10
Main Authors: Rossi, F, Venable, K B, Yorke-Smith, N
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Controllability
Fuzzy control
Polynomials
Uncertainty
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In real-life temporal scenarios, uncertainty and preferences are often essential and coexisting aspects. We present a formalism where quantitative temporal constraints with both preferences and uncertainty can be defined. We show how three classical notions of controllability (that is, strong, weak, and dynamic), which have been developed for uncertain temporal problems, can be generalized to handle preferences as well. After defining this general framework, we focus on problems where preferences follow the fuzzy approach, and with properties that assure tractability. For such problems, we propose algorithms to check the presence of the controllability properties. In particular, we show that in such a setting dealing simultaneously with preferences and uncertainty does not increase the complexity of controllability testing. We also develop a dynamic execution algorithm, of polynomial complexity, that produces temporal plans under uncertainty that are optimal with respect to fuzzy preferences.
ISSN:2331-8422
DOI:10.48550/arxiv.1110.2212