Procédures de décision par élicitation incrémentale de préférences en optimisation multicritère, multi-agents et dans l'incertain / Nawal Benabbou ; sous la direction de Patrice Perny

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Systèmes d'aide à la décision

Optimisation combinatoire

Décision multicritère

Classification Dewey : 004

Perny, Patrice (19..-....) (Directeur de thèse / thesis advisor)

Maudet, Nicolas (1972-....) (Président du jury de soutenance / praeses)

Lang, Jérôme (1965-....) (Rapporteur de la thèse / thesis reporter)

Pirlot, Marc (Rapporteur de la thèse / thesis reporter)

Dhaenens, Clarisse (Membre du jury / opponent)

Mousseau, Vincent (Membre du jury / opponent)

Vanderpooten, Daniel (Membre du jury / opponent)

Université Pierre et Marie Curie (Paris ; 1971-2017) (Organisme de soutenance / degree-grantor)

École doctorale Informatique, télécommunications et électronique de Paris (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire d'informatique de Paris 6 (1997-....) (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Les travaux menés dans cette thèse s'inscrivent dans le cadre de la théorie de la décision algorithmique, domaine de recherche à la croisée de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle. Notre objectif dans cette thèse est de concevoir des algorithmes efficaces pour la résolution de problèmes de décision dans des environnements complexes (multicritère, multi-agents, incertain). Nous nous intéressons d'une part à l'élicitation des préférences fondée sur des modèles décisionnels et d'autre part à l'exploitation de ces préférences pour la recherche des solutions optimales sur des espaces définis de manière explicite ou implicite (optimisation combinatoire). Pour la résolution de problèmes combinatoires, nous proposons et étudions une nouvelle approche, consistant à combiner l'élicitation incrémentale des préférences et l'exploration implicite des solutions potentielles. L'intuition sous-jacente est d'utiliser l'exploration des solutions potentielles pour identifier des questions informatives tout en exploitant les réponses obtenues pour mieux focaliser la recherche sur les solutions préférées. Cette approche nous a conduit à proposer des procédures de décision par élicitation incrémentale pour les problèmes de recherche dans un graphe d'états multi-objectifs, les problèmes de chemins optimaux et d'arbre couvrants dans les graphes multicritères, les problèmes de sac à dos multi-agents et les problèmes de décision séquentielle dans l'incertain. Nous établissons des résultats théoriques garantissant la correction des algorithmes proposés et présentons des tests numériques montrant leur efficacité pratique.

Résumé / Abstract : This thesis work falls within the area of algorithmic decision theory which is at the junction of decision theory, operations research and artificial intelligence. Our aim is to produce algorithms allowing the fast resolution of decision problems in complex environments (multiple criteria, multi-agents, uncertainty). This work focuses on decision-theoretic elicitation and uses preferences to efficiently determine the best solutions among a set of alternatives explicitly or implicitly defined (combinatorial optimization). For combinatorial optimization problems, we propose and study a new approach consisting in interleaving incremental preference elicitation and preference-based search. The idea is to use the exploration to identify informative preference queries while exploiting answers to better focus the search on the preferred solutions. This approach leads us to propose incremental elicitation procedures for multi-objective state-space search problems, multicriteria shortest path problems, multicriteria minimum spanning tree problems, multi-agents knapsack problems and sequential decision problems under uncertainty. We provide theoretical guarantees on the correctness of the proposed algorithms and we present numerical tests showing their practical efficiency.