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.

Motivated by shortcomings in recent natural disaster responses; this paper reports on a computational approach that offers techniques for matching social demands of a disaster type with the strengths of cultural traits among rescue teams.

"All cold-blooded animals and a large number of warm-blooded ones spend an unexpectedly large proportion of their time doing nothing at all, or at any rate, nothing in particular." (Elton 1927) Many animals are remarkably "lazy", spending >50% of their waking hours "resting" . This is common across all taxa, ecologies, and life histories, including what are commonly considered to be highly industrious animals: the social insects (e.g., Aesop's Fable 'The Grasshopper and the Ant'). This dissertation broadly seeks to explain a phenomenon that has long been observed, but never adequately addressed, by asking: 'why are there 'lazy' ants?' First, I established that inactivity was a real and ecologically relevant phenomenon in the ant Temnothorax rugatulus by testing whether inactivity was a lab artifact. I then showed that inactive workers comprise a behaviorally distinct group of workers that are commonly overlooked in studies looking at colony function, though they typically represent at least half of the individuals within social insect colonies. I then tested a set of mutually non-exclusive hypotheses explaining inactivity in social insects: that (1) inactivity is a form of social "cheating" in which egg-laying workers selfishly invest in their own reproduction rather than contribute to colony fitness, (2) inactive workers comprise a pool of reserve workers used to mitigate the effects of fluctuations in colony workload, (3) inactivity is the result of physiological constraints on worker age such that young and old workers may less active due to inexperience/physical vulnerability, and physiological deterioration respectively, (4) inactive workers are performing an as-yet unidentified function, such as playing a role in communication and acting as food stores, or repletes, and that (5) inactive workers represent the 'slow' end of intra-nest variation in worker 'pace-of-life'. Inactivity is linked to worker age, reproduction, and a potential function as food stores for the colony. These hypotheses are not mutually exclusive, and in fact, likely form a 'syndrome' of behaviors common to inactive social insect workers. Their simultaneous contribution to worker inactivity may explain the difficulty in finding a simple answer to this deceptively simple question.

This dissertation addresses improvements to a consensus based task allocation algorithms for improving the Quality of Service in multi-task and multi-agent environments. Research in the past has led to many centralized task allocation algorithms where a central computation unit is calculating the global optimum task allocation solution. The centralized algorithms are plagued by creating a single point of failure and the bandwidth needed for creating consistent and accurate situational awareness off all agents. This work will extend upon a widely researched decentralized task assignment algorithm based on the consensus principle. Although many extensions have led to improvements of the original algorithm, there is still much opportunity for improvement in providing sufficient and reliable task assignments in real-world dynamic conditions and changing environments. This research addresses practical changes made to the consensus based task allocation algorithms for improving the Quality of Service in multi-task and multi-agent environments.

Large-scale scenarios such as search-and-rescue operations, agriculture, warehouse, surveillance, and construction consist of multiple tasks to be performed at the same time. These tasks have non-trivial spatial distributions. Robot swarms are envisioned to be efficient, robust, and flexible for such applications. We model this system such that each robot can service a single task at a time; each task requires a specific number of robots, which we refer to as 'quota'; task allocation is instantaneous; and tasks do not have inter- dependencies. This work focuses on distributing robots to spatially distributed tasks of known quotas in an efficient manner. Centralized solutions which guarantee optimality in terms of distance travelled by the swarm exist. Although potentially scalable, they require non-trivial coordination; could be computationally expensive; and may have poor response time when the number of robots, tasks and task quotas increase. For a swarm to efficiently complete tasks with a short response time, a decentralized approach provides better parallelism and scalability than a centralized one. In this work, we study the performance of a weight-based approach which is enhanced to include spatial aspects. In our approach, the robots share a common table that reports the task locations and quotas. Each robot, according to its relative position with respect to task locations, modifies weights for each task and randomly chooses a task to serve. Weights increase for tasks that are closer and have high quota as opposed to tasks which are far away and have low quota. Tasks with higher weights have a higher probability of being selected. This results in each robot having its own set of weights for all tasks. We introduce a distance- bias parameter, which determines how sensitive the system is to relative robot-task locations over task quotas. We focus on evaluating the distance covered by the swarm, number of inter- task switches, and time required to completely allocate all tasks and study the performance of our approach in several sets of simulated experiments.

Area exploration and information gathering are one of the fundamental problems in mobile robotics. Much of the current research in swarm robotics is aimed at developing practical solutions to this problem. Exploring large environments poses three main challenges. Firstly, there is the problem of limited connectivity among the robots. Secondly, each of the robots has a limited battery life which requires the robots to be recharged each time they are running out of charge. Lastly, the robots have limited memory to store data. In this work, we mainly focus on the memory and energy constraints of the robot swarm. The memory constraint forces the robots to travel to a centralized data collection center called sink, to deposit data each time their memory is full. The energy constraint forces the robots to travel to the charging station called dock to recharge when their battery level is low. However, this navigation plan is inefficient in terms of energy and time. There is additional energy dissipation in depositing data at the centralized sink. Moreover, ample amount of time is spent in traveling from one end of the arena to the sink owing to the memory constraint. The goal is that the robots perform data gathering in the least time possible with the optimal use of energy. Both the energy and time spent while depositing data at the sink act as an additional overhead cost to this goal. In this work, we propose to study an algorithm to tackle this scenario in a decentralized manner. We implement a dynamic task allocation algorithm which accomplishes the goal of exploration with data gathering by assigning roles to robots based on their memory buffer and energy levels. The algorithm assigns two sets of roles, to the entire group of robots, namely: Role A is the data gatherer, a robot which does the task of workspace exploration and data gathering, and Role B is data relayer, a robot which does the task of data transportation from data gatherers to the sink. By this division of labor, the robots dynamically decide which role to choose given the contradicting goals of maximizing data gathering and minimizing energy loss. The choice of a robot to perform the task of data gathering or data relaying is the key problem tackled in this work. We study the performance of the algorithm in terms of task distribution, time spent by the robots on each task and data throughput. We analyze the behavior of the robot swarm by varying the energy constraints, timeout parameter as well as strategies for relayer choice. We also test whether the algorithm is scalable.

Two on-line task re-allocation methodologies capable of re-allocating agents to tasks on-line for minimum task completion time in dynamic environments are presented herein. The first methodology, the Dynamic Nearest Neighbour (DNN) Policy, is proposed for the operation of a fleet of vehicles in a city-like application of the dial-a-ride problem. The second methodology, the Dynamic Re-Pairing Methodology (DRPM) is proposed for the interception of a group of mobile targets by a dynamic team of robotic pursuers, where the targets are assumed to be highly maneuverable with a priori unknown, but real-time trackable, motion trajectories. Extensive simulations and experiments have verified the DNN policy to be tangibly superior to the first-come-first-served and nearest neighbour policies in minimizing customer mean system time, and the DRPM to be tangibly efficient in the optimal dynamic re-pairing of multiple mobile pursuers to multiple mobile targets for minimum total interception time.

Two on-line task re-allocation methodologies capable of re-allocating agents to tasks on-line for minimum task completion time in dynamic environments are presented herein. The first methodology, the Dynamic Nearest Neighbour (DNN) Policy, is proposed for the operation of a fleet of vehicles in a city-like application of the dial-a-ride problem. The second methodology, the Dynamic Re-Pairing Methodology (DRPM) is proposed for the interception of a group of mobile targets by a dynamic team of robotic pursuers, where the targets are assumed to be highly maneuverable with a priori unknown, but real-time trackable, motion trajectories. Extensive simulations and experiments have verified the DNN policy to be tangibly superior to the first-come-first-served and nearest neighbour policies in minimizing customer mean system time, and the DRPM to be tangibly efficient in the optimal dynamic re-pairing of multiple mobile pursuers to multiple mobile targets for minimum total interception time.

Many domains, such as emergency assistance, agriculture, construction, and planetary exploration, will increasingly require effective coordination of teams of robots and humans to accomplish a collection of spatially distributed heterogeneous tasks. Such coordination problems range from those that require loosely coordinated teams in which agents independently perform their assigned tasks, to those that require tightly coordinated teams where all actions of the team members need to be tightly synchronized. The scenarios of interest to this thesis lie between these two extremes, where some tasks are independent and others are related by constraints such as precedence, simultaneity, or proximity. These constraints may be a result of different factors including the complementary capabilities of different types of agents which require them to cooperate to achieve certain goals. The manner in which the constraints are satisfied influences the overall utility of the team. This thesis explores the problem of task allocation, scheduling, and routing for heterogeneous teams with such cross-schedule dependencies. We first describe and position this coordination problem in the larger space of multi-robot task allocation problems and propose an enhanced taxonomy for this space of problems. Recognizing that solution quality is important in many domains, we then present a mathematical programming approach to computing a bounded-optimal solution to the task allocation, scheduling and routing problem with cross-schedule dependencies. Specifically, we present a branch-and-price algorithm operating on a set-partitioning formulation of the problem, with side constraints. This bounded optimal “anytime” algorithm computes progressively better solutions and bounds, until it eventually terminates with the optimal solution. By examining the behavior of this algorithm, we gain insight into the impact on problem difficulty of various problem features, particularly different types of cross-schedule dependencies. Lastly, the thesis presents a flexible execution strategy for the resulting team plans with cross-schedule dependencies, and results demonstrating the approach on a team of indoor robots

No description available.