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.

Doctor of Philosophy / Department of Computing and Information Sciences / Scott A. DeLoach / The Organization-Based Multi-Agent Systems (OMAS) paradigm is an approach to address the challenges posed by complex systems. The complexity of these systems, the changing environment where the systems are deployed, and satisfying higher user expectations are some of current requirements when designing OMAS. For the agents in an OMAS to pursue the achievement of a common goal or task, a certain level of coordination and collaboration occurs among them. An objective in this coordination is to make the decision of who does what. Several solutions have been proposed to answer this task allocation question. The majority of the solutions proposed fall in the categories of marked-based approaches, reactive systems, or game theory approaches. A common fact among these solutions is the system information sharing among agents, which is used only to keep the participant agent informed about other agents activities and mission status. To further exploit and take advantage of this system information shared among agents, a framework is proposed to use this information to answer the question who does what, and reduce the communication among agents. DTAACS-OK is a distributed knowledge-based framework that addresses the Single Agent Task Allocation Problem (SAT-AP) and the Multiple Agent Task Allocation Problem (MAT-AP) in cooperative OMAS. The allocation of tasks is based on an identical organization knowledge posses by all agents in the organization. DTAACS-OK di ers with current solutions in that (a) it is not a marked-based approach where task are auctioned among agents, or (b) it is not based on agents behaviour, where the action or lack of action of an agent cause the reaction of other agents in the organization.