LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Languages: English
Types: Article
Subjects: Décision séquentielle, Incertitudes, Préférences, Contraintes, Modèles graphiques algébriques, Architecture de calcul, Décomposition en arbre, Elimination de variables, Programmation dynamique, Recherche arborescente, 000
De nombreux formalismes existent pour modéliser et résoudre des problèmes de décision séquentielle. Certains, comme les réseaux de contraintes, permettent de formuler des problèmes de décision "simples" alors que d’autres peuvent prendre en compte des données plus complexes telles que des incertitudes, des infaisabilités sur les décisions et des utilités. Diverses extensions d’un même formalisme sont de plus souvent introduites de manière à représenter l'incertain et les préférences sous des formes variées (probabilités, possibilités... ; utilités additives ou non...). Chacun de ces formalismes est généralement équipé d’algorithmes dédiés. La première partie de cette thèse définit un cadre de représentation général qui englobe de nombreux formalismes de décision séquentielle dans l'incertain. Ce cadre, nommé cadre PFU pour "Plausibilités-Faisabilité-Utilité", repose sur trois éléments clés : (1) une structure algébrique spécifiant comment combiner et synthétiser des informations ; (2) des fonctions locales portant sur certaines variables et exprimant des incertitudes, des faisabilités ou des utilités; (3) une classe de requêtes sur ces fonctions locales, qui permet de modéliser des scénarios décisionnels variés en termes d’observabilité et de controlabilité. Ce travail de représentation de la connaissance est complété, dans la seconde partie de la thèse, par un travail algorithmique. Les deux types d’algorithmes développés sont des algorithmes de type élimination de variables et de type recherche arborescente avec bornes et techniques de mémorisation. Nous montrons également qu’il est possible d’utiliser une architecture de calcul générale qui exploite la structure des requêtes considérées pour les décomposer en calcul locaux. En unifiant des formalismes variés, le cadre PFU apporte une meilleure compréhension des liens entre certains formalismes. Il n’est pas qu’un cadre unificateur étant donné que certaines de ces intanciations correspondent à de nouveaux formalismes. Enfin, il permet de définir des algorithmes génériques qui sont soit des généralisations d'algorithmes existants soit des techniques nouvelles applicables directement aux formalismes couverts. Numerous formalisms and dedicated algorithms have been designed to model and solve decision making problems. Some formalisms, such as constraint networks, can express “simple” decision problems, While, others can take into account uncertainties, unfeasible decisions, and utilities. Even in a single formalism, several variants are often proposed to model different types of uncertainty (probability, possibility...) or utility (additive or not). In the first part of this thesis, We introduce a generic algebraic framework that encompasses a large number of such formalisms: (1) we first adapt existing algebraic structures for representing uncertainty and expected utility in order to deal with generic forms of sequential decision making; on these structures, we introduce composite graphical models that express information via variables linked by “local” functions; on these graphical models, we define a simple class of queries which can represent various scenarios in terms of ohservabilities and controllabilities. These three elements define the Plausibility-Feasibility Utility (PFU) framework. This work on knowledge representation is completed by the second part of this thesis, which focuses on algorithms for answering PFU queries. Two types of algorithms are introduced: variable elimination algorithms, which can be more or less sophisticated depending on whether they finely analyze the structure of the queries they answer to, and tree search algorithms, which can be more or less advanced depending on whether they use bounds or recording. We also show that queries can be answered using a generic architecture of local computations called the multi-operator cluster DAG architecture. Theoretical complexity results based on tree-width are also provided, as well as a generic solver that answers PFU queries. The PFU framework provides a better understanding of the links between existing formalisms, it covers yet unpublished frameworks, and it unifies formalisms such as quantified booleans formulas and influence diagrams. The algorithms proposed are either generalizations of existing algorithms, or new techniques directly applicable to all subsumed formalisms.
  • No references.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article