This thesis describes experiments designed to measure the effect of collaborative communication on task performance of a multiagent system. A discrete event simulation was developed to model a multi-agent system completing a task to find and collect food resources, with the ability to substitute various communication and coordination methods. Experiments were conducted to find the effects of the various communication methods on completion of the task to find and harvest the food resources. Results show that communication decreases the time required to complete the task. However, all communication methods do not fare equally well. In particular, results indicate that the communication model of the bee is a particularly effective method of agent communication and collaboration. Furthermore, results indicate that direct communication with additional information content provides better completion results. Cost-benefit models show some conflicting information, indicating that the increased performance may not offset the additional cost of achieving that performance.

This dissertation describes a novel technique to creating a simulated team of agents through observation. Simulated human teamwork can be used for a number of purposes, such as expert examples, automated teammates for training purposes and realistic opponents in games and training simulation. Current teamwork simulations require the team member behaviors be programmed into the simulation, often requiring a great deal of time and effort. None are able to observe a team at work and replicate the teamwork behaviors. Machine learning techniques for learning by observation and learning by demonstration have proven successful at observing behavior of humans or other software agents and creating a behavior function for a single agent. The research described here combines current research in teamwork simulations and learning by observation to effectively train a multi-agent system in effective team behavior. The dissertation describes the background and work by others as well as a detailed description of the learning method. A prototype built to evaluate the developed approach as well as the extensive experimentation conducted is also described.

This thesis focuses on decision-theoretic reasoning and planning problems that arise when a group of collaborative agents are tasked to achieve a goal that requires collective effort. The main contribution of this thesis is the development of effective, scalable and quality-bounded computational approaches for multiagent planning and coordination under uncertainty. This is achieved by a synthesis of techniques from multiple areas of artificial intelligence, machine learning and operations research. Empirically, each algorithmic contribution has been tested rigorously on common benchmark problems and, in many cases, real-world applications from machine learning and operations research literature. The first part of the thesis addresses multiagent single-step decision making problems where a single joint-decision is required for the plan. We examine these decision-theoretic problems within the broad frameworks of distributed constraint optimization and Markov random fields. Such models succinctly capture the structure of interaction among different decision variables, which is subsequently exploited by algorithms to enhance scalability. The algorithms presented in this thesis are rigorously grounded on concepts from mathematical programming and optimization. The second part of the thesis addresses multiagent sequential decision making problems under uncertainty and partial observability. We use the decentralized partially observable Markov decision processes (Dec-POMDPs) to formulate multiagent planning problems. To address the challenge of NEXP-Hard complexity and yet push the envelope of scalability, we represent the domain structure in a multiagent system using graphical models such as dynamic Bayesian networks and constraint networks. By exploiting such graphical planning representation in an algorithmic framework composed of techniques from different sub-areas of artificial intelligence, machine learning and operations research, we show impressive gains in increasing the scalability, the range of problems addressed and enabling quality-bounded solutions for multiagent decision theoretic planning. Our contributions for sequential decision making include a) development of efficient dynamic programming algorithms for finite-horizon decision making, resulting in significantly increased scalability w.r.t. the number of agents and multiple orders-of-magnitude speedup over previous best approaches; b) development of probabilistic inference based algorithms for infinite-horizon decision making, resulting in new insights connecting inference techniques from the machine learning literature to multiagent systems; c) development of mathematical programming based scalable techniques for quality bounded solutions in multiagent systems, which has been considered intractable so far. Several of our contributions are some of the first for the respective class of problems. For example, we show for the first time how machine learning is closely related to multiagent decision making via a maximum likelihood formulation of the planning problem. We develop new graphical models and machine learning based inference algorithms for large factored planning problems. We also show for the first time how the problem of optimizing agents' policies can be formulated as a compact mixed-integer program, resulting in optimal solution for a range of Dec-POMDP benchmarks. In summary, we present a synthesis of different techniques from multiple sub-areas of AI, ML and OR to address the scalability and efficiency of algorithms for decision-theoretic reasoning and planning in multiagent systems. Such advances have already shown great promise to bridge the gap between multiagent systems and real-world applications.

Networked control systems, commonly employed in domains such as space exploration and robotics utilize network communication for efficient and coordinated control among distributed components. In these scenarios, effectively managing communication to prevent network overload poses a critical challenge. Previous research has explored the use of reinforcement learning methods combined with event-triggered control to autonomously have agents learn efficient policies for control and communication. Nevertheless, these approaches have encountered limitations in terms of performance and scalability when applied in multiagent scenarios. This thesis examines the underlying causes of these challenges and propose potential solutions. With the findings suggesting that training agents in a decentralized manner, coupled with modeling of the missing communication, can improve agent performance. This allows the agents to achieve performance levels comparable to those of agents trained with full communication, while reducing unnecessary communication

En la nueva era de tecnologías de la información, los sistemas tienden a ser cada vez más dinámicos, compuestos por entidades heterogéneas capaces de entrar y salir del sistema, interaccionar entre ellas, y adaptarse a las necesidades del entorno. Los sistemas multiagente han contribuído en los ultimos años, a modelar, diseñar e implementar sistemas autónomos con capacidad de interacción y comunicación. Estos sistemas se han modelado principalmente, a través de sociedades de agentes, las cuales facilitan la interación, organización y cooperación de agentes heterogéneos para conseguir diferentes objetivos. Para que estos paradigmas puedan ser utilizados para el desarrollo de nuevas generaciones de sistemas, características como dinamicidad y capacidad de reorganización deben estar incorporadas en el modelado, gestión y ejecución de estas sociedades de agentes. Concretamente, la reorganización en sociedades de agentes ofrece un paradigma para diseñar aplicaciones abiertas, dinámicas y adaptativas. Este proceso requiere determinar las consecuencias de cambiar el sistema, no sólo en términos de los beneficios conseguidos sinó además, midiendo los costes de adaptación así como el impacto que estos cambios tienen en todos los componentes del sistema. Las propuestas actuales de reorganización, básicamente abordan este proceso como respuestas de la sociedad cuando ocurre un cambio, o bien como un mecanismo para mejorar la utilidad del sistema. Sin embargo, no se pueden definir procesos complejos de decisión que obtengan la mejor configuración de los componentes organizacionales en cada momento, basándose en una evaluación de los beneficios que se podrían obtener así como de los costes asociados al proceso. Teniendo en cuenta este objetivo, esta tesis explora el área de reorganización en sociedades de agentes y se centra principalmente, en una propuesta novedosa para reorganización. Nuestra propuesta ofrece un soporte de toma de decisiones que considera cambios en múltiples / Alberola Oltra, JM. (2013). Reorganization in Dynamic Agent Societies [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/19243

O crescente interesse em prover uma maior autonomia a agentes articiais, além da sua capacidade de adaptação, racionalidade limitada, heterogeneidade, e necessidade de interação e cooperação podem fazer com que Sistemas Multiagentes (MASs) apresentem comportamentos globais indesejáveis. Esse cenário pode agravar-se, em especial quando esses sistemas envolvem a participação de humanos, uma vez que esses agem de forma menos controláveis e previsíveis, por exemplo, Sistemas Sócio-Técnicos (STSs). Essas características tornam a governaça desses sistemas um aspecto essencial para sua ecácia. A abordagem normativa é considerada uma proposta promissora para o atendimento desse requisito em tais sistemas. Nesse, normas fornecem uma visão socialmente realista das interação entre agentes autônomos abstraindo os detalhes de baixo nível. Suportada pelas normas está a noção de sanção como uma reação a potencialmente qualquer violação ou cumprimento de uma expectativa. Embora as normas já tenham sido extensamente investigadas no contexto de MASs, o conceito de sanção ainda carece de uma melhor inspeção. Esse carência é suprida nesse trabalho, primeiramente, propondo uma tipologia de sanções que captura as características relevantes de STSs, segundo, um processo adaptativo de sancionamento com a descrição das funções de seus componentes e inter-relacionamentos, e terceiro, um modelo adaptativo de avaliação de sancionamento que permite aos agentes decidirem qual sanção aplicar em cada situação. Em particular, esse model de avaliação permite a seleção entre sanções formais e informais dependendo de quanto o agente pode inuenciar o grupo social do agente objeto da sanção. Esse modelo é usado na avaliação de políticas de sanção única ou múltiplas em um estudo de caso de transação de energia elétrica no contexto de uma rede elétrica inteligente. Conclui-se dos resultados obtidos que sistemas que disponibilizam políticas de sancionamento com múltiplas sanções não aumentam em todos os casos o nível de cumprimento das normas quando comparado com políticas de sancionamento com sanção única. Entretanto, políticas com multíplas sanções são menos custosas. / The increasing interest on greater agents autonomy in addition to its adaptability, bounded rationality, and heterogeneity features, and the necessity of interaction and cooperation may bring Multiagent Systems (MASs) to exhibit undesirable global behaviors. It may become even worse especially when they involve human agents who are less manageable and predictable in their actions, like in Sociotechnical Systems (STSs). These characteristics renderaneffectivegovernanceanessentialaspectofthesesystems.Thenormativeapproach has been proposed as a prominent means to achieve this effectiveness, wherein norms provide a socially realistic view of interaction among autonomous parties that abstracts away low-level implementation details. Overlaid on norms is the notion of a sanction as a reaction to potentially any violation of or compliance with an expectation. Although norms have been well investigated in the context of MASs, sanctions still lack a more comprehensive inspection. We address the above-mentioned gap by proposing, rst, a typology of sanctions that reects the interplay of relevant features of STSs, second, a sanctioning enforcement process describing the functions of the diversity of components and their relationships, and third a sanctioning evaluation model that enables agents to evaluate and choose the most appropriate sanction to apply depending on a set of factors. In particular, this evaluation model enables the selection between formal or social sanctions based on how much the sanctioner can inuence the social group of the sanctioned agent. This model is used to evaluate mono-type and multi-type sanctioning policies in a Smart Grid energy trading case study. Our results show that multi-type sanctioning policies do not always increase the level of norm compliance compared to mono-type sanctioning policies, yet multi-type policies are less costly.

O crescente interesse em prover uma maior autonomia a agentes articiais, além da sua capacidade de adaptação, racionalidade limitada, heterogeneidade, e necessidade de interação e cooperação podem fazer com que Sistemas Multiagentes (MASs) apresentem comportamentos globais indesejáveis. Esse cenário pode agravar-se, em especial quando esses sistemas envolvem a participação de humanos, uma vez que esses agem de forma menos controláveis e previsíveis, por exemplo, Sistemas Sócio-Técnicos (STSs). Essas características tornam a governaça desses sistemas um aspecto essencial para sua ecácia. A abordagem normativa é considerada uma proposta promissora para o atendimento desse requisito em tais sistemas. Nesse, normas fornecem uma visão socialmente realista das interação entre agentes autônomos abstraindo os detalhes de baixo nível. Suportada pelas normas está a noção de sanção como uma reação a potencialmente qualquer violação ou cumprimento de uma expectativa. Embora as normas já tenham sido extensamente investigadas no contexto de MASs, o conceito de sanção ainda carece de uma melhor inspeção. Esse carência é suprida nesse trabalho, primeiramente, propondo uma tipologia de sanções que captura as características relevantes de STSs, segundo, um processo adaptativo de sancionamento com a descrição das funções de seus componentes e inter-relacionamentos, e terceiro, um modelo adaptativo de avaliação de sancionamento que permite aos agentes decidirem qual sanção aplicar em cada situação. Em particular, esse model de avaliação permite a seleção entre sanções formais e informais dependendo de quanto o agente pode inuenciar o grupo social do agente objeto da sanção. Esse modelo é usado na avaliação de políticas de sanção única ou múltiplas em um estudo de caso de transação de energia elétrica no contexto de uma rede elétrica inteligente. Conclui-se dos resultados obtidos que sistemas que disponibilizam políticas de sancionamento com múltiplas sanções não aumentam em todos os casos o nível de cumprimento das normas quando comparado com políticas de sancionamento com sanção única. Entretanto, políticas com multíplas sanções são menos custosas. / The increasing interest on greater agents autonomy in addition to its adaptability, bounded rationality, and heterogeneity features, and the necessity of interaction and cooperation may bring Multiagent Systems (MASs) to exhibit undesirable global behaviors. It may become even worse especially when they involve human agents who are less manageable and predictable in their actions, like in Sociotechnical Systems (STSs). These characteristics renderaneffectivegovernanceanessentialaspectofthesesystems.Thenormativeapproach has been proposed as a prominent means to achieve this effectiveness, wherein norms provide a socially realistic view of interaction among autonomous parties that abstracts away low-level implementation details. Overlaid on norms is the notion of a sanction as a reaction to potentially any violation of or compliance with an expectation. Although norms have been well investigated in the context of MASs, sanctions still lack a more comprehensive inspection. We address the above-mentioned gap by proposing, rst, a typology of sanctions that reects the interplay of relevant features of STSs, second, a sanctioning enforcement process describing the functions of the diversity of components and their relationships, and third a sanctioning evaluation model that enables agents to evaluate and choose the most appropriate sanction to apply depending on a set of factors. In particular, this evaluation model enables the selection between formal or social sanctions based on how much the sanctioner can inuence the social group of the sanctioned agent. This model is used to evaluate mono-type and multi-type sanctioning policies in a Smart Grid energy trading case study. Our results show that multi-type sanctioning policies do not always increase the level of norm compliance compared to mono-type sanctioning policies, yet multi-type policies are less costly.

Doctor of Philosophy / Department of Computing and Information Sciences / Scott A. DeLoach / Organization-based Multiagent Systems (OMAS) have been viewed as an effective paradigm for addressing the design challenges posed by today’s complex systems. In those systems, the organizational perspective is the main abstraction, which provides a clear separation between agents and systems, allowing a reduction in the complexity of the overall system. To ease the development of OMAS, several methodologies have been proposed. Unfortunately, those methodologies typically require the designer to handle system complexity alone, which tends to lead to ad-hoc designs that are not scalable and are difficult to maintain. Moreover, designing organizations for large multiagent systems is a complex and time-consuming task; design models quickly become unwieldy and thus hard to develop. To cope with theses issues, a framework for organization-based multiagent system designs based on separation of concerns and composition principles is proposed. The framework uses category theory tools to construct a formal composition framework using core models from the Organization-based Multiagent Software Engineering (O-MASE) framework. I propose a formalization of these models that are then used to establish a reusable design approach for OMAS. This approach allows designers to design large multiagent organizations by reusing smaller composable organizations that are developed separately, thus providing them with a scalable approach for designing large and complex OMAS. In this dissertation, the process of formalizing and composing multiagent organizations is discussed. In addition, I propose a service-oriented approach for building autonomous, adaptive multiagent systems. Finally, as a proof of concept, I develop two real world examples from the domain of cooperative robotics and wireless sensor networks.

Fundamental aspects of biologically-inspired regulatory mechanisms are considered in a robotics context, using artificial neural-network control systems . Regulatory mechanisms are used to control expression of genes, adaptation of form and behavior in organisms. Traditional neural network control architectures assume networks of neurons are fixed and are interconnected by wires. However, these architectures tend to be specified by a designer and are faced with several limitations that reduce scalability and tractability for tasks with larger search spaces. Traditional methods used to overcome these limitations with fixed network topologies are to provide more supervision by a designer. More supervision as shown does not guarantee improvement during training particularly when making incorrect assumptions for little known task domains. Biological organisms often do not require such external intervention (more supervision) and have self-organized through adaptation. Artificial neural tissues (ANT) addresses limitations with current neural-network architectures by modeling both wired interactions between neurons and wireless interactions through use of chemical diffusion fields. An evolutionary (Darwinian) selection process is used to ‘breed’ ANT controllers for a task at hand and the framework facilitates emergence of creative solutions since only a system goal function and a generic set of basis behaviours need be defined. Regulatory mechanisms are formed dynamically within ANT through superpositioning of chemical diffusion fields from multiple sources and are used to select neuronal groups. Regulation drives competition and cooperation among neuronal groups and results in areas of specialization forming within the tissue. These regulatory mechanisms are also shown to increase tractability without requiring more supervision using a new statistical theory developed to predict performance characteristics of fixed network topologies. Simulations also confirm the significance of regulatory mechanisms in solving certain tasks found intractable for fixed network topologies. The framework also shows general improvement in training performance against existing fixed-topology neural network controllers for several robotic and control tasks. ANT controllers evolved in a low-fidelity simulation environment have been demonstrated for a number of tasks on hardware using groups of mobile robots and have given insight into self-organizing system. Evidence of sparse activity and use of decentralized, distributed functionality within ANT controller solutions are found consistent with observations from neurobiology.

Multiagent systems offer a design paradigm used to conceptualise and implement systems composed of autonomous agents. Autonomy facilitates proactive independent behaviour yet in practice agents are constrained in order to ensure the system satisfies a desired social objective. Explicit constraints on agent behaviour, in the form of social norms, encourage this desirable system behaviour, yet research has largely focused on norm representation languages and protocols for norm proposal and adoption. The fundamental problem of how to automate the process of norm synthesis has largely been overlooked with norms assumed provided by the designer. Previous work has shown that automating the design of social norms is intractable in the worst case. Existing approaches, relying on state space enumerations, are effective for small systems but impractical for larger ones. Furthermore, they do not produce a set of succinct, general norms but rather a large number of state-specific restrictions. This work presents conflict-rooted synthesis, an automated norm synthesis approach that utilises a planning-based action schemata to overcome these limitations. These action schemata facilitate localised searches around specifications of undesirable states, using representations of sets of system states to avoid a full state enumeration. The proposed technique produces concise, generalised social norms that are applicable in multiple system states while also providing guarantees that agents are still able to achieve their original goals in the constrained system. To improve efficiency a set of theoretically sound, domain-independent optimisations are presented that reduce the state space searched without compromising the quality of the norms synthesised. A comparison with an alternative model checking based technique illustrates the advantages and disadvantages of our approach, while an empirical evaluation highlights the improved efficiency and quality of norms it produces at the cost of a less expressive specification of undesirable states. We empirically investigate the effectiveness of each of the proposed optimisations using a set of benchmark domains, quantifying how successful each of them is at reducing search complexity in practice. The results show that, with all optimisations enabled, conflict-rooted synthesis produces more generally applicable and succinct norms and consumes fewer system resources. Additionally, we show that this approach synthesises norms in systems where the competing approach is intractable. We provide a discussion of our approach, highlighting the impact our abstract search approach has on the fields of multiagent systems and automated planning, and discuss the limitations and assumptions we have made. We conclude with a presentation of future work.