Academic literature on the topic 'Élicitation incrémentale'

Cette thèse s'intéresse à la résolution de problèmes de décision sur domaine combinatoire par des méthodes d'élicitation incrémentale des préférences basée le regret pour l'optimisation interactive. On se situe à l'intersection de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle, en théorie de la décision algorithmique. On suppose que les préférences du décideur peuvent être représentées par une fonction de scalarisation paramétrée (somme pondérée, OWA et intégrale de Choquet), mais que les paramètres (par exemple, le jeu de poids) ne sont pas connus au départ. L'apprentissage actif des paramètres est entremêlé à la résolution du problème dans le but d'apprendre seulement la part d'information sur ce paramètre qui est utile pour résoudre le problème donnée. L'originalité de ces travaux réside dans la conception de méthodes fondées sur la recherche heuristique couplée à l'élicitation incrémentale pour déterminer la meilleure solution du décideur. Nous proposons d'abord deux méthodes pour résoudre des problèmes d'optimisation combinatoire multi-objectifs avec des préférences imprécises, la première basée sur la recherche locale et la seconde sur un algorithme génétique. Nous proposons ensuite deux approches permettant l'élicitation d'une fonction d'ensemble linéaire, sous-modulaire et super-modulaire avec la construction d'un sous-ensemble indépendant optimal soumis à une contrainte de matroïde. La première approche est basée sur un algorithme glouton et l'autre sur la recherche locale. Afin de démontrer l'efficacité pratique de nos approches, nos algorithmes sont testés numériquement sur différents problèmes et évalués en termes de temps de calcul, de nombre de requêtes et d'erreur empirique
This thesis is concerned with solving combinatorial domain decision problems using incremental regret-based preference elicitation methods for interactive optimization. It is situated at the intersection of decision theory, operations research and artificial intelligence, in algorithmic decision theory. It is assumed that the decision maker's preferences can be represented by a parameterised scalarization function (weighted sum, OWA and Choquet integral), but the parameters (e.g. set of weights) are not known at the beginning. The active learning of the parameters is intertwined with the solution of the problem in order to learn only that part of the information about the parameter that is useful to solve the given problem. The originality of this work lies in the use of methods based on heuristic search coupled with incremental elicitation to determine the best solution for the decision maker. In first we propose two methods for solving multi-objective combinatorial optimisation problems with imprecise preferences, the first based on local search and the second on a genetic algorithm. We then propose two approaches for the elicitation of a linear, submodular and super-modular set function with the construction of an optimal independent subset subject to a matroid constraint. The first approach is based on a greedy algorithm and the other on local search. In order to demonstrate the practical effectiveness of our approaches, our algorithms are numerically tested on different problems and evaluated in terms of computation time, number of queries and empirical error

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
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

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
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

Un drone totalement autonome est un aéronef sans pilote humain à bord. Il est donc capable d'accomplir une mission sans l'intervention d'un opérateur humain et de prendre des décisions de façon totalement autonome. Cela sous-entend que l'opérateur au sol doit avoir une confiance élevée dans les décisions prises par le drone. L'objectif principal de cette thèse est donc de proposer un moteur de décisions à embarquer dans le drone autonome qui garantit un niveau de confiance élevé de l'opérateur dans la capacité du drone à prendre les "bonnes" décisions. Pour cela nous proposons un moteur de décisions multi-niveaux composé de deux niveaux de décisions principaux. Le premier permet de surveiller l'état du drone et de son environnement pour détecter les événements qui peuvent perturber la réalisation de la mission et déclencher la prise de décision du second niveau. Celui-ci une fois déclenché permet de choisir une action de haut niveau (atterrir, continuer, ...) la mieux adaptée à la situation courante parmi un ensemble d'actions possibles. Ce moteur intègre aussi les préférences d'un opérateur en utilisant des modèles d'Aide Multi-Critère à la Décision. Ces modèles nécessitent une phase en amont de la mission, où les préférences de l'opérateur sont élicitées, avant d'être intégrées dans le drone. Pour réduire l'effort cognitif de l'opérateur pendant cette phase, nous proposons un processus d'élicitation incrémental pendant lequel les questions soumises à l'opérateur sont déduites des réponses précédentes. Cela nous permet de déterminer un modèle représentant fidèlement ses préférences, tout en minimisant le nombre de questions
A fully autonomous unmanned aerial vehicle (UAV) is an aircraft without a human pilot on board. It is consequently able to accomplish a mission without the intervention of a human operator and to make decisions in a totally autonomous way. This implies that the ground operator must have a high level of confidence in the decisions made by the UAV.The main objective of this thesis is therefore to propose a decision engine to be embedded in the autonomous UAV that guarantees a high level of operator confidence in the UAV's ability to make the "right" decisions. For this purpose, we propose a multi-level decision engine composed of two main decision levels. The first one monitors the state of the UAV and its environment to detect events that can disrupt the mission’s execution and trigger the second level. Once triggered, it allows to choose a highlevel action (landing, continuing,...) best adapted to the current situation from a set of possible actions. This engine also integrates the operator's preferences by using Multi-Criteria Decision Aiding models. They require a preliminary phase before the mission, where the operator's preferences are elicited, before being integrated into the UAV. To reduce the operator's effort during this phase, we propose an incremental elicitation process during which the questions submitted to the operator are deduced from the previous answers. This allows us to determine a model that accurately represents his or her preferences, while minimizing the number of questions

Les travaux effectués durant cette thèse s'inscrivent dans le cadre de la théorie de la décision algorithmique, domaine au carrefour de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle. Cette thèse vise à concevoir des méthodes d'optimisation interactive fondées sur l'élicitation incrémentale des préférences pour la prise de décision multicritère, multi-agents ou dans le risque. Nous nous intéressons plus précisément à l'élicitation incrémentale des paramètres de fonctions d'agrégation qui consiste à alterner questions préférentielles permettant de réduire l'incertitude concernant la valeur des paramètres modélisant les préférences particulières du décideur, et exploration de l'espace des solutions, jusqu'à pouvoir déterminer une recommandation de bonne qualité. L'intérêt d'alterner phases de questions et phases d'exploration est double: d'une part, les informations préférentielles récoltées durant une phase d'élicitation permettent de mieux focaliser la phase d'exploration suivante sur les solutions les plus intéressantes pour le décideur; d'autre part, l'exploration de l'espace des solutions permet de guider le choix des questions de manière à ce qu'elles soient les plus informatives possible. Nous introduisons dans cette thèse des méthodes d'élicitation dans différents contextes. Dans un premier temps, nous nous intéressons à des fonctions d'agrégation non-linéaires pour modéliser les préférences du décideur sur un ensemble combinatoire d'alternatives. Nous nous intéressons ensuite à la conception de méthodes d'élicitation prenant en compte la possibilité de la présence d'incohérences dans les réponses du décideur, d'abord sur domaine explicite, puis sur domaine combinatoire. Les algorithmes introduits sont génériques et peuvent s'appliquer à différents problèmes de choix multi-objectifs
This thesis work falls within the area of algorithmic decision theory, a research domain at the crossroad of decision theory, operations research and artificial intelligence. The aim is to produce interactive optimization methods based on incremental preference elicitation in decision problems involving several criteria, opinions of agents or scenarios. Preferences are represented by general decision models whose parameters must be adapted to each decision problem and each decision maker. Our methods interleave the elicitation of parameters and the exploration of the solution space in order to determine the optimal choice for the decision maker. The idea behind this is to use information provided by the elicitation to guide the exploration of the solution space and vice versa. In this thesis, we introduce new incremental elicitation methods for decision making in different contexts : first for decision making in combinatorial domains when the decision models are non-linear, and then in a setting where one takes into account the possibility of inconsistencies in the answers of te decision maker. All the algorithms that we introduce are general and can be applied to a wide range of multiobjective decision problems

Cette thèse se situe dans le cadre de la théorie de la décision algorithmique, domaine de recherche à l'intersection de la théorie de la décision, de l'intelligence artificielle et de la recherche opérationnelle. Nous nous intéressons à la prise en compte de comportements sophistiqués dans des environnements complexes (décision multicritère, décision collective, décision dans le risque et l'incertain). Nous proposons d'abord des méthodes d'optimisation multi-objectifs sur domaine implicite lorsque les préférences sont représentées par des modèles dépendants du rang (intégrale de Choquet, bipolar OWA, Cumulative Prospect Theory et intégrale de Choquet bipolaire). Ces méthodes reposent sur des approches de programmation mathématique et d'algorithmique discrète. Ensuite, nous présentons des méthodes d'élicitation incrémentale des paramètres de modèles dépendants du rang permettant de prendre en compte la présence d'un point de référence dans les préférences d'un décideur (bipolar OWA, Cumulative Prospect Theory, intégrale de Choquet avec capacités et bicapacités). Finalement, nous abordons la modification structurelle de solutions sous contraintes (coût, qualité) dans des méthodes de tri à plusieurs points de référence. Les différentes approches proposées dans cette thèse ont été testées et nous présentons les résultats numériques obtenus afin d'illustrer leur efficacité pratique
This thesis work falls within the research field of algorithmic decision theory, which is defined at the junction of decision theory, artificial intelligence and operations research. This work focuses on the consideration of sophisticated behaviors in complex decision environments (multicriteria decision making, collective decision making and decision under risk and uncertainty). We first propose methods for multi-objective optimization on implicit sets when preferences are represented by rank-dependent models (Choquet integral, bipolar OWA, Cumulative Prospect Theory and bipolar Choquet integral). These methods are based on mathematical programming and discrete algorithmics approaches. Then, we present methods for the incremental parameter elicitation of rank-dependent model that take into account the presence of a reference point in the decision maker's preferences (bipolar OWA, Cumulative Prospect Theory, Choquet integral with capacities and bicapacities). Finally, we address the structural modification of solutions under constraints (cost, quality) in multiple reference point sorting methods. The different approaches proposed in this thesis have been tested and we present the obtained numerical results to illustrate their practical efficiency