A Multiagent Framework for a Diagnostic and Prognostic System Irtaza Barlas 124 Pages Directed By: Dr. George Vactsevanos The shortcomings of the current diagnostic and prognostic systems stem from the limitations of their frameworks. The framework is typically designed on the passive, open loop, static, and isolated notions of diagnostics, in that the framework does not observe its diagnostic results (open-looped), hence can not improve its performance (static). Its passivity is attributed to the fact that an external event triggers the diagnostic or prognostic action. There is also no effort in place to team-up the diagnostic systems for a collective learning, hence the implementation is isolated. In this research we extend the current approaches of the design and implementation of diagnostic and prognostic systems by presenting a framework based upon Multiagent systems. This research created novel architectures by providing such unique features to the framework, as learning, reasoning, and coordination. As the primary focus of the research the concept of Case-Based Reasoning was exploited to reason in the temporal domain to generate better prognosis, and improve the accuracy of detection as well as prediction. It was shown that the dynamic behavior of the intelligent agent helps it to learn over time, resulting in improved performance. An analysis is presented to show that a coordinated effort to diagnose also makes sense in uncertain situations when there are certain number of systems attempting to communicate certain number of failures, since there can be high probability of finding a shareable experience.

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.

Embora haja muitas pesquisas na área de teamwork, o desenvolvimento de times de agentes para ambientes complexos continua sendo um desafio, especialmente se esses ambientes possuem requisitos de tempo-real. Muitas ferramentas foram desenvolvidas, mas não existe uma bala de prata e aquelas mais gerais possuem sérios problemas com o requisito de tempo-real. Este trabalho introduz uma nova ferramenta baseada em proxy, usando a teoria de Joint Intentions, que ajuda agentes a serem membros de uma equipe dentro de um ambiente parcialmente observável, dinâmico, estocástico e com requisitos de tempo-real. Os experimentos de validação dessa ferramenta são executados no jogo de computador Unreal Tournament 2004, que fornece um ambiente com tais características. / Although there are many researches in teamwork, the development of agent teams for complex environments still presents many challenges, especially if these environments have real-time requirements. Many tools have been developed, but there is not a silver bullet, and the most general tools have serious problems with real-time requirements. This paper introduces a new proxy-based tool, based on Joint Intentions, to help agents to be a teammate in partilly observable, dynamic and stochastic environments with real-time requirements. The validation experiments for this proxy were performed in the computer game Unreal Tournament 2004, that provides an environment with such features.

Embora haja muitas pesquisas na área de teamwork, o desenvolvimento de times de agentes para ambientes complexos continua sendo um desafio, especialmente se esses ambientes possuem requisitos de tempo-real. Muitas ferramentas foram desenvolvidas, mas não existe uma bala de prata e aquelas mais gerais possuem sérios problemas com o requisito de tempo-real. Este trabalho introduz uma nova ferramenta baseada em proxy, usando a teoria de Joint Intentions, que ajuda agentes a serem membros de uma equipe dentro de um ambiente parcialmente observável, dinâmico, estocástico e com requisitos de tempo-real. Os experimentos de validação dessa ferramenta são executados no jogo de computador Unreal Tournament 2004, que fornece um ambiente com tais características. / Although there are many researches in teamwork, the development of agent teams for complex environments still presents many challenges, especially if these environments have real-time requirements. Many tools have been developed, but there is not a silver bullet, and the most general tools have serious problems with real-time requirements. This paper introduces a new proxy-based tool, based on Joint Intentions, to help agents to be a teammate in partilly observable, dynamic and stochastic environments with real-time requirements. The validation experiments for this proxy were performed in the computer game Unreal Tournament 2004, that provides an environment with such features.

Embora haja muitas pesquisas na área de teamwork, o desenvolvimento de times de agentes para ambientes complexos continua sendo um desafio, especialmente se esses ambientes possuem requisitos de tempo-real. Muitas ferramentas foram desenvolvidas, mas não existe uma bala de prata e aquelas mais gerais possuem sérios problemas com o requisito de tempo-real. Este trabalho introduz uma nova ferramenta baseada em proxy, usando a teoria de Joint Intentions, que ajuda agentes a serem membros de uma equipe dentro de um ambiente parcialmente observável, dinâmico, estocástico e com requisitos de tempo-real. Os experimentos de validação dessa ferramenta são executados no jogo de computador Unreal Tournament 2004, que fornece um ambiente com tais características. / Although there are many researches in teamwork, the development of agent teams for complex environments still presents many challenges, especially if these environments have real-time requirements. Many tools have been developed, but there is not a silver bullet, and the most general tools have serious problems with real-time requirements. This paper introduces a new proxy-based tool, based on Joint Intentions, to help agents to be a teammate in partilly observable, dynamic and stochastic environments with real-time requirements. The validation experiments for this proxy were performed in the computer game Unreal Tournament 2004, that provides an environment with such features.

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.

Cette thèse propose un modèle organisationnel et holonique de l'environnement pour la simulation des déplacements de piétons dans des bâtiments. Une foule de piétons peut être considérée comme un système composé d'un grand nombre d'entités en interaction, dont la dynamique globale ne peut se réduire à la somme des comportements de ses composants. La simulation multiniveau fondée sur les modèles multiagents holoniques constitue une approche permettant d'analyser la dynamique de tels systèmes. Elle autorise leur analyse en considérant plusieurs niveaux d'observation (microscopique, mésoscopique et macroscopique) et prend en compte les ressources de calcul disponibles. Dans ces systèmes, l'environnement est considéré comme l'une des parties essentielles. La dynamique des piétons composant la foule est alors clairement distinguée de celle de l'environnement dans lequel ils se déplacent. Un modèle organisationnel décrivant la structure et la dynamique de l'environnement est proposé. L'environnement est structurellement décomposé en zones, sous-zones, etc. Les organisations et les rôles de cet environnement sont projetés dans une société d'agents ayant en charge de simuler la dynamique de l'environnement et les différentes missions qui lui sont classiquement assignées dans les systèmes multiagents. Ce modèle précise également les règles de passage entre deux niveaux d'observation. Ainsi, chaque agent appartenant au modèle de l'environnement tente d'utiliser une approximation des comportements de ses sous-zones afin de limiter la consommation de ressources durant la simulation. La qualité de l'approximation entre ces deux niveaux d'observation est évaluée avec des indicateurs énergétiques. Ils permettent de déterminer si l'agent approxime correctement les comportements des agents associés aux sous-zones. En sus du modèle organisationnel et holonique proposé, nous présentons un modèle concret de la simulation de voyageurs dans un terminal d'aéroport. Ce modèle concret est implanté sur les plateformes JaSIM et Janus. / This work presents a holonic organizational model of the environment for the simulation of pedestrians in buildings. A crowd of pedestrians is considered as a system composed of a large number of interacting entities. The global dynamics of this system cannot be reduced to the sum of the behaviors of its components, Multilevel simulation based on holonic multiagent models is one approach to analyze the dynamics of such systems. It allows their analysis by considering several levels of observation (microscopic, mesoscopic and macroscopic) and the available computing resources. In these systems, the environment is considered as an essential part. The behavior of the crowd is clearly distinguished from the behavior of the environment in which the pedestrians move. An organizational model is proposed to describe the structure and the dynamics of the indoor environment. This environment is structurally divided into areas, sub-areas, etc. Organizations and roles are mapped into a society of agents in charge of simulating the dynamics of the environment and their various missions in multiagent systems. This model also specifies the rules for changing the level of observation dynamically. Thus, each agent belonging to the model of the environment tries to use an approximation of behaviors of its sub-zones, and at the same time to minimize the resource consumption. The quality of the approximation between these two levels is evaluated with energy-based indicators. They help to determine if the agent approximates the behaviors of its sub-agents correctly. In addition to the organizational and holonic model proposed in this work, we present a concrete model of the simulation of passengers in an airport terminal. This concrete model is implemented on the platforms JaSIM and Janus.