Gauthier Picard

Un modèle agent générique pour la comparaison d'approches d'allocation de ressources dans le domaine du transport à la demande

Les problèmes d'allocation sont d'importance majeure dans la gestion des systèmes de transport à la demande (ODT). Ils ont été étudiés pendant des décennies, et diverses solutions ont été proposées. Les approches de résolution peuvent être classées en deux catégories : centralisées et décentralisées. Dans la pratique, chacune a ses avantages et désavantages. Dans ce travail, nous visons à fournir un modèle générique pour le problème du transport à la demande en ligne avec des véhicules autonomes et un modèle multi-agents dédié à l'allocation des ressources et à la planification d'une flotte de véhicules. Ce dernier considère des véhicules autonomes qui communiquent dans un réseau inter-véhiculaire pour satisfaire les demandes de course dans un système ODT. Nous évaluons la généricité de ce modèle en appliquant plusieurs approches d'allocation (programmation mathématique, heuristique gloutonne, optimisation par contraintes distribuées et enchères) et comparons leurs performances sur des scénarios synthétiques générés à partir de données réelles.

Planification multi-utilisateurs et multi-satellites de tâches d'observation dans des constellations avec portions d'orbites exclusives

Nous étudions des techniques distribuées de planification sur des scénarios d'observation de la Terre avec utilisateurs et satellites multiples. Nous nous concentrons sur la coordination des utilisateurs ayant réservé des portions d'orbites exclusives et d'un planificateur central ayant plusieurs demandes qui peuvent utiliser certains intervalles de ces portions exclusives. Nous définissons le problème de planification de constellations de satellites d'observation de la Terre (EOSCSP 1). Pour le résoudre, nous proposons des schémas multiagents de résolution distribués, notamment l'optimisation sous contraintes distribuée, où les agents coopèrent pour répartir les demandes sans partager leurs propres plans. Ces contributions sont évaluées expérimentalement sur des instances EOSCSP générées sur la base de carnets d'observation réels grande échelle ou très conflictuels.

Analyse des performances d'algorithmes DCOP pour l'association d'utilisateurs de réseaux HetNets

Cet article étudie l'applicabilité des techniques d'optimisation sous contraintes distribuée (DCOP) dans le cadre des réseaux radios hétérogènes (HetNets). Nous nous intéressons plus particulièrement au problème de l'association des terminaux utilisateurs aux stations de base, dont l'objectif est de déterminer quel utilisateur (e.g. téléphone mobile) est associé à quelle station de base pour créer un canal de communication. Toutes les stations ne garantissent pas les mêmes qualités de service et d'expérience aux utilisateurs, et la qualité de l'allocation finale (e.g. le débit total obtenu) est un critère à maximiser. Nous présentons ici un modèle DCOP de ce problème d'association, qui se base sur une gentification des stations de base se coordonnant pour obtenir une allocation efficace. Nous évaluons les performances d'algorithmes légers (MGM, MGM-2, DSA) sur un environnement simulé réaliste. Leurs performances sont comparées à celles d'une solution optimale, ainsi qu'à celle de la politique d'association actuellement utilisée dans ces réseaux, à savoir maxSINR.

Résilience et auto-réparation de processus de décisions multi-agents

Nous définissons la notion de k-résilience de graphes de calculs en support aux décisions d'agents opérées sur des systèmes dynamiques. Nous proposons une méthode d'auto-réparation de la distribution des calculs, DRPM[MGM-2], afin d'assurer la continuité des décisions collectives suite à la disparition d'agents, grâce au déploiement de réplicas de calculs. Nous nous intéressons ici à la réparation de processus d'optimisation sous contraintes, où les calculs sont des variables de décision ou des contraintes distribuées sur l'ensemble des agents. Nous évaluons expérimentalement les performances de DRPM[MGM-2] sur différentes topologies de systèmes opérant des algorithmes (Max-Sum ou A-DSA) pour résoudre des problèmes classiques (aléatoire, coloration de graphe, Ising) alors que des agents disparaissent.

Mise en place d'une décision collective résiliente sur une infrastructure IoT à l'aide du framework pyDCOP

Cette démonstration vise à illustrer l'utilisation du framework pyDCOP, qui implémente plusieurs méthodes de résolution de problèmes d'optimisation sous contraintes distribuées (DCOP) et fournit des utilitaires pour les déployer sur une infrastructure distribuée et également doter le système de capacités de résilience, nécessaire dans des environnements comme l'Internet-of-Things, dans des scénarios d'Intelligence ambiante ou de Smart Home. Les scénarios sont modélisés dans un format dédié, traduits dans un problème d'optimisation ou de satisfaction de contraintes distribuées, puis poussés vers les dispositifs qui se coordonnent en utilisant des protocoles choisis pour s'autoconfigurer de manière décentralisée. PyDCOP fournit également un cadre de résilience, qui équipe le système avec des capacités d'adaptation contre les disparitions imprévues d'équipements. Ce mécanisme est basé sur la réplication de décisions et un mécanisme de réparation léger basé sur un DCOP.

Négociation multi-agent « un-à-plusieurs » et mécanismes de coordination pour la gestion de la satisfaction des utilisateurs d'un service

La qualité d'expérience (QoE) est définie comme la mesure de la satisfaction des utilisateurs d'un service. Les travaux existants sur la QoE reposent sur une vision binaire de la satisfaction, qui a été critiquée par de nombreuses études empiriques, soulignant son aspect graduel. L'objectif de cet article est d'aller au-delà de cette vision binaire, et de proposer un mécanisme de gestion de la QoE. En particulier, nous proposons un mécanisme de négociation « un-à-plusieurs » permettant au fournisseur de service de se charger de la gestion de la satisfaction pour atteindre des objectifs fins de QoE, tout en minimisant les coûts. Ce problème est formulé comme un problème d'optimisation, pour lequel un modèle linéaire est proposé. Pour référence, un solveur linéaire générique est utilisé pour trouver la solution optimale, et une approche heuristique alternative est proposée afin d'améliorer la réactivité lorsque le système monte en échelle avec un nombre croissant d'utilisateurs. Les deux solutions sont développées et évaluées expérimentalement en comparaison d'autres cadres de négociation « un-à-plusieurs » de l'état de l'art.

DeciMaxSum: décimer pour résoudre des DCOP cycliques plus efficacement

Dans le cadre de la résolution des problèmes d'optimisation des contraintes distribués (DCOP), les algorithmes approchés de propagation de croyances (BP) comme Max-Sum sont des candidats de choix. Cependant, lorsque le modèle graphique sous-jacent est très cyclique, ces méthodes de résolution souffrent de mauvaises performances, en raison de la non-convergence et des trop nombreux messages échangés. Afin d'améliorer les performances de Max-Sum sur de tels DCOPs, nous proposons de s'inspirer de la décimation guidée par BP pour résoudre des problème k-SAT. Nous proposons la nouvelle méthode DeciMaxSum, paramétrable par des critères de déclenchement de décimation, de choix de variables à décimer et de valeurs pour ces variables. Sur la base d'une évaluation expérimentale sur le modèle d'Ising, certaines de ces combinaisons de critères présentent de meilleures performances que les algorithmes concurrents.

Optimisation sous contraintes distribuée : une introduction au domaine

Le raisonnement sous contraintes est une des techniques majeures en intelligence artificielle et en recherche opérationnelle, pour modéliser des problèmes de décision et concevoir des méthodes de résolution efficaces. Sa déclinaison distribuée, le raisonnement sous contraintes distribué (DCR) est un outil puissant pour mettre oeuvre des décisions coopératives dans le cadre des systèmes multi-agents. De tels problèmes se déclinent en (i) des problèmes de satisfaction de contraintes (DisCSP) où l'on recherche une solution satisfaisant toutes les contraintes et en (ii) des problèmes d'optimisation sous contraintes (DCOP) où l'on recherche une solution minimisant un coût global induit par les contraintes. Cet état de l'art se focalise sur le cas des DCOP, qui ont démontré leur forte applicabilité à des problèmes réels. Nous présenterons les principales familles de problèmes et de méthodes de résolutions, ainsi que des exemples d'applications.

Déploiement de graphes de facteurs pour l'exécution d'algorithmes DCOP sur des infrastructures ouvertes

Négociation « one-to-many » adaptative pour améliorer l'acceptabilité des services d'un fournisseur SaaS

Approches multiagents pour l'allocation de courses à une flotte de taxis autonomes

Approche DCOP pour résoudre des problèmes de configuration économe d'environnements intelligents

Nous considérons des environnements dans lesquels des objets intelligents, munis de capacités limitées de calcul et de communication doivent coopérer pour auto-configurer leur état de manière énergétiquement efficace, afin de respecter des besoins utilisateurs. De tels besoins sont exprimés comme des règles de scènes, configurées par l'utilisateur via une interface intuitive qui connecte des conditions sur l'état des objets à des états cibles de l'environnement. Nous traduisons ce problème de configuration d'environnements intelligents en un problème d'optimisation sous contraintes. Afin d'installer distribution, robustesse et ouverture, nous le résolvons grâce à des algorithmes distribués par envois de messages. Nous illustrons notre approche sur un exemple réaliste, et évaluons les performances des protocoles mis en oeuvre dans un environnement simulé.

Analyse des critères d'évaluation de systèmes multi-agents adaptatifs

La complexité croissante des applications actuelles favorise le développement de systèmes multi-agents auto-organisateurs possédant des propriétés self-* . Ces systèmes autonomes présentent des capacités intéressantes permettant la gestion de la dynamique endogène et exogène des applications étudiées. De nouveaux critères doivent être proposés afin de caractériser et évaluer l'apport de ces propriétés self-* et leur influence sur les performances du système. Dans cet article, différentes catégories regroupant les principaux critères d'évaluation sont décrites afin de guider l'évaluation de ce type de systèmes depuis les phases de conception jusqu'aux phases d'exécution : évaluation du système en cours de fonctionnement, caractéristiques intrinsèques et méthodologie de conception. In the last few years, the growing complexity of current applications has led to design self-organizing multi-agents systems presenting self-* properties. Those systems behave autonomously and must handle the dynamics coming from exogenous or endogenous changes. New or updated characterization and evaluation criteria are required for analyzing the contribution of self-* properties and system performances. This paper aims at guiding the evaluation of this kind of systems from the design phase all the way to the execution results by providing sets of main criteria : evaluation of the system at run-time, intrinsic characterization and development methodologie.

Réorganisation et auto-organisation dans les systèmes multi-agents

Récemment, les aspects sociaux et organisationnels sont devenus des sujets de recherche majeurs en systèmes multi-agents (SMA). Les travaux conduits peuvent être déclinés suivant un point de vue centré agent (ACPV) et un point de vue centré organisation (OCPV), dans lesquels la notion centrale de dynamique des organisations est considérée. Dans ACPV, cette notion correspond à des phénomènes ascendants et émergents qui sont regroupés sous le terme général d'auto-organisation. Dans OCPV, cette notion d'organisation nourrit un large panel de travaux relatifs à la réorganisation formelle et descendante d'organisations préexistantes installées dans le SMA. Dans cet article, nous proposons de positionner ces approches afin de construire une vision synthétique de la dynamique des organisations dans les SMA. In the last years, social and organisational aspects of agency have become a major issue in multi-agent systems' research. The conducted works may be structured along two main points of view : an agent centred point of view (ACPV) and an organisation centred point of view (OCPV). In both approaches the central notion of multi-agent organisation dynamic is considered. In ACPV, this notion leads to a kind of informal, bottom-up, emergent phenomena that we regroup under the general term of selforganisation. In OCPV, this notion gives birth to a huge set of works related to the reorganisation of the formal, top-down, pre-existent organisations that are installed in the MAS. In this paper, we propose to position these two approaches to build a comprehensive picture of organisation dynamic in multi-agent systems.

Gestion de la confiance et intégration des exigences sociales au sein de communautés virtuelles

La confiance est devenue un facteur clé des processus de décision au sein de communautés virtuelles. Le caractère ouvert et décentralisé de ces environnements couplés à leur dimension sociale défient les mécanismes actuelles de gestion de la confiance. Notamment pour ce qui concerne la gestion et l'intégration des exigences de confiance des utilisateurs et ceux de leurs communautés. Afin de répondre à ce problème, nous proposons SC-TMS, un système de gestion de la confiance adaptatif basé sur le principe de conformité sociale [4]. En nous appuyant sur les technologies multi-agents, des politiques de confiance sont utilisées pour spécifier à la fois les modèles de confiance centrés utilisateur et les modèles centrés communauté. Les agents y sont utilisés pour gérer et combiner ces différentes politiques de manière flexible et décentralisée. Nous décrivons les fonctionnalités et l'architecture qui les mettent en oeuvre et discutons de leur implémentation. Recently, trust became a key factor in the decision process within virtual communities. The inherent decentralization and openness of such environments produced new challenges that are not solved by current approaches. In this paper we are considering how user-centred and community-centred trust policies can be considered, managed and combined. To this aim, we propose an adaptive Socially-Compliant Trust Management Systems (SC-TMS) based on multi-agent technologies. In this framework, trust policies can be used to specify (i) usercentred and (ii) community-centred trust models. Agents are used to manage and combine these different policies in a decentralized and flexible way. We describe the functionalities and the architecture that supports them and discuss also a prototype implementation.

Casanova: un comportement d'agent pour l'équité des mariages préservant la privacité

Cet article prône une approche orientée individu pour la résolution du problème classique des mariages stables. Selon cette approche, la solution émerge des négociations entre agents. Par exemple, l'algorithme de Gale-Shapley (GS) distingue deux comportements d'agents (proposant et disposant) qui négocient pour aboutir à une solution stable, pareto-otpimale mais inéquitable : la communauté des proposants est favorisée. Nous proposons ici l'algorithme Casanova qui met en oeuvre une stratégie de concession minimale. Les agents jouent simultanément le rôle de disposant et de proposant dans une multitude de négociations bilatérales. De plus, les solutions qui émergent ne peuvent être atteintes par GS et elles sont plus équitables. Notre implémentation est décentralisée et préserve la privacité. This paper promotes an individual-based approach for solving a well-known problem, the stable marriage problem. In this approach, a solution is the output of an emergent phenomena due to the negotiation between the agents. For instance, the Gale-Shapley (GS) algorithm implies two distinct behaviours (the proposer and the responder) to reach a stable matching which is pareto-optimal even if it is in favour of the proposers rather than the responders. We propose here the Casanova algorithm which applies the minimal concession strategy for negotiation. Each agents play the role of proposer and responder in multi bi-lateral negotiations. Moreover, the emergent solutions, which are more equitable, cannot be reached by GS. Our implementation is privacy-preserving and decentralized.

Organisation multi-agent pour la gouvernance de systèmes Machine-to-Machine

Le paradigme Machine-to-Machine (M2M) implique des appareils (capteurs, effecteurs) interagissant pour fournir des services localisés dans le monde physique. Avec la maturité du M2M, émerge une demande grandissante pour des solutions mutualisées dans lesquelles les applications peuvent partager un ensemble commun d'appareils. Dans ce contexte, le projet SensCity propose une infrastructure pour mettre en oeuvre des applications à l'échelle de la ville, ce qui nécessite de fournir des moyens de gouvernance agile pour prendre en compte l'extensibilité du système (ie. scalability). Nous proposons d'utiliser les technologies multi-agents pour répondre à cette problématique. Selon cette approche, la stratégie de gouvernance est exprimée par une organisation multi-agent à l'aide du framework organisationnel MOISE. Nous illustrons notre proposition par un système de gestion intelligente du strationnement. The Machine-to-Machine (M2M) paradigm involves devices (sensors, actuators) interacting together to provide services located in the physical world. As the technology is gaining maturity, there is a growing need for mutualized solutions in which applications can share a common set of devices. In this context, the SensCity project proposes an infrastructure to enable mutualized city scale applications. Implementing such an infrastructure raises the problem of providing an agile governance with respect to scalability. Besides, Multi-Agent technologies grant adaptability, flexibility and proactivity properties to such a decentralized applications. Thus, this paper proposes a Multi-Agent organization for expressing the governance strategy of such systems. Using the MOIS E framework, we illustrate how it is used within a smart parking management application.

Optimisation multi-agent par partitionnement adaptatif de l'espace de conception

Nous proposons l'usage de systèmes multiagents pour résoudre des problèmes d'optimisation impliquant des simulateurs numériques coûteux. Il est alors usuel de remplacer certains appels aux simulateurs numériques par des appels à des métamodèles. L'idée proposée dans cet article est d'assigner les métamodèles adéquats à chaque sous-région afin de (i) rendre l'optimisation moins coûteuse, (ii) générer une méthode d'optimisation qui trouve les optima globaux et locaux et (iii) fournir une meilleure compréhension du problème d'optimisation et de son espace de conception. La technique utilisée est de partitionner l'espace de conception entre divers agents utilisant des métamodèles différents pour approximer leur sous-région et se coordonnant pour modifier les frontières de leur sous-région. In this paper we explore the use of multi-agent methods to tackle complex optimization problems that require expensive simulations. We particularly focus on surrogate-based optimization for problems in which direct optimization is too expensive. The proposed strategy partitions the design space between several agents that use different surrogates to approximate their subregion landscape. Agents coordinate by exchanging points to compute their surrogate and by modifying the boundaries of their subregions. The rationale behind this technique is to assign adequate surrogate to each subregion so that (i) optimization is cheaper, (ii) the overall optimization process is not only global in scope but also stabilizes on local optima and (iii) the final partitioning provides a better understanding of the optimization problem.

Méthode multi-agent d'optimisation par partitionnement auto-organise

Dans le cadre de la conception de produits complexes, et en nous basant sur une méthode d'optimisation multi-agent par partitionnement de l'espace de conception, nous proposons une nouvelle méthode permettant au système multiagent de découvrir tous les optima locaux par des mécanismes auto-organisés de création et de destruction d'agents, et ce avec un nombre limité d'appels aux fonctions coûteuses. Les agents sont en charge de la découverte d'optima locaux dans leur propre partition de l'espace de conception, qui évolue au cours de la résolution. Notre approche est mise en oeuvre sur un problème illustratif en 2 dimensions et un problème difficile en 6 dimensions. Based on an multi-agent optimization method for complex system design with adaptive partitioning of the design space, we propose a new multi-agent method to discover all the local optima using self-organizing mechanisms of creation and destruction of agents, with a limited number of expensive function calls. Each agent is responsible for the discovery of local optima in its own partition of the design space, which evolves during the solving process. Our approach is implemented on a sample illustrative 2D-problem and a more difficult 6D-problem.

Conception d'une place de marché pour la vente et la distribution d'énergie dans les smart grids

Cet article introduit un nouveau mécanisme de marché qui permet aux prosommateurs d'échanger de l'électricité tout en satisfaisant les contraintes physiques du réseau. La règle d'allocation de notre marché est mise en oeuvre au moyen de RadPro, un algorithme efficace de programmation dynamique qui évalue en temps polynomial combien d'énergie chaque prosommateur échange ainsi que comment l'énergie doit être distribuée au travers du réseau. Nos résultats empiriques montrent que RadPro surclasse de manière significative CPLEX et Gurobi en temps lors du calcul de l'allocation optimale dans des réseaux acycliques. De plus, la gestion par envoi de messages de RadPro offre la possibilité d'exécuter notre marché d'une manière décentralisée (pair-à-pair). This paper introduces a novel market that allows prosumers to trade electricity while satisfying the constraints of the grid. Our market's allocation rule is implemented by means of the so-called RadPro, an efficient dynamic programming algorithm that assesses in polynomial time how much energy each prosumer trades as well as how energy must be distributed throughout the grid. Our empirical results show that Rad- Pro significantly outperforms both CPLEX and Gurobi in solving time when computing the optimal allocation over acyclic networks. Furthermore, the message-passing nature of RadPro offers the possibility of running our market in a decentralized (peer-to-peer) manner.

Gestionnaire multiagent de contexte pour les applications d'intelligence ambiante

L'intelligence ambiante (AmI) connaît actuellement un développement croissant d'applications. Afin de mettre en place flexibilité d'installation et généricité dans le déploiement et l'approvisionnement de solutions de gestion de contexte, nous proposons CONSERT, un integiciel de gestion du contexte (CMM), basé sur les techniques et les principes du Web sémantique et des systèmes multiagents. Dans cet article, nous nous appliquons à montrer comment l'architecture multiagent de ce CMM offre la souplesse nécessaire pour déployer différents types de schémas de provisionnement de contexte pour répondre à différentes applications d'AmI. Nous présentons l'utilisation de notre solution avec un scénario issu du domaine de la gestion d'une université “intelligente”. Ambient Intelligence (AmI) is experiencing an increasing development of applications. As to install flexibility and genericity in the deployment and provisioning of context management solutions, we propose CONSERT, a CMM, based on techniques and principles from the Semantic Web and Multiagent Systems domains. In this paper we focus on showing how the multiagent architecture of this CMM provides the necessary flexibility to deploy different kinds of context provisioning patterns to address different AmI applications. We showcase the usage of our solution with a scenario from the domain of smart university life management.

Contextualiser l'interaction entre agents en combinant dimensions sociale et physique au sein de l'environnement

L'environnement, en tant qu'espace partagé entre agents, est un élément essentiel des systèmes multiagents. Selon les systèmes, cet espace intègre des dimensions différentes comme une dimension physique support à l'ancrage spatial et à l'activité des agents sur cette dimension, ou une dimension sociale support aux communications entre agents. Ces dimensions sont souvent traitées de manière indépendante et ne sont reliées qu'au sein de l'agent qui constitue alors le lieu de jonction et de combinaison des informations véhiculées dans ces différentes dimensions. Il s'avère cependant que la combinaison entre ces dimensions est à considérer également en dehors des agents, pour pouvoir par exemple, situer des communications. Dans cet article, nous proposons un modèle unifié assurant la combinaison des dimensions physiques et sociales pour la mise en oeuvre d'interactions contextualisées entre agents. Ce modèle est développé avec le langage multiagent SARL. Nous illustrons cette proposition par une application de simulation de trafic routier dans la ville de Belfort.