Search

International audience; We consider the problem of allocating indivisible items to agents where both agents and items are partitioned into disjoint groups. Following previous works on public housing allocation, each item (or house) belongs to a block and each agent is assigned a type. The allocation problem consists in assigning at most one item to each agent in a good way while respecting diversity constraints. Based on Schelling's seminal work, we introduce a generic individual utility function where the welfare of an agent not only relies on her preferences over the items but also takes into account the fraction of agents of her own type in her own block. In this context, we investigate the issue of stability, and study two existing allocation mechanisms: a sequential mechanism used in Singapore and a distributed procedure based on mutually improving swaps of items.

International audience; Mediation is a process for resolving conflicts among several entities. In argumentation debates, conflicting agents that may be organized as teams exchange arguments to persuade each other. In this paper, we consider an automated mediator , which assigns the speaking slots to agents so as to optimize some objectives and ensure the fairness of the debate. We propose a general setting where the argu-mentation strategies of the agents are probabilistically known and may evolve over time. We show that the problem can be solved as a semi-Markov decision problem with hidden modes.

International audience; We investigate fairness issues in distributed resource allocation of indivisible goods. More specifically, we study envy-freeness in a setting where the observations of agents only result from encounters with other agents. Agents thus have a partial and uncertain view of the entire allocation, that they maintain throughout the process, and which allows them to have different estimates of their envy. We provide a fully distributed protocol allowing to guarantee termination despite the limited knowledge of agents.

International audience

International audience; One prominent way to deal with conflicting viewpoints among agents is to conduct an argumentative debate: by exchanging arguments, agents can seek to persuade each other. In this paper we investigate the problem, for an agent, of optimizing a sequence of moves to be put forward in a debate, against an opponent assumed to behave stochasti-cally, and equipped with an unknown initial belief state. Despite the prohibitive number of states induced by a naive mapping to Markov models, we show that exploiting several features of such interaction settings allows for optimal resolution in practice, in particular: (1) as debates take place in a public space (or common ground), they can readily be modelled as Mixed Observability Markov Decision Processes, (2) as argumentation problems are highly structured, one can design optimization techniques to prune the initial instance. We report on the experimental evaluation of these techniques.

International audience; In the simple resource allocation setting consisting in assigning exactly one resource per agent, the top trading cycle procedure stands out as being the undisputed method of choice. It remains however a centralized procedure which may not well suited in the context of multiagent systems, where distributed coordination may be problematic. In this paper, we investigate the power of dynamics based on rational bilateral deals (swaps) in such settings. While they may induce a high efficiency loss, we provide several new elements that temper this fact: (i) we identify a natural domain where convergence to a Pareto-optimal allocation can be guaranteed, (ii) we show that the worst-case loss of welfare is as good as it can be under the assumption of individual rationality, (iii) we provide a number of experimental results, showing that such dynamics often provide good outcomes, especially in light of their simplicity, and (iv) we prove the NP-hardness of deciding whether an allocation maximizing utilitarian or egalitarian welfare is reachable.

International audience; Reinforcement Learning (RL) has been mainly interested in computing an optimal policy for an agent acting in a stationary environment. However, in many real world decision problems the assumption on the stationarity does not hold. One can view a non-stationary environment as a set of contexts (also called modes or modules) where a context corresponds to a possible stationary dynamics of the environment. Even most approaches assume that the number of modes is known, a RL method-Reinforcement Learning with Context Detection (RLCD)-has been recently proposed to learn an a pirori unknown set of contexts and detect context changes. In this paper, we propose a new approach by adapting the tools developed in statistics and more precisely in sequential analysis for detecting an environmental change. Our approach is thus more theoretically founded and necessitates less parameters than RLCD. We also show that our parameters are easier to interpret and therefore easier to tune. Finally, we show experimentally that our approach out-performs the current methods on several application problems.

National audience; Dans cet article, nous étudions des procédures décentralisées d'allocation de ressources reposant sur des échanges bilatéraux entre les agents. Nous nous intéressons aux problèmes dans lesquels chaque agent possède une unique ressource et est en mesure d'échanger cette ressource avec un autre agent afin d'augmenter sa satisfaction, les préférences d'un agent étant décrites par un ordre linéaire sur les ressources. Différentes approches se sont précédemment proposées de calculer de manière centralisée une solution optimale au sens de Pareto. Notre propos est d'étudier les propriétés des solutions obtenues par des procédures décentralisées. Malgré le fait que dans le pire cas, ces solutions puissent potentiellement être loin de l'optimalité, nous avançons plusieurs arguments permettant de relativiser ces résultats négatifs. Nous comparons également les solutions résultant d'échanges bilatéraux avec celles obtenues par la procédure centralisée Top Trading Cycle.

International audience; In this paper, we focus on planning credible walking paths in real-time for a potentially highly congested crowd of au- tonomous pedestrians. For this purpose, we exploit the prin- ciple of least effort, applied to human navigation, which pos- tulates that credible behaviours emerge as a function of the organism's propensity to minimize metabolic energy expen- diture with respect to task, environment dynamics, and or- ganism's constraints to action. We therefore propose a consistent problem formulation for the navigation task where both individual and collective dynamics are taken into account. Each pedestrian is represented as a situated agent who tries to reach its destination by following energy efficient paths. Agents are autonomous, and at the same time, sub- ject to the environment dynamics. They interact with each other through the environment in order to estimate their en- ergy expenditure relatively to their tasks. Our formulation results in a generic and scalable multi-agent model, capable of simulating individual and collective behaviours regardless of the number of agents.

International audience; Le modèle des Processus Décisionnels de Markov (MDP) (Puterman94) permet de représenter et de résoudre des problèmes de décision séquentielle dans l'incertain.Il suppose que l'environnement dans lequel les décisions sont prises est stationnaire.Cependant, dans la pratique, cela peut ne pas être le cas.Choi et al. ont proposé les Hidden-Mode MDP (HM-MDP) (Choi99) pour répondre à cette limitation.Dans leur nouveau modèle, l'environnement est supposé évoluer selon une chaîne de Markov. Chaque mode m d'un HM-MDP est un MDP défini par le tuple avec S l'ensemble des états, A l'ensemble des actions, T_m la fonction de transition entre les états et R_m la fonction de récompense. L'ensemble des états et l'ensemble des actions sont donc communs pour tous les modes. Un HM-MDP est alors défini par le tuple avec M l'ensemble des modes et C la fonction de transition entre les modes.Nous proposons les Hidden-Semi-Markov-Mode MDP (HS3MDP) comme extension des HM-MDP pour les cas où l'environnement évolue selon une chaîne semi-markovienne.Cette hypothèse est d'après nous plus réaliste car l'environnement n'évolue pas forcément à tous les pas de temps. Un HS3MDP est défini par un tuple avec M et C définis comme précédemment et la fonction H(m, m', h) indiquant la probabilité, après avoir changé de mode de m à m', de rester h pas de temps dans le nouveau mode m'. L'un des problèmes de la littérature est celui de la gestion d'ascenseurs. Dans ce problème, l'ensemble des états représente toutes les combinaisons possibles de positions des ascenseurs ainsi que de l'état des boutons d'appel (à l'intérieur) et de sélection d'étages (à l'extérieur). Les actions sont monter, descendre et ouvrir les portes. La fonction de transition entre les états est dépendante des probabilités d'arrivée de personnes à chacun des étages. Cette probabilité est modifiée en fonction des différentes heures de pointes, des réunions inattendues, etc. représentées par les modes. Les fonctions de récompenses engendrent un coup pour chaque utilisateur dont la requête n'est pas satisfaite. C et H sont définies suivant les dynamiques du problème.Les HM-MDP et les HS3MDP sont des sous-classes des MDP partiellement observables (Puterman94) et peuvent donc être résolus en utilisant les méthodes déjà existantes.Cependant, ils souffrent de la même malédiction de la dimension que les POMDP.Nous nous sommes donc intéressés à la résolution approchée des HS3MDP en utilisant POMCP (Silver10) l'un des meilleurs algorithmes de résolution approchée des POMDP à ce jour.Nous l'avons adapté en exploitant la strucutre particulière des HS3MDP afin d'en améliorer les performances et nous avons expérimenté POMCP original et adapté sur différents problèmes non stationnaires de la littérature.

International audience; Despite the significant progress to extend Markov Decision Processes (MDP) to cooperative multi-agent systems, developing approaches that can deal with realistic problems remains a serious challenge. Existing approaches that solve Decentralized Markov Decision Processes (DEC-MDPs) suffer from the fact that they can only solve relatively small problems without complex constraints on task execution. OC-DEC-MDP has been introduced to deal with large DEC-MDPs under resource and temporal constraints. However, the proposed algorithm to solve this class of DEC-MDPs has some limits: it suffers from overestimation of opportunity cost and restricts policy improvement to one sweep (or iteration). In this paper, we propose to overcome these limits by first introducing the notion of Expected Opportunity Cost to better assess the influence of a local decision of an agent on the others. We then describe an iterative version of the algorithm to incrementally improve the policies of agents leading to higher quality solutions in some settings. Experimental results are shown to support our claims.

International audience; Cet article présente une nouvelle approche pour la simulation des déplacements de piétons autonomes en temps réel dans un environnement urbain. Partant du constat que les modèles actuels sont divisés entre représentation macroscopique et représentation microscopique du déplacement, nous proposons une approche posant le problème d'une manière plus générique afin de s'abstraire au maximum de ce clivage. Pour cela nous présentons un modèle microscopique à influence macroscopique qui tient conjointement compte de l'évolution du trafic et des interactions les plus élémentaires qui ont lieu lors du déplacement des piétons. Ces interactions sont le fruit des dépendances qui se créent naturellement entre les déplacements de piétons et qui influencent leurs plans. Les simulations que nous avons réalisées montrent des résultats encourageants aussi bien en termes de crédibilité que de temps de calcul.

National audience; A resource allocation problem is a problem in which a set of agents - cooperative or not - must find an assignment of a set of resources over a set of consumers (most of the time, the agents themselves). This allocation must match, as best as possible, with the agents’ preferences, which are often antagonist. In most allocation problems, the solution space has a combinatorial structure that creates difficulties with the preference formal representation and the optimal choice calculation. Furthermore, agents must frequently make a decision with an incomplete knowledge of the system state while exogenous factors may affect this state after the decision. There is thus a need for the agents to handle uncertainty about the system in order to maximize their satisfaction. However, the allocation problem gets more complicated in case of uncertainty and usual models of collective resource allocation are not appropriate for this context. Whereas resource allocation models for combinatorial domains are the subjects of studies, none of these models consider uncertainty aspects in a distributed context. In this paper we propose a decision-theoretic approach that allows a set of agents to solve, in a distributed way, resource allocation problems under uncertainty. We represent possible interactions and limited observability as an interaction graph and we propose an MDP based approach to compute exchange strategies taking into account future interaction opportunities.

International audience; Dans cet article, nous nous intéressons à l'exploration d'une zone par un robot mobile au-tonome. Notre approche procède à des re-calculs réguliers des politiques en utilisant des processus décisionnels de Markov, au fur et à mesure que la connaissance du robot est actualisée. Dans la mesure où, l'exploration conduit, à chaque instant, à une explosion combinatoire des possibilités sur les poli-tiques d'actions. Le problème de planification par résolution d'un MDP large décomposé est soulevé avec une contrainte forte sur la rapidité des calculs mis en oeuvre. L'approche proposée cherche à par-titionner l'espace des états du robot de façon à construire, ensuite, une hiérarchie de MDP : un MDP abstrait haut niveau et plusieurs MDPs locaux aux régions construites. L'approche est ensuite évaluée par plusieurs expérimentations statistiques. L'originalité consiste en la capacité de l'agent à hiérarchiser l'intérêt de chaque zone à explorer relativement à toutes les autres pour optimiser la politique construite à chaque modification de la carte.

International audience; A resource allocation problem is a problem in which a set of agents - cooperative or not - must find an assignment of a set of resources. This allocation must match, as best as possible, with the agents’ preferences, which are often antagonist. In most allocation problems, the solution space has a combinatorial structure that creates difficulties with the preference formal representation and the optimal choice calculation. Furthermore, agents must frequently make a decision with an incomplete knowledge of the system state while exogenous factors may affect this state after the decision. There is thus a need for the agents to handle uncertainty about the system in order to maximize their satisfaction. However, the allocation problem gets more complicated in case of uncertainty and usual models of collective resource allocation are not appropriate for this context. Whereas resource allocation models for combinatorial domains are the subject of studies, none of these models consider uncertainty aspects in a distributed context. In this paper, we propose a decision-theoretic approach that allows a set of agents to solve, in a distributed way, resource allocation problems under uncertainty. We represent possible interactions and limited observability as an interaction graph and we propose an MDP based approach to compute exchange strategies taking into account future interaction opportunities.

National audience; Les processus décisionnels de Markov sont des modèles couramment utilisés pour représenter des problèmes dedécisions séquentielles dans l'incertain. Cependant, les méthodes de résolution existantes font les hypothèses destationnarité et de représentabilité de la fonction de transition par des probabilités. Nous proposons de retirer ceshypothèses en utilisant l'apprentissage par minimisation de regret dans le cadre multi‐états, mono et multi‐agents.

National audience; Les travaux présentés dans cet article ont pour but de simuler les déplacements de piétons dans une ville virtuelle, en temps réel, et de manière crédible pour un observateur extérieur. Nous présentons un moteur de simulation qui comprend un module de navigation et un module sémantique. Le module de navigation s'appuiera sur des règles de raisonnement fournies par le module sémantique. Ces règles permettront, entre autre, d'inférer un "facteur de danger" qui sera exploité par les algorithmes de déplacement. Notre objectif est de mesurer l'apport d'un module sémantique pour le calcul de courts déplacements des piétons dans un environnement urbain tout en mettant l'accent sur leurs interactions avec les véhicules afin de rendre le comportement plus crédible. Nous présentons tout d'abord l'architecture générale de notre moteur de simulation, qui se compose d'un module de représentation des informations sémantiques de l'environnement et d'un module de navigation pour le déplacement des piétons. Par la suite, nous décrivons l'implémentation qui nous a permis d'évaluer notre modèle.

International audience

International audience; Markov Decision Processes (MDPs) are a mathematical framework for modeling sequential decision problems under uncertainty as well as Reinforcement Learning problems. Written by experts in the field, this book provides a global view of current research using MDPs in Artificial Intelligence. It starts with an introductory presentation of the fundamental aspects of MDPs (planning in MDPs, Reinforcement Learning, Partially Observable MDPs, Markov games and the use of non-classical criteria). Then it presents more advanced research trends in the domain and gives some concrete examples using illustrative applications.

National audience; Mixed-initiative cooperative control can help overcome the limitations of autonomous robots by introducing a human operator into the control loop. Developing new computational models for cooperative control presents several key questions : how to account for the different perceptual and action abilities of the robot versus the human operator, the different costs of their actions, and the fact that human operators cannot switch their attention and take over control instantly. We present a decision-theoretic approach to solve these problems using Mixed-Initiative Markov Decision Processes (MI-MDPs). This framework allows us to compute optimal plans that not only tell the robot what actions to perform, but also when to request human attention or transfer control to the human operator. The result is a model with a varying degree of autonomy, particularly suitable for robots exploring a domain with regions that are too complex or risky for autonomous operation. Experimental results confirm the effectiveness of this approach in common scenarios in which fully-autonomous operation or continuous human control are both undesirable.

This thesis deals with distributed multiagent decision-making underuncertainty. We formalize this problem with Decentralized MarkovDecision Processes (DEC-MDP) which extends Markov Decision Processes(MDP) to multi-agent settings. Even if DEC-MDPs describe an expressiveframework for cooperative multiagent decision, they suffer from a highcomplexity and fail to formalize constraints on task execution.Despite the wide variety of approaches to solve DEC-MDPs, computinga solution for large problems remains a serious challenge even forapproximation approaches.We develop an approach that can solve large problems, and that candeal with more complex time and action representations. We thereforedefine a class of DEC-MDP, OC-DEC-MDP, that allows us to considerseveral possible durations for each task taking into accountconstraints on task execution. Having considered the representationof the problems we deal with, we turn to OC-DEC-MDP resolution. Ourpurpose is to develop an efficient planning approach that computeseach agent's policy even for large missions. Given the highcomplexity of finding an optimal solution, we aim at computing anapproximate solution. We also split the multiagent decision probleminto a set of MDPs. For purposes of coordinating the agents, we thenintroduce the notion of Opportunity Cost., Cette thèse porte sur la prise de décision distribuée dans dessystèmes multi-agents agissant sous incertitude (les colonies derobots autonomes par exemple). Les processus décisionnels de MarkovDécentralisés décrivent un formalisme mathématique permettant demodéliser et de résoudre de tels problèmes. Leur utilisation pour laplanification des tâches dans des applications réelles posetoutefois quelques difficultés. Le modèle usuel des DEC-MDPs nepermet par exemple pas la prise en compte de contraintes sur l'exécution des tâches. De plus,la complexité de leur résolution est telle qu'il est difficile de déterminer une solution optimale excepté pour de petits problèmes.Le travail que nous présentons dans cette thèse a pour premier objectifd'adapter le modèle des DEC-MDPs afin de proposer une modélisationadéquate du temps et des actions, et de permettre la représentation deproblèmes réels. Nous décrivons ainsi une nouvelle classe deDEC-MDPs : les OC-DEC-MDPs (DEC-MDP avec Coût Occasionné). Dans un second temps,nous nous intéressons à leur résolution. Nous proposons différentsalgorithmes procédant à la planification des tâches de chaque agenten vue d'une prise de décision décentralisée et autonome, en accordavec les contraintes du problème. Afin de développer des algorithmesefficaces et de traiter des problèmes de taille importante, nous recherchons uneapproximation de la solution optimale. Nous procédonségalement à un découpage du problème initial en un ensemble de MDPs,et introduisons la notion de coût occasionné afin de tenir comptedes interactions entre les agents et de calculer des politiquescoopératives.