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.

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.

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