Un cadre algébrique général pour représenter et résoudre des problèmes de décision séquentielle avec incertitudes, faisabilités et utilités

Other literature type English OPEN
Pralet, Cédric (2006)
  • Subject: 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.
Share - Bookmark