Les systèmes multi-agents mettent en jeu des entités artificielles, conçues par des utilisateurs potentiellement différents, devant se coordonner pour atteindre leur but. La problématique générale est donc l'atteinte d'états "satisfaisants" en dépit de contraintes liées à la distribution des entités qui prennent part à la décision collective, et du caractère non nécessairement coopératifs de ces agents. Je discute de problèmes de vote dans le cas où les profils représentant les préférences des agents prenant part à la décision ne sont pas complètement spécifiés (à cause, par exemple, de la perte de messages du fait de la distribution, ou encore de l'impossibilité de spécifier parfaitement un profil portant sur un nombre rédhibitoire d'alternatives, comme dans le cas de domaines combinatoires). Les questions que nous abordons sont par exemple celles de la taille minimale nécessaire à encoder le profil partiel tout en restant capable de déterminer de manière certaine l'alternative choisie après complétion des votes, ou encore de la difficulté (algorithmique) liée à la détermination des alternatives que l'on peut exclure sans craindre de regretter ce choix plus tard, même si d'autres alternatives peuvent apparaîtrent. J'aborde également des procédures complètement décentralisées d'allocation de ressources. Ici on suppose que les agents débutent avec une allocation initiale et modifient de manière itérative cette allocation par le biais de contrats, c'est-à-dire de réallocation locale de ressources entre eux. En posant la contrainte que chacun de ces contrats doit être individuellement rationnel on se penche sur les garanties de convergence de tels systèmes vers de états efficaces et/ou équitables (au sens par exemple de l'égalitarisme ou l'absence d'envie). J'envisage enfin un processus de prise de décision collective plus délibératif, au sens où les agents peuvent échanger des arguments et contre-arguments, pour (éventuellement) modifier le point de vue des autres. Dans un premier temps je discute d'un cadre où les agents coopèrent en vue d'établir un diagnostic commun d'une situation, alors que les agents ne percoivent que localement leur environnement et ne disposent que de possibilités restreintes de communication. Chaque agent construit (sur la base d'informations partielles) une hypothèse qui pourra être par la suite réfutée par d'autres agents, nous sommes en présence d'un raisonnement de type non-monotone. Je présente enfin brièvement le cadre non-coopératif d'une argumentation multi-partite, où les agents peuvent avoir des opinions réellement contradictoires. Un protocole simple est proposé, qui contraint minimalement la pertinence des arguments échangés, et quelques phénomènes liés au comportement statégique des agents sont illustrés.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La prise de décision dans l'incertain et la coordination sont au coeur des systèmes multiagents. Dans ce type de systèmes, les agents doivent être en mesure de percevoir leur environnement et de prendre des décisions en considérant les autres agents. Lorsque l'environnement est partiellement observable, les agents doivent être en mesure de gérer cette incertitude pour prendre des décisions les plus éclairées possible en considérant les informations incomplètes qu'ils ont pu acquérir. Par ailleurs, dans le contexte d'environnements multiagents coopératifs, les agents doivent être en mesure de coordonner leurs actions de manière à pouvoir accomplir des tâches demandant la collaboration de plus d'un agent. Dans cette thèse, nous considérons des environnements multiagents coopératifs complexes (dynamiques, incertains et temps-réel). Pour ce type d'environnements, nous proposons une approche de prise de décision dans l'incertain permettant une coordination flexible entre les agents. Plus précisément, nous présentons un algorithme de résolution en ligne de processus de décision de Markov partiellement observables (POMDPs). Par ailleurs, dans de tels environnements, les tâches que doivent accomplir les agents peuvent devenir très complexes. Dans ce cadre, il peut devenir difficile pour les agents de déterminer le nombre de ressources nécessaires à l'accomplissement de chacune des tâches. Pour résoudre ce problème, nous proposons donc un algorithme d'apprentissage permettant d'apprendre le nombre de ressources nécessaires à l'accomplissement des tâches selon les caractéristiques de celles-ci. Dans un même ordre d'idée, nous proposons aussi une méthode d'ordonnancement permettant d'ordonner les différentes tâches des agents de manière à maximiser le nombre de tâches pouvant être accomplies dans un temps limité. Toutes ces approches ont pour but de permettre la coordination d'agents pour l'accomplissement efficace de tâches complexes dans un environnement multiagent partiellement observable, dynamique et incertain. Toutes ces approches ont démontré leur efficacité lors de tests effectués dans l'environnement de simulation de la RoboCup- Rescue.

L'objectif de cette thèse est l'étude de la synthèse de plans dans un contexte multi-agent. La problèmatique principale est de comprendre les mécanismes qui permettent à une société d'agents autonomes de construire collectivement un plan global. Contrairement aux approches classiques dans lesquelles la planification n'est qu'un outil parmi d'autres pour définir les activités des agents et la coordination une «surcouche» nécessaire à leur synchronisation, la contribution de nos travaux repose sur la conception d'un modèle de planification entièrement distribué dans lequel les agents raisonnent conjointement sur leurs activités respectives pour atteindre un but commun prédéfini en intégrant leurs compétences hétérogènes ainsi que leurs croyances partielles sur le monde. Dans cette perspective, nous proposons de considérer la synthèse de plans comme un raisonnement collectif et révisable fondé sur l'échange entre les agents de conjectures, i.e., des plans qui peuvent être exécutés si certaines conditions sont vérifiées et de réfutations, i.e., des objections quant à la réalisation du plan. Les intéractions entre agents peuvent se définir comme un processus dialectique d'investigation dans lequel les agents proposent leurs compétences pour démonter la validité de certaines hypothèses, réfuter les conjectures non réalisables, réparer lorsque cela est possible les conjectures précédemment réfutées et ainsi élaborer pas à pas un plan solution.

Prendre de bonnes décisions dans des environnements multiagents est une tâche difficile dans la mesure où la présence de plusieurs décideurs implique des conflits d'intérêts, un manque de coordination, et une multiplicité de décisions possibles. Si de plus, les décideurs interagissent successivement à travers le temps, ils doivent non seulement décider ce qu'il faut faire actuellement, mais aussi comment leurs décisions actuelles peuvent affecter le comportement des autres dans le futur. La théorie des jeux est un outil mathématique qui vise à modéliser ce type d'interactions via des jeux stratégiques à plusieurs joueurs. Des lors, les problèmes de décision multiagent sont souvent étudiés en utilisant la théorie des jeux. Dans ce contexte, et si on se restreint aux jeux dynamiques, les problèmes de décision multiagent complexes peuvent être approchés de façon algorithmique. La contribution de cette thèse est triple. Premièrement, elle contribue à un cadre algorithmique pour la planification distribuée dans les jeux dynamiques non-coopératifs. La multiplicité des plans possibles est à l'origine de graves complications pour toute approche de planification. Nous proposons une nouvelle approche basée sur la notion d'apprentissage dans les jeux répétés. Une telle approche permet de surmonter lesdites complications par le biais de la communication entre les joueurs. Nous proposons ensuite un algorithme d'apprentissage pour les jeux répétés en ``self-play''. Notre algorithme permet aux joueurs de converger, dans les jeux répétés initialement inconnus, vers un comportement conjoint optimal dans un certain sens bien défini, et ce, sans aucune communication entre les joueurs. Finalement, nous proposons une famille d'algorithmes de résolution approximative des jeux dynamiques et d'extraction des stratégies des joueurs. Dans ce contexte, nous proposons tout d'abord une méthode pour calculer un sous-ensemble non vide des équilibres approximatifs parfaits en sous-jeu dans les jeux répétés. Nous montrons ensuite comment nous pouvons étendre cette méthode pour approximer tous les équilibres parfaits en sous-jeu dans les jeux répétés, et aussi résoudre des jeux dynamiques plus complexes. / Making good decisions in multiagent environments is a hard problem in the sense that the presence of several decision makers implies conflicts of interests, a lack of coordination, and a multiplicity of possible decisions. If, then, the same decision makers interact continuously through time, they have to decide not only what to do in the present, but also how their present decisions may affect the behavior of the others in the future. Game theory is a mathematical tool that aims to model such interactions as strategic games of multiple players. Therefore, multiagent decision problems are often studied using game theory. In this context, and being restricted to dynamic games, complex multiagent decision problems can be algorithmically approached. The contribution of this thesis is three-fold. First, this thesis contributes an algorithmic framework for distributed planning in non-cooperative dynamic games. The multiplicity of possible plans is a matter of serious complications for any planning approach. We propose a novel approach based on the concept of learning in repeated games. Our approach permits overcoming the aforementioned complications by means of communication between players. We then propose a learning algorithm for repeated game self-play. Our algorithm allows players to converge, in an initially unknown repeated game, to a joint behavior optimal in a certain, well-defined sense, without communication between players. Finally, we propose a family of algorithms for approximately solving dynamic games, and for extracting equilibrium strategy profiles. In this context, we first propose a method to compute a nonempty subset of approximate subgame-perfect equilibria in repeated games. We then demonstrate how to extend this method for approximating all subgame-perfect equilibria in repeated games, and also for solving more complex dynamic games.

Les systèmes multi-agents s'attaquent aux nombreuses problématiques posées actuellement dans le monde informatique telles que la distribution, l'évolution, l'adaptabilité et l'interopérabilité des systèmes. Les solutions proposées par ces systèmes sont prometteuses et permettent d'obtenir des systèmes flexibles et évolutifs. Cependant, leur mise en oeuvre reste difficile. Ceci est dû au manque de techniques d'ingénierie adaptées à ce genre de système et qui permettent un développement fiable et cohérent. Bien qu'il existe plusieurs propositions intéressantes au niveau des méthodologies, des langages de spécification et des plates-formes d'implémentation orientés agent, celles-ci manquent de cohésion et font ressortir plusieurs différences aussi bien au niveau de la sémantique des concepts utilisés mais aussi au niveau des démarches de développement. Notre but durant cette thèse a été de proposer une approche flexible et cohérente supportant le développement des systèmes multiagents. Cette approche que nous baptisons ArchMDE se base sur une combinaison de l'approche centrée architecture et de l'approche dirigée par les modèles. L'approche centrée architecture nous permet de raisonner sur les éléments qui structurent le système multi-agents ainsi que leurs interactions. Elle permet d'identifier les patrons architecturaux nécessaires au développement des systèmes multi-agents en prenant en compte les différentes vues du système (vue organisationnelle, vue environnementale, etc.). L'approche orientée modèles nous permet d'exprimer de façon explicite la manière de combiner ces patrons architecturaux afin d'avoir une représentation globale du système multi-agents. D'autre part, IDM permet de couvrir les différentes phases du cycle de développement en adoptant une démarche basée sur la transformation de modèles. Cette démarche permet de garantir la cohérence du système durant les différentes phases du cycle de vie. Par ailleurs, celle-ci offre l'avantage de préserver le savoir-faire des développeurs en exprimant explicitement les opérations d'intégration (entre les patrons architecturaux) et de mapping (entre les modèles de conception et les modèles d'implémentation). Pour implanter ArchMDE, nous utilisons le cadre de développement ArchWare qui est basé sur le pi-calcul typé, polyadique et d'ordre supérieur, ce qui permet de supporter les aspects communicatifs et évolutifs des systèmes multi-agents. Le choix d'un cadre formel vise à réduire l'ambiguïté liée aux concepts multi-agents mais aussi à garantir une conception sûre. En effet, l'utilisation d'un langage formel donne la possibilité d'exprimer explicitement différentes propriétés structurelles et comportementales. Le cadre de développement ArchWare offre divers langages accompagnés de différents outils qui nous seront utiles pour mettre en oeuvre notre approche.

Les approches habituelles pour la protection de la privacité s'attachent à définir un niveau de sensibilité pour chaque information. Cette information est soit publique, soit privée et sa circulation est restreinte à un groupe d'agents prédéfini. Dans cette thèse, nous nous appuyons sur la théorie de l'intégrité contextuelle, qui propose de redéfinir la notion de violation de privacité. Selon cette théorie, toute transmission peut déclencher une violation de privacité suivant le contexte dans lequel elle a lieu. Cette thèse utilise la théorie de l'intégrité contextuelle afin de proposer un modèle de protection de la privacité pour les systèmes multi-agents décentralisés: le modèle PrivaCIAS. Afin de contrôler les agents dans le système, le modèle PrivaCIAS fournit un ensemble de normes qui permet la mise en place d'un contrôle social basé sur la confiance. Le modèle donne le contrôle aux agents pour constater les violations (selon l'intégrité contextuelle), puis punir les contrevenants en les excluant du système sans avoir besoin de recourir à une autorité centrale. Ce modèle vise les réseaux sociaux décentralisés comme champ d'application.

À l’heure du Web 2.0, de nouvelles pratiques d’apprentissage se sont développées au sein de la communauté universitaire. Les étudiants adoptent des pratiques d’intégration de leurs activités sociales au sein de leur processus d’apprentissage. Ces derniers s’attendent à avoir accès à une vaste quantité d’information à travers des outils formels ou informels et à faire partie d'une communauté mondiale de pairs. Le besoin de combiner les ressources institutionnelles et personnelles formalise le concept d’environnement personnel d’apprentissage (EPA). Toutefois, l’élaboration de tels environnements nécessite de développer des compétences complexes que les étudiants du supérieur, pourtant décrits comme natifs du numérique, ne possèdent pas nécessairement. Quelques supports de construction d’EPA ont été proposés dans la littérature, mais ces travaux mettent de côté un point important qui est l’interopérabilité des ressource s. L’objectif du présent mémoire est de fournir aux étudiants un support de construction de leur EPA sous forme d’un tableau de bord, qui permettra d’avoir une vision actualisée des ressources et d’exploiter davantage les liens qui en découlent. Offrir aux étudiants un support de construction de leur EPA est une façon de leur faciliter la réappropriation individuelle des ressources d’apprentissage provenant de sources variées et une gestion optimale en termes de contenu et de processus. La solution proposée est basée sur le concept des systèmes multi-agents et repose sur le modèle organisationnel Agent - Groupe - Rôle. Un prototype a également été implémenté et a permis de démontrer la faisabilité de la solution proposée. / With Web 2.0, the university community have developed new learning practices. Students adopt practices for integrating their social activities into their learning process. The needs of learners are rapidly changed and institutions do not still offer resources totally adapted to this context. Students expect to have access to a vast amount of information through formal or informal tools and to be part of a global peer community. The need to combine institutional and personal resources implies a new concept: Personal Learning Environment (PLE). A PLE is defined as a space for learners to customize the aggregation of heterogeneous resources for their learning needs. Developing such environments requires the involvement of complex skills that higher education students, though described as digital natives, do not necessarily possess. The objective of this research work is to allow students to have support for the construction of their PLE as a dashboard. It would provide an up - to - date view of resources use and further exploit the resulting linkages. The proposed solution is based on the Agent - Group - Role organizational model, one of design method for multi-agent systems. A prototype was also implemented and allowed to demonstrate the feasibility of the proposed solution.

De manière générale, les problèmes séquentiels de décisions multiagents sont très difficiles à résoudre surtout lorsque les agents n'observent pas parfaitement ni complètement l'état de leur environnement. Les modèles actuels pour représenter ces problèmes restent à ce jour très généraux et difficilement applicables dans les multiples applications possibles. Nous proposons dans cette thèse plusieurs approches de réduction de la complexité computationnelle et en pire cas de ces modèles. Une première approche se base sur l'utilisation de contraintes sur l'espace des actions possibles que les différents agents du système peuvent entreprendre. Cette utilisation de connaissances a priori dans la modélisation au travers de modèles déjà connus, mais non appliqués à la prise de décision séquentielle permet une réduction significative d'un des facteurs de la complexité algorithmique. La seconde approche consiste à restreindre les possibilités d'observations de l'agent à un ensemble similaire à l'espace d'états utilisé pour représenter son environnement. De cette manière, nous montrons que les agents peuvent converger rapidement en probabilité vers des croyances communes sans nécessairement avoir à communiquer. Dans ce contexte, nous avons également développé un algorithme permettant alors aux agents de se coordonner au moment de l'exécution lorsqu'il n'existe pas de communication explicite. Enfin, nous avons entrepris la mise en application de telles réductions à deux problèmes. Un premier problème de patrouille multiagent est considéré et modélisé, et un second problème lié à l'apprentissage de POMDPS continus dans des cas précis de transition et d'observabilité est également abordé. Les résultats obtenus montrent que dans certains cas de problèmes de coordination, la communication ? lorsqu'elle est disponible ? est non négligeable, et que dans le cas de l'apprentissage de POMDPs, considérer le quasi-déterminisme du modèle permet l'apprentissage de converger.

Le travail présenté se situe dans le champ des systèmes complexes. Certains problèmes complexes ne possèdent pas de solution analytique ou ont une solution trop compliquée pour être mise en œuvre facilement. Les méthodes analytiques traditionnelles se posent soit d'un point de vue global (holiste) soit découpent la complexité en éléments distincts pour représenter le comportement du système par une seule entité (réductionniste). Elles sous-estiment ainsi la complexité des différents niveaux d'organisation du système et leur imbrication. De fait, il est quasiment impossible de prévoir l'évolution de tels systèmes à cause du trop grand nombre d'entités et de leurs interactions.<br />Une autre approche se base sur la modélisation du comportement de chaque élément participant à cette évolution ainsi que celle de ses interactions avec les autres éléments et avec l'environnement. Lors de ces interactions, différents types de données peuvent être échangés (information, argent, nourriture, virus, etc...). Ces échanges peuvent être vus comme un flux. Le principe est de mettre en relation des entités ayant des caractéristiques simples qui leur permettront d'interagir les unes avec les autres dans un environnement spécifique afin d'obtenir un comportement global de plus haut niveau. Comme nous pouvons l'observer dans certaines sociétés d'animaux dits sociaux, la performance collective émerge des interactions directes ou indirectes entre les individus et l'environnement : elle est le résultat d'un processus d'auto-organisation au cours duquel l'environnement et la collectivité se structurent mutuellement. L'imprévisibilité de l'évolution des systèmes complexes ne permet pas de les caractériser complètement. Par conséquent, pour modéliser et comprendre la circulation de flux dans de tels systèmes, il est nécessaire de se tourner vers la simulation. <br />Afin de tenir compte des différentes spécifications des systèmes complexes dans leur modélisation, les Systèmes MultiAgents (SMA) représentent une méthode particulièrement appropriée. Il est alors possible de représenter des phénomènes environnementaux comme la conséquence d'interactions d'agents agissant en parallèle, chaque agent étant une entité réactive et autonome. <br />Notre travail est centré sur l'étude de la gestion des flux dans les systèmes complexes par l'élaboration de Simulation Orientée Agents (SOA). En particulier, nous appliquons cette démarche à l'étude de la circulation d'un parasite (Cryptosporidium parvum) dans un écosystème. L'objectif est de mieux comprendre les différents épisodes d'infection auprès de population d'hôtes (animale ou humaine) sous des contraintes spécifiques. Étant donné que ce parasite est particulièrement résistant aux méthodes de désinfection traditionnelles, il est nécessaire de saisir les facteurs prédominants agissant dans la contamination et la propagation du parasite. <br />A cet effet, les données, recueillies auprès de biologistes, nous ont permis de concevoir un outil d'expérimentation en épidémiologie. Cette SOA permet une exploration des comportements possibles du système où circule Cryptosporidium spp.. Ainsi, un ensemble de scenarii a pu être simulé. Les résultats permettent d'évaluer la fiabilité de la modélisation, puis, d'émettre de nouvelles hypothèses concernant la dissémination du parasite.<br />Dans l'objectif d'apporter aux biologistes un outil d'aide à la décision autonome, nous avons développé un système de niveau supérieur (méta-système) capable de réaliser le monitoring d'une SOA. Ce méta-système, basé sur le concept de métaheuristique, cherche à optimiser le comportement du système en fonction d'une problématique précise en évaluant l'impact de facteurs prédéfinis sur l'évolution de la SOA. Ainsi, il est à même d'interpréter les résultats des simulations pour permettre de faire émerger, par l'auto-génération de scenarii, les causes qui influent sur la propagation du parasite.