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

• Soutenue le : 17/11/2006 - Prix national de thèse ASTI 2007 (ANR)..
• Directeurs de thèse : Thomas Schiex, Gérard Verfaillie (ONERA, Toulouse)
• Ecole doctorale : École Nationale Supérieure de l’Aéronautique et de l’Espace
• Manuscrit : Manuscrit (Version courte en français)
• Manuscript : Manuscrit (Version longue en anglais)

Résumé : 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 capables de répondre à certaines requêtes. 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é-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 considérer des scénarios décisionnels variés en termes d’observabilité et de contrôlabilité. Ce travail de représentation de la connaissance est complété, dans la seconde partie de la thèse, par un travail algorithmique. Cette approche duale reflète l’ambition de construire un cadre algébrique général permettant à la fois de représenter des problèmes de décision variés et de les résoudre. Les deux types d’algorithmes développés sont des algorithmes de type élimination de variables ou 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, tels que les formules booléennes quantifiées et les diagrammes d’influence, le cadre PFU apporte une meilleure compréhension des formalismes existants et des liens qui existent entre eux. 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 correspondent soit à des généralisations d’algorithmes existants soit à des nouvelles techniques applicables directement à tous les formalismes couverts.