Search

This paper describes our work concerning the dynamic formation and reformation of teams in the context of multi-agent planning under uncertainty. We seek to develop a fully decentralized system which uses solely the individual observations of each of its agents in order to adjust its own composition in regards to the evolution of the task at hand. We present our model along with some of its interesting structural properties. We also show how our model generalizes the definitions usually encountered within the realm of cooperative game theory to the stochastic case., Notre travail concerne la formation et la reformation dynamique d'équipes dans le contexte de la planification multi-agent sous incertitude. Nous cherchons à concevoir un système décentralisé qui repose sur les observations individuelles de chacun de ses agents pour ajuster sa composition à l'évolution de la situation. Nous présentons notre modèle ainsi que quelques unes de ses propriétés structurelles intéressantes. Nous montrons également comme notre modèle généralise les définitions fréquemment rencontrées en théorie des jeux coopérative au cas stochastique.

International audience; Possibilistic decision theory has been proposed twenty years ago and has had several extensions since then. Even though ap-pealing for its ability to handle qualitative decision problems, possibilistic decision theory suffers from an important drawback. Qualitative possibilistic utility criteria compare acts through min and max operators, which leads to a drowning effect. To over-come this lack of decision power of the theory, several refinements have been proposed. Lexicographic refinements are particularly appealing since they allow to benefit from the Expected Utility background, while remaining qualitative. This article aims at extend-ing lexicographic refinements to sequential decision problems i.e., to possibilistic decision trees and possibilistic Markov decision processes, when the horizon is finite. We present two criteria that refine qualitative possibilistic utilities and provide dynamic programming algorithms for calculating lexicographically optimal policies.

We investigate the potential of the Markov decision processes theory through two applications. The first part of this work is dedicated to the numerical study of an industriallauncher integration process in co-operation with Airbus DS. It is a particular case of inventory control problems where a launch calendar has a key role. The model we propose implies that standard optimization techniques cannot be used. We then investigate two simulation-based algorithms. They return non trivial optimal policies which can be applied in actual practice. The second part of this work deals with the study of partially observable optimal stopping problems. We propose an approximation method using optimal quantization for problems with general state space. We study the convergence of the approximated optimal value towards the real optimal value. The convergence rate is also under study. We apply our method to a numerical example.; Nous explorons l'étendue du champ applicatif des processus markoviens décisionnels au travers de deux problématiques. La première, de nature industrielle, propose l'étude numérique de l'optimisation d'un processus d'intégration lanceur en collaboration avec Airbus DS. Il s'agit d'un cas particulier des problèmes de gestion d'inventaire dans lequel un calendrier de tirs joue un rôle central. La modélisation adoptée entraîne l'impossibilité d'appliquer les procédures d'optimisation classiques liées au formalisme des processus markoviens décisionnels. Nous étudions alors des algorithmes basés sur des simulations qui rendent des stratégies optimales non triviales et qui sont utilisables dans la pratique. La deuxième problématique, de nature théorique, se concentre sur les questions d'arrêt optimal partiellement observables. Nous proposons une méthode d'approximation par quantification de ces problèmes lorsque les espaces d'états sont quelconques. Nous étudions la convergence de la valeur optimale approchée vers la valeur optimale réelle ainsi que sa vitesse. Nous appliquons notre méthode à un exemple numérique.

We investigate the potential of the Markov decision processes theory through two applications. The first part of this work is dedicated to the numerical study of an industriallauncher integration process in co-operation with Airbus DS. It is a particular case of inventory control problems where a launch calendar has a key role. The model we propose implies that standard optimization techniques cannot be used. We then investigate two simulation-based algorithms. They return non trivial optimal policies which can be applied in actual practice. The second part of this work deals with the study of partially observable optimal stopping problems. We propose an approximation method using optimal quantization for problems with general state space. We study the convergence of the approximated optimal value towards the real optimal value. The convergence rate is also under study. We apply our method to a numerical example.; Nous explorons l'étendue du champ applicatif des processus markoviens décisionnels au travers de deux problématiques. La première, de nature industrielle, propose l'étude numérique de l'optimisation d'un processus d'intégration lanceur en collaboration avec Airbus DS. Il s'agit d'un cas particulier des problèmes de gestion d'inventaire dans lequel un calendrier de tirs joue un rôle central. La modélisation adoptée entraîne l'impossibilité d'appliquer les procédures d'optimisation classiques liées au formalisme des processus markoviens décisionnels. Nous étudions alors des algorithmes basés sur des simulations qui rendent des stratégies optimales non triviales et qui sont utilisables dans la pratique. La deuxième problématique, de nature théorique, se concentre sur les questions d'arrêt optimal partiellement observables. Nous proposons une méthode d'approximation par quantification de ces problèmes lorsque les espaces d'états sont quelconques. Nous étudions la convergence de la valeur optimale approchée vers la valeur optimale réelle ainsi que sa vitesse. Nous appliquons notre méthode à un exemple numérique.

National audience; Markov Decision Processes with factored state and action spaces, usually referred to as FA-FMDPs, provide a rich framework to model problems of sequential decision under uncertainty, where both the state and action spaces are of high dimension and highly structured, as in robotics, conservation biology or disease management domains. However, even dedicated solution algorithms (exact or approximate) do not apply when the dimensions of the state and action spaces both exceed 20-30, except under strong assumptions about state transitions or value function. In this paper we introduce the F^3 MDP framework and associated approximate solution algorithms which can tackle much larger problems. An F^3 MDP is an FA-FMDP whose reward function is additively factored and solution policies are constrained to be factored and can be stochastic. The proposed algorithms belong to the family of Policy Iteration (PI) algorithms and exploit continuous optimization tools. We validate them on extensive experiments. On small problems, where the optimal policy is available, they provide policies close to optimal. On larger problems belonging to the subclass of GMDPs they compete well with state-of-the-art resolution algorithms in terms of quality. Finally, we show that our algorithms can tackle very large F^3 MDPs. Indeed, they can solve problems of disease management in crop fields with state and action spaces of size 2^100.

Markov Decision Processes (MDP) are a mathematical formalism of many domains of artifical intelligence such as planning, machine learning, reinforcement learning... Solving an MDP means finding the optimal strategy or policy of an agent interacting in a stochastic environment. When the size of this system becomes very large it becomes hard to solve this problem with classical methods. This thesis deals with the resolution of MDPs with large state space. It studies some resolution methods such as: abstractions and the projection methods. It shows the limits of some approachs and identifies some structures that may be interesting for the MDP resolution. This thesis focuses also on projection methods, the Least square temporal difference algorithm LSTD([lambda]). An estimate of the rate of the convergence of this algorithm has been derived with an emphasis on the role played by the parameter [lambda]. This analysis has then been generalized to the case of Least square non stationary policy iteration LS([lambda])NSPI . We compute a performance bound for LS([lambda])NSPI by bounding the error between the value computed given a fixed iteration and the value computed under the optimal policy, that we aim to determine, Les processus décisionnels de Markov (MDP) sont un formalisme mathématique des domaines de l'intelligence artificielle telle que la planification, l'apprentissage automatique, l'apprentissage par renforcement... Résoudre un MDP permet d'identifier la stratégie (politique) optimale d'un agent en interaction avec un environnement stochastique. Lorsque la taille de ce système est très grande il devient difficile de résoudre ces processus par les moyens classiques. Cette thèse porte sur la résolution des MDP de grande taille. Elle étudie certaines méthodes de résolutions: comme les abstractions et les méthodes dites de projection. Elle montre les limites de certaines abstractions et identifie certaines structures "les bisimulations" qui peuvent s'avérer intéressantes pour une résolution approchée du problème. Cette thèse s'est également intéressée à une méthode de projection l'algorithme Least square temporal difference LSTD([lambda]). Une estimation de la borne sur la vitesse de convergence de cet algorithme a été établie avec une mise en valeur du rôle joué par le paramètre [lambda]. Cette analyse a été étendue pour déduire une borne de performance pour l'algorithme Least square non stationary policy iteration LS([lambda])NSPI en estimant la borne d'erreur entre la valeur calculée à une itération fixée et la valeur sous la politique optimale qu'on cherche à identifier

National audience; Markov Decision Processes with factored state and action spaces, usually referred to as FA-FMDPs, provide a rich framework to model problems of sequential decision under uncertainty, where both the state and action spaces are of high dimension and highly structured, as in robotics, conservation biology or disease management domains. However, even dedicated solution algorithms (exact or approximate) do not apply when the dimensions of the state and action spaces both exceed 20-30, except under strong assumptions about state transitions or value function. In this paper we introduce the F^3 MDP framework and associated approximate solution algorithms which can tackle much larger problems. An F^3 MDP is an FA-FMDP whose reward function is additively factored and solution policies are constrained to be factored and can be stochastic. The proposed algorithms belong to the family of Policy Iteration (PI) algorithms and exploit continuous optimization tools. We validate them on extensive experiments. On small problems, where the optimal policy is available, they provide policies close to optimal. On larger problems belonging to the subclass of GMDPs they compete well with state-of-the-art resolution algorithms in terms of quality. Finally, we show that our algorithms can tackle very large F^3 MDPs. Indeed, they can solve problems of disease management in crop fields with state and action spaces of size 2^100.

Article dans revue scientifique avec comité de lecture. nationale.; National audience; Les algorithmes connexionnistes sont inspirés de la manière dont le cerveau traite l'information : ils impliquent un grand nombre d'unités simples fortement interconnectées, manipulant des informations numériques de manière distribuée et massivement parallèle. Le contrôle optimal est une théorie computationnelle qui permet d'écrire l'interaction entre un agent et un environnement : elle permet de formaliser précisément le problème consistant à atteindre un certain nombre de buts via l'interaction. Si le contrôle optimal caractérise un "but" (l'optimisation d'un critère), l'approche connexionniste suggère, elle, une "manière" de calculer. Nous décrivons plusieurs problématiques s'inscrivant dans le cadre du contrôle optimal et montrons qu'elles admettent des solutions qui sont connexionnistes : 1) Le contrôle optimal et sa variante adaptative (l'apprentissage par renforcement) dans un petit espace d'états 2) L'apprentissage d'une représentation pour approximer le problème de contrôle optimal ayant un grand espace d'états.

This PhD thesis has been interested in two fields of artificial intelligence : reinforcement learning (RL) on the one hand, and multi-agent systems (MAS) on the other hand. The former allows for the conception of agents (intelligent entities) based on a reinforcement signal which rewards decisions leading to the specified goal, whereas the latter is concerned with the intelligence that can result from the interaction of a group of entities (in the perspective that the whole is more than the sum of its parts). Both these tools suffer from various difficulties. The work we accomplished has shown how these tools can serve each other to answer some of these problems. Thus, agents of a MAS have been conceived through RL, and the architecture of a reinforcement learning agent has been designed as a MAS. Both tools appear to be very complementary, and our global approach of a “progressive” design has proved its efficiency., Cette thèse s'est intéressée à deux domaines de l'intelligence artificielle : d'une part l'apprentissage par renforcement (A/R), et d'autre part les systèmes multi-agents (SMA). Le premier permet de concevoir des agents (entités intelligentes) en se basant sur un signal de renforcement qui récompense les décisions menant au but fixé, alors que le second concerne l'intelligence qui peut venir de l'interaction d'un groupe d'entités (dans la perspective que le tout soit plus que la somme de ses parties). Chacun de ces deux outils souffre de diverses difficultés d'emploi. Le travail que nous avons mené a permis de montrer comment chacun des deux outils peut servir à l'autre pour répondre à certains de ces problèmes. On a ainsi conçu les agents d'un SMA par A/R, et organisé l'architecture d'un agent apprenant par renforcement sous la forme d'un SMA. Ces deux outils se sont avérés très complémentaires, et notre approche globale d'une conception “progressive” a prouvé son efficacité.

This thesis studies the use of connectionist algorithms for solving reinforcement learning problems. Connectionist algorithms are inspired by the way information is processed by the brain: they rely on a large network of highly interconnected simple units, which process numerical information in a distributed and massively parallel way. Reinforcement learning is a computational theory that describes the interaction between an agent and an environment: it enables to precisely formalize goal-directed learning from interaction.We have considered three problems, with increasing complexity, and shown that they can be solved with connectionist algorithms: 1) Reinforcement learning in a small state space: we exploit a well-known algorithm in order to build a connectionist network: the problem's paramaters are stored into weighted units and connections and the planning is the result of a distributed activity in the network. 2) Learning a representation for approximating a reinforcement learning problem with a large state space: we provide an algorithm for automatically building a state space partition in order to approximate a large problem. 3) Self-organization of specialized modules for approximating various reinforcement problems with a large state space: we exploit a ``divide and conquer'' approach and show that various tasks can efficiently be spread over a little number of specialized functional modules.; Cette thèse étudie l'utilisation d'algorithmes connexionnistes pour résoudre des problèmes d'apprentissage par renforcement. Les algorithmes connexionnistes sont inspirés de la manière dont le cerveau traite l'information : ils impliquent un grand nombre d'unités simples fortement interconnectées, manipulant des informations numériques de manière distribuée et massivement parallèle. L'apprentissage par renforcement est une théorie computationnelle qui permet de décrire l'interaction entre un agent et un environnement : elle permet de formaliser précisément le problème consistant à atteindre un certain nombre de buts via l'interaction.Nous avons considéré trois problèmes de complexité croissante et montré qu'ils admettaient des solutions algorithmiques connexionnistes : 1) L'apprentissage par renforcement dans un petit espace d'états : nous nous appuyons sur un algorithme de la littérature pour construire un réseau connexionniste ; les paramètres du problème sont stockés par les poids des unités et des connexions et le calcul du plan est le résultat d'une activité distribuée dans le réseau. 2) L'apprentissage d'une représentation pour approximer un problème d'apprentissage par renforcement ayant un grand espace d'états : nous automatisons le procédé consistant à construire une partition de l'espace d'états pour approximer un problème de grande taille. 3) L'auto-organisation en modules spécialisés pour approximer plusieurs problèmes d'apprentissage par renforcement ayant un grand espace d'états : nous proposons d'exploiter le principe "diviser pour régner" et montrons comment plusieurs tâches peuvent être réparties efficacement sur un petit nombre de modules fonctionnels spécialisés.

Rapport interne.; Les travaux présentés ici s'intéressent à la synthèse automatique d'agents en environnement incertain. Nous avons ainsi fait le choix de nous placer dans le cadre de l'apprentissage par renforcement (A/R), et plus précisément des processus de décision markoviens partiellement observables (PDMPO). Une seconde décision a été de se restreindre à des agents travaillant sans modèle (de leur environnement) ni mémoire à court terme. Par contre, nous nous sommes particulièrement intéressés au cas d'agents confrontés à de multiples motivations (objectifs) simultanées. Cette problématique précise conduit assez directement aux travaux du domaine de la sélection d'action (S/A). Le présent article propose et évalue différentes architectures de sélection d'action pour le contrôle d'agents. Leur principe commun est de combiner de manière adaptative des comportements de base déjà connus, en apprenant (par renforcement) les réglages de la combinaison de manière à maximiser les gains de l'agent. Ces travaux ouvrent la voix vers une seconde étape dans laquelle les comportements de base eux-mêmes seraient sélectionnés et conçus de manière automatique.

Colloque sans acte à diffusion restreinte.; Zygiella x-notata est une araignée orbitèle dont l'alimentation, le développement et la reproduction (production d'une descendance) nécessite la mise en place d'un piège (toile géométrique). Les araignées femelles adultes sont capables de reconstruire quotidiennement et nous avons montré qu'elles présentent de plus la capacité de moduler leur comportement de construction à court terme, d'une toile à l'autre en réponse aux modifications de leur situation (état interne, milieu). De manière à maximiser leur fitness, elles devraient ajuster leurs constructions successives (fréquence de tissage, investissement consacré à la construction de chacune des toiles) en accord avec les variations de leur situation. La construction d'une toile présente des risques (prédation, parasitisme), des coûts énergétiques (production et mise en place de la soie) et des bénéfices (capture de proies). d'un point de vue énergétique, la construction d'une toile influence donc l'état interne de l'araignée qui en retour peut influencer les décisions relatives à la construction de la toile suivante (investissement, moment de tissage). Par ailleurs les conséquences de la réalisation d'une toile sont probabilistes, elles dépendent des caractéristiques du piège (taille, âge, dégâts) et de celles du milieu (proies potentielles, parasites, prédateurs). Aussi, pour aborder les règles selon lesquelles l'araignée construit ses toiles successives, nous élaborons un modèle dynamique et stochastique. Nous cherchons à prédire la façon dont l'araignée femelle adulte doit gérer la construction de ses toiles successives après la mue imaginale pour maximiser ses chances d'atteindre au mieux le poids permettant la ponte.