Many biological systems are known to accomplish complex tasks in a decentralized, robust, and scalable manner - characteristics that are desirable to the coordination of engineered systems as well. Inspired by nature, we produce coordination strategies for a network of heterogenous agents and in particular, we focus on intelligent collective systems. Bottlenose dolphins and African lions are examples of intelligent collective systems since they exhibit sophisticated social behaviors and effortlessly transition between functionalities. Through preferred associations, specialized roles, and self-organization, these systems forage prey, form alliances, and maintain sustainable group sizes. In this thesis, we take a three-phased approach to bioinspiration: in the first phase, we produce agent-based models of specific social behaviors observed in nature. The goal of these models is to capture the underlying biological phenomenon, yet remain simple so that the models are amenable to analysis. In the second phase, we produce bio-inspired algorithms that are based on the simple biological models produced in the first phase. Moreover, these algorithms are developed in the context of specific coordination tasks, e.g., the multi-agent foraging task. In the final phase of this work, we tailor these algorithms to produce coordination strategies that are ready to be deployed in target applications.

Our research focuses on one of the more fundamental issues in multi-agent, mobile robotics: the formation control problem. The idea is to create controllers that cause robots to move into a predefined formation shape. This is a well studied problem for the scenario in which the robots know in advance to which point in the formation they are assigned. In our case, we assume this information is not given in advance, but must be determined dynamically. This thesis presents an algorithm that can be used by a network of mobile robots to simultaneously determine efficient robot assignments and formation pose for rotationally and translationally invariant formations. This allows simultaneous role assignment and formation sysnthesis without the need for additional control laws. The thesis begins by introducing some general concepts regarding multi-agent robotics. Next, previous work and background information specific to the formation control and assignment problems are reviewed. Then the proposed assignment al- gorithm for role assignment and formation control is introduced and its theoretical properties are examined. This is followed by a discussion of simulation results. Lastly, experimental results are presented based on the implementation of the assignment al- gorithm on actual robots.

This thesis makes a number of contributions to the theory of approximation algorithm design for multi-agent systems. In particular, we focus on two research directions. The first direction is to generalize the classical framework of combinatorial optimization to the submodular setting, where we assume that each agent has a submodular cost function. We show hardness results from both the information-theoretic and computational aspects for several fundamental optimization problems in the submodular setting, and provide matching approximation algorithms for most of them. The second direction is to introduce game-theoretic issues to approximation algorithm design. Towards this direction, we study the application of approximation algorithms in the theory of truthful mechanism design. We study both the standard objectives of revenue and social welfare, by designing efficient algorithms that satisfy the requirement of truthfulness and guarantee approximate optimality.

The goal of this thesis is twofold: first, we want to present the distributed belief accommodation and revision model for multi-agent systems that has been developed and, second, we wish to show its applicability to an appropriate domain. The Distributed Belief Accommodation & Revision model, called DeBAteR model, was developed for co-operative heterogeneous multi-agent systems used to model inherently dynamic distributed problems. In these systems, although the agents are able to detect changes both in the environment and in the problem specifications, each agent has only a partial view of the global picture. As a result the information that represents the current state of affairs is dynamic, incomplete and sometimes uncertain. This non-monotonic kind of data is called beliefs ? a belief is a piece of data that is held as correct as long as no contradicting evidence is found or presented. Each agent is expected to include an assumption based truth maintenance module for representing properly this type of data. Our main effort was concentrated on the task of maintaining the system's information, which consists of updating, revising and accommodating the represented beliefs. Belief updating is necessary for including the changes detected by the agents both in the environment and/or in the problem specifications. Belief revision is essential for solving the inconsistencies detected among the represented beliefs. Belief accommodation and revision is crucial for integrating the multiple disparate perspectives regarding the same data items, which may occur whenever there is overlap of expertise domains between the agents. In order to solve the information conflicts that result from the detection of inconsistencies between distinct beliefs or within multi-perspective beliefs we conceived the DeBATeR model. The DeBAteR is fully distributed, provides individual belief autonomy and is made of two methodologies: the pro-active belief accommodation and revision methodology and the delayed belief revision methodology. Whilst the first methodology is used to solve domain independent conflicts, the second methodology was devised for solving domain dependent conflicts. Both methodologies use argumentation for, in the case of the domain independent conflicts, choosing the most credible perspective between the existing multiple perspectives of a belief, and, in the case of the domain dependent conflicts, finding the best alternative belief support set for the affected concepts. These methodologies are distributed and their scope may be internal or collective. The DeBAteR model main contributions are: (i) the pro-active methodology conceived for solving domain independent conflicts and (ii) the capability, not only to represent and maintain individual beliefs and joint beliefs, but also to accommodate, rationally maintain and make use of multi-perspective beliefs. Finally, we describe the developed decision support multi-agent system for choosing adequate project locations, called DIPLOMAT ? Dynamic and Interactive Project Location Test bed, which has the ability of accommodating and revising the represented beliefs according to the DeBAteR model methodologies. / O objectivo desta dissertação é duplo: por um lado, pretendemos dar a conhecer o modelo de revisão e acomodação de crenças para sistemas multi-agente por nós desenvolvido e, por outro, procuramos ilustrar a sua validade descrevendo a aplicação que realizámos. O modelo, designado DeBAteR ? Distributed Belief Accommodation & Revision, destina-se a sistemas multi-agente cooperativos e heterogéneos que modelam problemas inerentemente distribuídos e dinâmicos. Neste tipo de sistemas, a informação que representa o ambiente é dinâmica (os agentes possuem a capacidade de constatar alterações no ambiente e/ou nas condições do problema) e, muitas vezes, incompleta (os agentes possuem visões parcelares da realidade) e/ou incerta. Este tipo de informação, de carácter não definitivo, designa-se por crenças ? uma crença é uma convicção tida como correcta enquanto não for posta em causa por alguma evidência. Cada agente, a fim de representar e manipular crenças, foi enriquecido com um módulo específico de manutenção de consistência baseado em suposições. O nosso esforço concentrou-se na tarefa de manutenção (actualização, revisão e acomodação) da informação do sistema. A actualização de crenças é essencial para incorporar as alterações que os agentes detectam no ambiente e/ou nas condições do problema. A revisão de crenças é indispensável para resolver inconsistências (conflitos) entre as crenças representadas. A acomodação e revisão simultânea de crenças é imprescindível para a integração das múltiplas perspectivas díspares que surgem em relação a um mesmo item de informação (crenças pluri-perspectiva) quando existe sobreposição de domínios de especialidade entre os agentes. Para tentar solucionar estes conflitos entre crenças concebemos um modelo distribuído que assegura autonomia individual de crença. O modelo de acomodação e revisão de crenças DeBAteR é composto por duas metodologias: a metodologia pró-activa de acomodação e revisão de crenças pluri-perspectiva e a metodologia retardada de revisão de crenças. A primeira, destina-se a resolver conflitos independentes do domínio e a segunda destina-se à resolução de conflitos dependentes do domínio. Estas metodologias são suportadas quase integralmente por um sistema de argumentação que procura, no caso dos conflitos independentes do domínio, escolher a perspectiva mais credível e, no caso dos conflitos dependentes do domínio, encontrar o melhor conjunto alternativo de suporte para os conceitos afectados. Esta actividade é descentralizada e pode decorrer quer no âmbito intra-agente, quer no âmbito inter-agente. É ainda de realçar: (i) o carácter pró-activo da resolução dos conflitos independentes do domínio (crenças pluri-perspectiva) e (ii) a capacidade de, não só, representar e manter crenças de âmbito individual (crenças suportadas por apenas um agente) e crenças conjuntas (crenças suportadas por vários agentes), mas também, de sintetizar, manter racionalmente e utilizar crenças pluri-perspectiva. Por último, descrevemos o sistema multi-agente de apoio à decisão no domínio da localização de empreendimentos desenvolvido, denominado DIPLOMAT ? Dynamic and Interactive Project Location Test bed, o qual possui a capacidade de acomodar e rever crenças de acordo com as metodologias concebidas no âmbito do modelo DeBAteR.

published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

Process planning and scheduling are two important manufacturing planning functions which are traditionally performed separately and sequentially. Usually, the process plan has to be prepared first before scheduling can be performed. However, due to the complexity of manufacturing systems and the uncertainties and dynamical changes encountered in practical production, process plans and schedules may easily become inefficient or even infeasible. The concept of integrated process planning and scheduling (IPPS) has been proposed to improve the efficiency, effectiveness as well as flexibility of the respective process plan and schedule. By combining both functions together, the process plan for producing a part could be dynamically arranged in accordance with the availability of manufacturing resources and current status of the system, and its operations’ schedule could be determined concurrently. Therefore, IPPS could provide an essential solution to the dynamic process planning and scheduling problem in the practical manufacturing environment. Nevertheless, process planning and scheduling are both complex functions that depend on many factors and flexibilities in the manufacturing system, IPPS is therefore a highly complex NP-hard problem. Ant colony optimization (ACO) is a widely applied meta-heuristics, which has been proved capable of generating feasible solutions for IPPS problem in previous research. However, due to the nature of the ACO algorithm, the performance is not that favourable compared with other heuristics. This thesis presents an enhanced ACO approach for IPPS. The weaknesses and limitations of standard ACO algorithm are identified and corresponding modifications are proposed to deal with the drawbacks and improve the performance of the algorithm. The mechanism is implemented on a specifically designed multi-agent system (MAS) framework in which ants are assigned as software agents to generate solutions. First of all, the manufacturing processes of the parts are graphically formulated as a disjunctive AND/OR graph. In applying the ACO algorithm, ants are deployed to find a path on the disjunctive graph. Such an ant route indicates a corresponding solution with associated operations scheduled by the sequence of ant visit. The ACO in this thesis is enhanced with the novel node selection heuristic and pheromone update strategy. With the node selection heuristic, pheromone is deposited on the nodes as well as edges on the ant path. This is contrast to the conventional ACO algorithm that pheromone is only deposited on edges. In addition, a more reasonable strategy based on “earliest completion time” of operations are used to determine the heuristic desirability of ants, instead of the “greedy” strategy used in standard ACO, which is based on the “shortest processing time”. The approach is evaluated by a comprehensive set of problems with a full set of flexibilities, while multiple performance measurements are considered, including makespan, mean flow time, average machine utilization and CPU time, among which makespan is the major criterion. The results are compared with other approaches and encouraging improvements on solution quality could be observed. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

This thesis examines the problem of having an intelligent agent reasoning about interaction with users in real-time decision making environments. Our work is motivated by the models of Fleming and Cheng, which reason about interaction sensitive to both expected quality of decision (following interaction) and cost of bothering users. In particular, we are interested in dynamic, time critical scenarios. This leads first of all to a novel process known as strategy regeneration, whereby the parameter values representing the users and the task at hand are refreshed periodically, in order to make effective decisions about which users to interact with, for the best decision making. We also introduce two new parameters that are modeled: each user's lack of expertise (with the task at hand) and the level of criticality of each task. These factors are then integrated into the process of reasoning about interaction to choose the best overall strategy, deciding which users to ask to resolve the current task. We illustrate the value of our framework for the application of decision making in hospital emergency room scenarios and offer validation of the approach, both through examples and from simulations. To sum up, we provide a framework for reasoning about interaction with users through user modeling for dynamic environments. In addition, we present some insights into how to improve the process of hospital emergency room decision making.

En esta tesis se presentan formalismos para modelar la dinámica de conocimiento en bases de creencias de agentes que son parte de un sistema multi-agente. En el contexto de sistemas multi-agente, un agente puede a menudo recibir información a través de informantes. Estos informantes son agentes independientes que tienen sus propios intereses y, por lo tanto, podrían no ser completamente fiables. Es natural para un agente creerle más a un informante que a otro. Es por esto que en nuestro trabajo se propondrá la organización de los informantes en un orden parcial que compara la credibilidad de los mismos. De esta manera, esta tesis se enfoca en revisión de creencias con múltiples fuentes (MSBR: Multi-Source Belief Revision), proponiendo un modelo completo de cambio basado en informantes. La dinámica del conocimiento es modelada por la teoría de cambio de creencias, la cual busca mostrar cómo quedan constituidas las creencias de un agente después de recibir cierta información externa. Existen diferentes modelos de cambio en la teoría de cambio de creencias. Uno de sus principales referentes, el modelo AGM [AGM85], distingue claramente tres operaciones de cambio: expansiones, contracciones y revisiones. La operación de expansión es la más simple de caracterizar desde el punto de vista lógico, pues consiste solamente en la adición de nuevas creencias. Sin embargo, las contracciones y revisiones no tienen esta propiedad. Las contracciones involucran la eliminación de creencias, mientras que las revisiones involucran tanto la adición como la eliminación de creencias. El orden parcial de credibilidad entre agentes no necesita permanecer estático, ya que el agente puede decidir actualizar su relación de orden parcial para reflejar una nueva percepción de la credibilidad de un informante. Es por esto que otro de los objetivos de esta tesis es el estudio y desarrollo de técnicas y formalismos para la actualización del grado de credibilidad que se le asigna a un agente por interactuar en el marco de un sistema multi-agente. Aquí también estudiamos operadores de cambio, no sobre creencias (como mencionamos antes), sino sobre orden parcial de credibilidad. Con estos operadores se puede modelar la dinámica de sistemas de confianza y reputación. Por lo tanto, la investigación también se enfocará en la caracterización y desarrollo de operadores de cambio que permitan modelar la dinámica de la confianza y reputación de agentes en un sistema. De esta manera, los agentes podrán actualizar la relación de orden con la cual se representa la reputación de sus pares. Así, estos operadores podrán ser usados para alterar dinámicamente la estructura de la credibilidad de los informantes a fin de reflejar una nueva percepción de la credibilidad de un informante o la llegada de un nuevo agente al sistema. En resumen, se pretende combinar formalismos de revisión de creencias y actualización de conocimiento con técnicas de mantenimiento de confianza y reputación de agentes en un ambiente distribuido para representar la dinámica de órdenes parciales de credibilidad. / Tesis doctoral del Departamento de Ciencias e Ingeniería de la Computación (Universidad Nacional del Sur). Grado alcanzado: Doctor en Ciencias de la Computación. Director de tesis: Alejandro J. García y Marcelo A. Falappa. La tesis, presentada en el año 2010, obtuvo el Premio "Dr. Raúl Gallard" en el 2012.

The field of mobile robotic systems has become a rich area of research and design. These systems can navigate difficult terrain using multiple actuators with conventional ambulation, by hopping, jumping, or for aerial vehicles, using flapping wings, propellers, or engines to maintain aerial flight. Unmanned Aerial Systems(UAS) have been used extensively in both military and civilian applications such as reconnaissance or search and rescue missions. For air vehicles, range and endurance is a crucial design parameter as it governs which missions can be performed by a particular vehicle. In addition, when considering the presence of external disturbances such as atmospheric winds, these missions can be even more challenging. Meta aircraft technologies is one area of research that can increase range and endurance by taking advantage of an increase in L/D. A meta aircraft is an aircraft composed of smaller individual aircraft connected together through a similar connection mechanism that can potentially transfer power, loads, or information. This dissertation examines meta aircraft flight dynamics and controls for a variety of different configurations. First, the dynamics of meta aircraft systems are explored with a focus on the changes in fundamental aircraft modes and flexible modes of the system. Specifically, when aircraft are connected, the fundamental modes change, can become overdamped or even unstable. In addition, connected aircraft exhibit complex flexible modes and mode shapes that change based on the parameters of the connection joint and the number of connected aircraft. Second, the connection dynamics are explored for meta aircraft where the vehicles are connected wing tip to wing tip using passive magnets with a particular focus on modeling the connection event between aircraft in a practical environment. It is found that a multi-stage connection control law with position and velocity feedback from GPS and connection point image feedback from a camera yields adequate connection performance in the presence of realistic sensor errors and atmospheric winds. Furthermore, atmosphericwinds with low frequency gusts at the intensity normally found in a realistic environment pose the most significant threat to the success of connection. The frequency content of the atmospheric disturbance is an important variable to determine success of connection. Finally, the geometry of magnets that create the connection force field can alter connection rates. Finally, the performance of a generic meta aircraft system are explored. Using a simplified rigid body model to approximate any meta aircraft configuration, adequate connection is achieved in the presence of realistic winds. Using this controller overall performance is studied. In winds, there is an overall decrease in outer loop performance for meta aircraft. However, inner loop performance increases for meta aircraft. In addition, the aerodynamic benefit of different configurations are investigated. Wing to wing tip connected flight provides the most benefit in terms of average increased Lift to Drag ratio while tip to tail configurations drop the Lift to Drag ratio as trailing aircraft fly in the downwash of the leading aircraft.

Our study examines some design alternatives for a carbon market by exploring the fledgling Alberta carbon market. We attempt to evaluate the performance of these designs on the bases of trade volume, cost efficiency and stability. To achieve this we construct an empirically-calibrated but simple agent-based model, certain aspects of which we selectively modify to incorporate various design options. We make comparisons among these options based on data simulated from the ensuing family of models. We find strong evidence that in general, market design features such as source-of-credits, the scale of the market, and pricing-mechanism are very important considerations that influence the performance of the market. In addition, we find support for the notion that the level of the price cap relative to the average cost of abatement in the market matters, and beyond a threshold, higher price caps are associated with lower levels of performance. / vii, 155 leaves ; 29 cm