Resource allocation problems have been widely studied according to various scenarios in literature. In such problems, a set of resources must be allocated to a set of agents, according to their own preferences. Self-organization issues in telecommunication, scheduling problems or supply chain management problems can be modeled using resource allocation problems. Such problems are usually solved by means of centralized techniques, where an omniscient entity determines how to optimally allocate resources. However, these solving methods are not well-adapted for applications where privacy is required. Moreover, several assumptions made are not always plausible, which may prevent their use in practice, especially in the context of agent societies. For instance, dynamic applications require adaptive solving processes, which can handle the evolution of initial data. Such techniques never consider restricted communication possibilities whereas many applications are based on them. For instance, in peer-to-peer networks, a peer can only communicate with a small subset of the systems. In this thesis, we focus on distributed methods to solve resource allocation problems. Initial allocation evolves step by step thanks to local agent negotiations. We seek to provide agent behaviors leading negotiation processes to socially optimal allocations. In this work, resulting resource allocations can be viewed as emergent phenomena. We also identify parameters favoring the negotiation efficiency. We provide the negotiation settings to use when four different social welfare notions are considered. The original method proposed in this thesis is adaptive, anytime and can handle any restriction on agent communication possibilities.

Les simulateurs de conduite sont utilisées par l'industrie automobile pour le développement de systèmes d'aide à la conduite, des études d'ergonomie, de design, ou encore du comportement des conducteurs. L'objectif est d'améliorer la sécurité des véhicules, et de réduire coûts et délais des projets. Dans les simulateurs, le conducteur évolue dans un trafic simulé dont le réalisme est crucial pour la validité des résultats : les réactions d'un conducteur sont d'autant plus correctes qu'il perçoit l'environnement comme réel. Dans les approches centrées individu, comme ici le trafic, un des critères important pour le réalisme est la variété comportementale des agents. De plus, les comportements doivent également être cohérents : l'apparition de situations aberrantes est très pénalisante pour l'immersion. Cependant, ces deux aspects ne sont généralement pas pris en compte simultanément. Dans ce travail, nous nous sommes donc intéressés à la question suivante : dans les approches centrées individus, augmenter la variété des comportements des agents tout en préservant leur cohérence améliore-t-il le réalisme ? Par ailleurs, le contexte industriel des travaux, effectués en convention Cifre chez Renault, impliquait des besoins spécifiques : il fallait concevoir un outil qui permette à la fois aux experts de spécifier des comportements variés et cohérents, et aux utilisateurs finaux de les exploiter facilement. Nous proposons dans ce travail un modèle de différenciation comportementale, qui se décline en un outil dont les principaux apports sont d'être générique, non-intrusif, et de permettre une conception en dehors de l'agent. Le modèle s'articule selon trois axes. Tout d'abord, il décrit les comportements des agents par des normes. Celles-ci fournissent un profil comportemental à la conception, et un contrôle de la conformitéà l'exécution. Ensuite, le processus de génération des comportements permet d'autoriser la création d'agents déviants ou en violation. Il influe pour cela sur le déterminisme du mécanisme. Enfin, les normes peuvent être inférées à partir de simulations enregistrées ou de situations réelles, afin d'analyser les résultats des expérimentations et d'automatiser la configuration du modèle. Nous avons appliqué cet outil à la simulation de trafic dans scaner, l'application développée et utilisée par le Centre Technique de Simulation de Renault pour ses simulateurs de conduite. Les modules logiciels développés au cours de la thèse introduisent dans le trafic des styles de conduite spécifiés sous forme de normes, par exemple des conducteurs prudents ou agressifs. Ils permettent ensuite de peupler l'environnement de manière automatisée, et de faire évoluer facilement les scénarios existants. Ces développements sont d'ores et déjà intégrés dans la version commerciale de l'application. Au delà de l'amélioration subjective du réalisme, les expérimentations réalisées démontrent les apports de l'outil sur la variété et la représentativité des comportements obtenus.

This dissertation presents a suite of design tools for multi-agent systems that address three main areas: network design, decentralized controller generation, and the synthesis of decentralized control strategies by combining individual decentralized controllers. First, a new metric for quantifying heterogeneity in multi-agent systems is presented based on combining different notions of entropy, and is shown to overcome the drawbacks associated with existing diversity metrics in various scientific fields. Moreover, a new method of controlling multi-agent networks through the single-leader network paradigm is presented where by directly exploiting the homogeneity of agent capabilities, a network which is not completely controllable can be driven closer to a desired target configuration than by using traditional control techniques. An algorithm is presented for generating decentralized control laws that allow for agents to best satisfy a desired global objective, while taking into account network topological constraints and limitations on how agents can compute their control signals. Then, a scripting tool is developed to aid in specifying sequences of decentralized controllers to be executed consecutively, while helping ensure that the required network topological requirements needed for each controller to execute properly are maintained throughout mode switches. Finally, the underlying concepts behind the developed tools are showcased in three example applications: distributed merging and spacing for heterogeneous aircraft during terminal approaches, collaborative multi-UAV convoy protection in dynamic environments, and an educational tool used to teach a graduate-level networked controls course at the Georgia Institute of Technology.

Ce mémoire de thèse s'intéresse à la prise en compte de la dimension temporelle au sein des systèmes multi-agents (SMA) dans le contexte de systèmes industriels dynamiques.L'étude s'appuie sur l'approche Voyelles afin d'étudier l'impact du temps au sein de chacune des dimensions d'un SMA que cette approche distingue et afin de mettre en place un raisonnement temporel orienté multi-agents.Après avoir analysé les conséquences de la prise en compte du temps dans chacun de ses aspects, un ensemble de méthodes et d'outils sont proposés pour résoudre les problèmes mis en évidence. Le modèle de SMA temporel proposé présente notamment une prise en compte des aspects temporels au sein de l'interaction et del'organisation ainsi qu'un modèle d'agent permettant de les intégrer. Ces propositions sont ensuite confrontées à des applications concrètes issues du milieu industriel.

Multiagent coordination problems arise in a variety of applications, from satellite constellations and formation flight, to air traffic control and unmanned vehicle teams. We investigate the coordination of mobile agents using two kinds of approaches. In the first, which takes its inspiration from fluid dynamics and algebraic topology, control authority is split between mobile agents and a network of static infrastructure nodes - like wireless base stations or air traffic control towers - and controllers are developed that distribute their computation throughout this network. In the second, we look at networks of interconnected mechanical systems, and develop novel optimal control algorithms, which involve the computation of optimal deformations of time- and output- spaces, to achieve approximate formation tracking. Finally, we investigate algorithms that optimize these controllers to meet subjective criteria of humans.

Many complex and interdependent systems engineering challenges involve more than one stakeholder or decision maker. These challenges, such as the definition and acquisition of future air mobility systems, are often found in situations where resources are finite, objectives are conflicting, constraints are restricting, and uncertainty in future outcomes prevail. Air mobility operational models which simulate fleet wide behavior effects over time, in various mission scenarios, and potentially over the entire design life-cycle, are always multi-dimensional, cover a large decision space, and require significant time to generate sufficient solutions to adequately describe the design space. This challenge is coupled with the fact that, in these highly integrated solutions or acquisitions, multiple stakeholders or decision makers are required to cooperate and reach agreement in selecting or defining the requirements for the design or solution and in its costly and lengthy implementation. However, since values, attitudes, and experiences are different for each decision maker, reaching consensus across the multiple criteria with different preferences and objectives is often a slow and highly convoluted process. In response to these common deficiencies and to provide quantitative analyses, this research investigates and proposes solutions to two challenges: 1) increase the speed at which operational solutions and associated requirements are generated and explored, and 2) systematize the group decision-making process, to both accelerate and improve decision making in these large operational problems requiring cooperation. The development of the Air Mobility Operations Design (AirMOD) model is proposed to address the first challenge by implementing and leveraging surrogate models of airlift capability across a wide scenario space. In addressing the second major challenge, the proposed Multi-Agent Consensus Reaching on the Objective Space (MACRO) methodology introduces a process to reduce the feasible decision space, by identifying regions of high probability of consensus reaching, using preference distributions, power relationships, and game-theoretic techniques. In a case study, the MACRO methodology is demonstrated on a large air mobility solution space generated by AirMOD to illustrate plausibility of the overall approach. AirMOD and MACRO offer considerable advantages over current methods to better define the operational design space and improve group decision-making processes requiring cooperation, respectively.

Les travaux présentés dans cette thèse portent sur le thème de la modélisation et de l'aide à la décision dans le cadre des systèmes complexes. Plus précisément, nous nous intéressons au couplage de simulations orientées agent à une méthode de résolution de problèmes inverses. Une architecture générique de système d'aide à la décision est ainsi proposée. Ces travaux sont appliqués à la conception d'un système d'aide à la décision dédié à l'entomologie médico-légale. Cette discipline à mi-chemin entre la criminalistique et l'entomologie vise à concevoir des méthodes de datation de la mort basées sur des indices entomologiques, i.e., les insectes (principalement des diptères nécrophages) ou restes d'insectes retrouvés sur ou à proximité du corps. Ainsi, dans le cadre de ce travail réalisé en collaboration avec le laboratoire d'entomologie médico-légale de l'Institut de Médecine Légale de Lille, nous présentons : * un modèle à base d'agents permettant de simuler le développement des diptères nécrophages dans un environnement complexe (e.g., un corps situé dans un écosystème donné), en prenant en compte plus de paramètres que les méthodes classiques, * une implémentation de l'architecture de système d'aide à la décision évoquée plus haut, basée sur ce modèle.

Le travail présenté dans ce mémoire s'inscrit dans le cadre du projet SocLab, qui propose une formalisation de la sociologie de l'action organisée (SAO). Cette formalisation repose sur un méta-modèle de la structure des organisations sociales, à partir duquel il est possible de développer une étude analytique des propriétés d'une organisation et de calculer, par simulation, les comportements que les acteurs sont susceptibles d'adopter. On est alors en mesure de réaliser un diagnostique organisationnel qui, s'il est moins riche que dans l'expression discursive de la SAO, gagne en objectivation et en rigueur. Selon cette approche, une organisation est vue comme un système qui, en fonction du comportement des acteurs les uns vis à vis des autres, procure à chacun d'eux une certaine capacité d'action pour atteindre ses objectifs, sans distinguer ceux qui relèvent de son rôle et ceux qui lui sont propres. Un tel système est parcouru par deux boucles de régulation : une première, que l'on peut qualifier de fonctionnelle, selon laquelle les acteurs adaptent leurs comportements les uns aux autres afin d'obtenir une capacité d'action qui les satisfassent ; une seconde, qui relève de l'évolution endogène de l'organisation, selon laquelle les acteurs cherchent à modifier à leur avantage la structure même de l'organisation. L'utilisation du méta-modèle donne lieu à la représentation de la structure d'une organisation sous la forme d'une structure mathématique, constituée d'ensembles, de fonctions (différentiables) et de relations. En mobilisant divers outils mathématiques, nous étudions l'influence de la structure d'une organisation sur chacune de ces deux boucles de régulation. On pourra par exemple, s'agissant de la régulation fonctionnelle, expliquer pourquoi les acteurs se comportent comme ils le font et détecter des coalitions, avérées ou potentielles, ou bien avoir une idée des directions dans lesquelles un acteur pourrait tenter de modifier la structure de l'organisation. Plus généralement, l'étude mathématique de la structure d'une organisation nous permet de définir une grande variété d'indicateurs qui s'interprètent, à l'aide des concepts de la sociologie des organisations, comme autant de propriétés de l'organisation considérée.

Logic-based formalizations of dynamical systems are central to the field of knowledge representation and reasoning. These formalizations can be used to model agents that act, reason,and perceive in a changing and incompletely known environment. A key aspect of reasoning about agents and their behaviors is the notion of joint ability. A team of agents is jointly able to achieve a goal if despite any incomplete knowledge or even false beliefs about the world or each other, they still know enough to be able to get to a goal state, should they choose to do so. A particularly challenging issue associated with joint ability is how team members can coordinate their actions. Existing approaches often require the agents to communicate to agree on a joint plan. In this thesis, we propose an account of joint ability that supports coordination among agents without requiring communication, and that allows for agents to have incomplete (or even false) beliefs about the world or the beliefs of other agents. We use ideas from game theory to address coordination among agents. We introduce the notion of a strategy for each agent which is basically a plan that the agent knows how to follow. Each agent compares her strategies and iteratively discards those that she believes are not good considering the strategies that the other agents have kept. Our account is developed in the situation calculus, a logical language suitable for representing and reasoning about action and change that is extended to support reasoning about multiple agents. Through several examples involving public, private, and sensing actions, we demonstrate how symbolic proof techniques allow us to reason about team ability despite incomplete specifications about the beliefs of agents.

L'objectif de cette thèse est de proposer une démarche méthodologique de conception d'un modèle de simulation de systèmes de production qui intègre une représentation des comportements distribués et cognitifs des acteurs décisionnels, et dont l'intérêt est de permettre d'étudier la pertinence de changements organisationnels dans ces systèmes. En effet, l'analyse des conditions d'évolution des systèmes de production et de leur contexte a permis de mettre en relief le besoin de " réactivité " pour faire face à un environnement de moins en moins stable et prévisible et devant lequel l'organisation doit chercher des alternatives à un fonctionnèment planifié, prédictif, figé et séquentiel. Les réponses organisationnelles des entreprises à ces sollicitations s'expriment par un mouvement vers la fleXIbilité et l'intégration, et passent par un rapprochement entre la structure décisionnelle et la structure physique. Pour mettre en évidence cette nouvelle réalité, nous proposons un processus de modélisation qui débute par la construction d'un modèle conceptuel de compréhension des organisations, basé sur une représentation des processus de décision, et sur une formalisation des phénomènes d'orientation des comportements décisionnels. En parallèle, nous analysons les concepts associés à la problématique des systèmes multi-agents, systèmes qui étudient l'émergence de comportements collectifs résultant de l'activité coopérative de plusieurs entités autonomes "intelligentes" sur lesquelles l'expertise est répartie. Ces études convergent vers un modèle de simulation issu des techniques de simulation à événements discrets, dans lequel nous intégrons une modélisation du système décisionnel à base d'agents. Enfin, l'implémentation de ce modèle sera basée sur des techniques de simulation orientée objets (objets actifs, programmation concurrente), et sera validée sur deux exemples, l'un pédagogique et conceptuel, 1 'autre industriel.