A multi-agent system consists of a number of agents, which may include software agents, robots, or even humans, in some application environment. Multi-robot systems are increasingly being employed to complete jobs and missions in various fields including search and rescue, space and underwater exploration, support in healthcare facilities, surveillance and target tracking, product manufacturing, pick-up and delivery, and logistics. Multi-agent task allocation is a complex problem compounded by various constraints such as deadlines, agent capabilities, and communication delays. In high-stake real-time environments, such as rescue missions, it is difficult to predict in advance what the requirements of the mission will be, what resources will be available, and how to optimally employ such resources. Yet, a fast response and speedy execution are critical to the outcome. This thesis proposes distributed optimisation techniques to tackle the following questions: how to maximise the number of assigned tasks in time restricted environments with limited resources; how to reach consensus on an execution plan across many agents, within a reasonable time-frame; and how to maintain robustness and optimality when factors change, e.g. the number of agents changes. Three novel approaches are proposed to address each of these questions. A novel algorithm is proposed to reassign tasks and free resources that allow the completion of more tasks. The introduction of a rank-based system for conflict resolution is shown to reduce the time for the agents to reach consensus while maintaining equal number of allocations. Finally, this thesis proposes an adaptive data-driven algorithm to learn optimal strategies from experience in different scenarios, and to enable individual agents to adapt their strategy during execution. A simulated rescue scenario is used to demonstrate the performance of the proposed methods compared with existing baseline methods.

This paper reports the findings of using multi-agent based simulation model to evaluate the sawmill yard operations within a large privately owned sawmill in Sweden, Bergkvist Insjön AB in the current case. Conventional working routines within sawmill yard threaten the overall efficiency and thereby limit the profit margin of sawmill. Deploying dynamic work routines within the sawmill yard is not readily feasible in real time, so discrete event simulation model has been investigated to be able to report optimal work order depending on the situations. Preliminary investigations indicate that the results achieved by simulation model are promising. It is expected that the results achieved in the current case will support Bergkvist-Insjön AB in making optimal decisions by deploying efficient work order in sawmill yard.

Current research in multi-agent systems (MAS) has advanced to the development of open MAS, which are characterized by the heterogeneity of agents, free exit/entry and decentralized control. Conflicts of interest among agents are inevitable, and hence automated negotiation to resolve them is one of the promising solutions. This thesis studies three modifications on alternating-offer bargaining protocols for automated negotiation in open MAS. The long-term goal of this research is to design negotiation protocols which can be easily used by intelligent agents in accommodating their need in resolving their conflicts. In particular, we propose three modifications: allowing non-monotonic offers during the bargaining (non-monotonic-offers bargaining protocol), allowing strategic delay (delay-based bargaining protocol), and allowing strategic ignorance to augment argumentation when the bargaining comprises argumentation (ignorance-based argumentation-based negotiation protocol). <p>Utility theory and decision-theoretic approaches are used in the theoretical analysis part, with an aim to prove the benefit of these three modifications in negotiation among myopic agents under uncertainty. Empirical studies by means of computer simulation are conducted in analyzing the cost and benefit of these modifications. Social agents, who use common human bargaining strategies, are the subjects of the simulation. <p>In general, we assume that agents are bounded rational with various degrees of belief and trust toward their opponents. In particular in the study of the non-monotonic-offers bargaining protocol, we assume that our agents have diminishing surplus. We further assume that our agents have increasing surplus in the study of delay-based bargaining protocol. And in the study of ignorance-based argumentation-based negotiation protocol, we assume that agents may have different knowledge and use different ontologies and reasoning engines. <p>Through theoretical analysis under various settings, we show the benefit of allowing these modifications in terms of agents expected surplus. And through simulation, we show the benefit of allowing these modifications in terms of social welfare (total surplus). Several implementation issues are then discussed, and their potential solutions in terms of some additional policies are proposed. Finally, we also suggest some future work which can potentially improve the reliability of these modifications.

No description available.

Current research in multi-agent systems (MAS) has advanced to the development of open MAS, which are characterized by the heterogeneity of agents, free exit/entry and decentralized control. Conflicts of interest among agents are inevitable, and hence automated negotiation to resolve them is one of the promising solutions. This thesis studies three modifications on alternating-offer bargaining protocols for automated negotiation in open MAS. The long-term goal of this research is to design negotiation protocols which can be easily used by intelligent agents in accommodating their need in resolving their conflicts. In particular, we propose three modifications: allowing non-monotonic offers during the bargaining (non-monotonic-offers bargaining protocol), allowing strategic delay (delay-based bargaining protocol), and allowing strategic ignorance to augment argumentation when the bargaining comprises argumentation (ignorance-based argumentation-based negotiation protocol). <p>Utility theory and decision-theoretic approaches are used in the theoretical analysis part, with an aim to prove the benefit of these three modifications in negotiation among myopic agents under uncertainty. Empirical studies by means of computer simulation are conducted in analyzing the cost and benefit of these modifications. Social agents, who use common human bargaining strategies, are the subjects of the simulation. <p>In general, we assume that agents are bounded rational with various degrees of belief and trust toward their opponents. In particular in the study of the non-monotonic-offers bargaining protocol, we assume that our agents have diminishing surplus. We further assume that our agents have increasing surplus in the study of delay-based bargaining protocol. And in the study of ignorance-based argumentation-based negotiation protocol, we assume that agents may have different knowledge and use different ontologies and reasoning engines. <p>Through theoretical analysis under various settings, we show the benefit of allowing these modifications in terms of agents expected surplus. And through simulation, we show the benefit of allowing these modifications in terms of social welfare (total surplus). Several implementation issues are then discussed, and their potential solutions in terms of some additional policies are proposed. Finally, we also suggest some future work which can potentially improve the reliability of these modifications.

Reinforcement learning is a machine learning technique designed to mimic the way animals learn by receiving rewards and punishment. It is designed to train intelligent agents when very little is known about the agent’s environment, and consequently the agent’s designer is unable to hand-craft an appropriate policy. Using reinforcement learning, the agent’s designer can merely give reward to the agent when it does something right, and the algorithm will craft an appropriate policy automatically. In many situations it is desirable to use this technique to train systems of agents (for example, to train robots to play RoboCup soccer in a coordinated fashion). Unfortunately, several significant computational issues occur when using this technique to train systems of agents. This dissertation introduces a suite of techniques that overcome many of these difficulties in various common situations. First, we show how multi-agent reinforcement learning can be made more tractable by forming coalitions out of the agents, and training each coalition separately. Coalitions are formed by using information-theoretic techniques, and we find that by using a coalition-based approach, the computational complexity of reinforcement-learning can be made linear in the total system agent count. Next we look at ways to integrate domain knowledge into the reinforcement learning process, and how this can signifi-cantly improve the policy quality in multi-agent situations. Specifically, we find that integrating domain knowledge into a reinforcement learning process can overcome training data deficiencies and allow the learner to converge to acceptable solutions when lack of training data would have prevented such convergence without domain knowledge. We then show how to train policies over continuous action spaces, which can reduce problem complexity for domains that require continuous action spaces (analog controllers) by eliminating the need to finely discretize the action space. Finally, we look at ways to perform reinforcement learning on modern GPUs and show how by doing this we can tackle significantly larger problems. We find that by offloading some of the RL computation to the GPU, we can achieve almost a 4.5 speedup factor in the total training process.

This thesis details the development of a custom autopilot system designed specifically for multi-agent robotic missions. The project was motivated by the need for a flexible autopilot system architecture that could be easily adapted to a variety of future multi-vehicle experiments. The development efforts can be split into three categories: algorithm and software development, hardware development, and testing and integration. Over 12,000 lines of C++ code were written in this project, resulting in custom flight and ground control software. The flight software was designed to run on a Gumstix Overo Fire(STORM) computer on module (COM) using a Linux Angstrom operating system. The flight software was designed to support the onboard GN&C algorithms. The ground control station and its graphical user interface were developed in the Qt C++ framework. The ground control software has been proven to operate safely during multi-vehicle tests, and will be an asset in future work. Two TSH GAUI 500X quad-rotors and one Gears Educational Systems SMP rover were integrated into an autonomous swarm. Each vehicle used the Gumstix Overo COM. The C-DUS Pilot board was designed as a custom interface circuit board for the Overo COM and its expansion board, the Gumstix Pinto-TH. While the built-in WiFi capability of the Overo COM served as a communication link to a central wireless router, the C-DUS Pilot board allowed for the compact and reliable integration of sensors and actuators. The sensors used in this project were limited to accelerometers, gyroscopes, magnetometers, and GPS. All of the components underwent extensive testing. A series of ground and flight tests were conducted to safely and gradually prove system capabilities. The work presented in this thesis culminated with a successful three-vehicle autonomous demonstration comprised of two quad-rotors executing a standoff tracking trajectory around a moving rover, while simultaneously performing GPS-based collision avoidance. / text

Research on multi-agent systems performing cooperative tasks has received considerable attention in recent years. Because multiple agents perform cooperative tasks in close proximity, the coordination control of multiple agents to avoid collisions holds one of the critical keys to mission success. The potential function approach has been extensively employed for collision avoidance, but it has one inherent limitation of local minimum. This dissertation proposes a new avoidance strategy for the issue of local minimum. The primary objective of this research is to construct novel potential-function-based control schemes that drive agents from their initial to the goal configurations while avoiding collision with other agents and obstacles. The control schemes enable agents to avoid being trapped at a local minimum by forcing them to exit from the regions that may contain a local minimum. This dissertation consists of three studies, each of which has different technical assumptions. In the first study, all-to-all communication ability among agents is assumed. In addition, each agent is assumed to a priori know the location of all obstacles. In the second study, all-to-all communication ability is again assumed, but each agent is assumed to determine the location of obstacles using a sensor with a limited sensing range. In the third study, limited communication ability is assumed (i.e., each agent exchanges information only with agents within its limited communication range), and each agent is assumed to determine the location of the obstacles using its sensor with a limited sensing range. Relative to existing solutions, the new control schemes presented here have three distinct advantages. First, our avoidance strategy can provide cost-efficient solutions in applications because agents will never be trapped at a local minimum. Second, our control signals are continuous, which allows agents to change their speed in a realistic manner that is consistent with their natural motion traits. Finally, our control scheme allows for setting the upper bound of the velocity of each agent, which guarantees that the speed of agents will never exceed a maximum speed limit. / text

Distributed simulations have been widely applied as the method to study complex systems which are analytically intractable and numerically prohibitive to evaluate. However it is not a trivia task to develop distributed simulations. Besides distributed simulations may introduce difficulties for analysis due to decentralized, heterogeneous data sources. It is important to integrate these data sources seamlessly for analysis. In applications for system design, it is required to explore the alternatives of hardware components, algorithms, and simulation models. How to enable these operations conveniently is critical for the distributed system as well. All these challenges raise the need of a workbench that facilitates rapid composition, evaluation, modification and validation of components in a distributed system.This dissertation proposes a platform for these challenges, which we refer to the SPEED-CS platform. The architecture of the platform consists of multiple layers that include network layer, component management layer, components layer, and modeling layer. It is a multi-agent system (MAS), containing static agents and mobile agents. The mobile agent is referred as the Data Exchange Agent, which is able to visit sub-simulations and has the intelligence to find the useful data for output analysis. Experiments show that the MAS requires much less network bandwidth than the "centralized" system does, in which simulations report data to output analyst.The application of the SPEED-CS platform is extended to handle systems with dynamic data sources. We demonstrate that the platform can be used for parallel reality applications where simulation parameters can be updated according to real-time sensor information. Data exchange agents are involved to manage the collection, dissemination, and analysis of data from dynamic data sources including simulations and/or physical systems.The SPEED-CS platform is also implemented to integrate simulations and optimizations. The system is able to provide services to facilitate distributed computing, event services, naming services, and component management. One of the important features is that the component sets can be updated and enlarged with different models adding in. This feature enables the platform to work as a testbed to explore alternatives of system designs.Finally we conclude this dissertation with several future research topics.

This thesis is to develop a novel consensus algorithm or protocol for multi-agent systems in the event of communication link failure over the network. The structure or topology of the system is modeled by an algebraic graph theory, and defined as a discrete time-invariant system with a second-order dynamics. The communication link failure is governed by a Bernoulli process. Lyapunov-based methodologies and Linear Matrix Inequality (LMI) techniques are then applied to find an appropriate controller gain by satisfying the sufficient conditions of the error dynamics. Therefore, the controller with the calculated gain is guaranteed to drive the system to reach a consensus. Finally, simulation and experiment studies are carried out by using two Mobile Robot Pioneer 3-DXs and one Pioneer 3-AT as a team to verify the proposed work.