We define a novel algorithm based on utility functions for dynamically allocating tasks to mobile robots in a multi-robot system. The algorithm attempts to maximize the performance of the mobile robot while minimizing inter-robot communications. The algorithm takes into consideration the proximity of the mobile robot to the task, the priority of the task, the capability required by the task, the capabilities of the mobile robot, and the rarity of the capability within the population of mobile robots. We evaluate the proposed algorithm in a simulation study and compare it to alternative approaches, including the contract net protocol, an approach based on the knapsack problem, and random task selection. We find that our algorithm outperforms the alternatives in most metrics measured including percent of tasks complete, distance traveled per completed task, fairness of execution, number of communications, and utility achieved.

Multi-robot systems leverage the numbers and characteristics of different robots to accomplish an overall mission. Efficient task allocation and motion planning of multi-robot teams are essential to ensure each robot's actions contribute to the overall mission while avoiding conflict with each other. The original contribution of this thesis is an optimized, efficient, and multi-factor task allocation algorithm to comprise the main component of a task coordination framework (TCF), with motion planning as a secondary component. This algorithm determines which robot performs which tasks and in what order. It presents a novel solution to the multiple robot task allocation problem (MRTA) as an extension of the multiple travelling salesmen (MTSP) problem. This extension to the MTSP considers operational factors representing physical limitations, the suitability of each robot, and inter-task dependencies. The task allocation algorithm calculates an optimized distribution of tasks such that a global objective function is minimized to simultaneously reduce total cost and ensure an even distribution of tasks among the agents. Once an optimized distribution of tasks is calculated, the motion planning component calculates collision-free velocities to drive the robots to their goal poses to facilitate task execution in a shared environment. The proposed TCF was implemented on teams of unmanned air vehicles (UAVs) and unmanned ground vehicles (UGVs). Test cases considered scenarios where the UAVs executed aerial observation tasks while UGVs executed simulated patrol and delivery tasks. The solutions were tested using real-life robots as a proof of concept and to validate simulations. The robots' kinematic and computer vision models were combined with the task coordination framework to facilitate the implementation. Large-scale simulations involving greater numbers of robots operating in a larger area were also conducted to demonstrate the task coordination framework's versatility and efficacy.

The evolution of cloud computing has finally started to affect robotics. Indeed, there have been several real-time cloud applications making their way into robotics as of late. Inherent benefits of cloud robotics include providing virtually infinite computational power and enabling collaboration of a multitude of connected devices. However, its drawbacks include higher latency and overall higher energy consumption. Moreover, local devices in proximity incur higher latency when communicating among themselves via the cloud. At the same time, the cloud is a single point of failure in the network. Fog Computing is an extension of the cloud computing paradigm providing data, compute, storage and application services to end-users on a so-called edge layer. Distinguishing characteristics are its support for mobility and dense geographical distribution. We propose to study the implications of applying fog computing concepts in robotics by developing a middle-ware solution for Robotic Fog Computing Cluster solution for enabling adaptive distributed computation in heterogeneous multi-robot systems interacting with the Internet of Things (IoT). The developed middle-ware has a modular plug-in architecture based on micro-services and facilitates communication of IOT devices with the multi-robot systems. In addition, the developed middle-ware solutions support different load balancing or task allocation algorithms. In particular, we establish that we can enhance the performance of distributed system by decreasing overall system latency by using already established multi-criteria decision-making algorithms like TOPSIS and TODIM with naive Q-learning and with Neural Network based Q-learning. / Master of Science

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.

The applications for Unmanned Aerial Vehicles are numerous and cover a range of areas from military applications, scientific projects to commercial activities, but many of these applications require substantial human involvement. This work focuses on the problems and limitations in cooperative Unmanned Aircraft Systems to provide increasing realism for cooperative algorithms. The Consensus Based Bundle Algorithm is extended to remove single agent limits on the task allocation and consensus algorithm. Without this limitation the Consensus Based Grouping Algorithm is proposed that allows the allocation and consensus of multiple agents onto a single task. Solving these problems further increases the usability of cooperative Unmanned Aerial Vehicles groups and reduces the need for human involvement. Additional requirements are taken into consideration including equipment requirements of tasks and creating a specific order for task completion. The Consensus Based Grouping Algorithm provides a conflict free feasible solution to the multi-agent task assignment problem that provides a reasonable assignment without the limitations of previous algorithms. Further to this the new algorithm reduces the amount of communication required for consensus and provides a robust and dynamic data structure for a realistic application. Finally this thesis provides a biologically inspired improvement to the Consensus Based Grouping Algorithm that improves the algorithms performance and solves some of the difficulties it encountered with larger cooperative requirements.

O objetivo deste trabalho é propor técnicas de alocação dinâmica de tarefas periódicas em MPSoCs homogêneos, com processadores interligados por uma rede emchip do tipo malha, visando redução do consumo de energia do sistema. O foco principal é a definição de uma heurística de alocação, não se considerando protocolos de escalonamento distribuído, uma vez que este ainda é um primeiro estudo para o desenvolvimento de um alocador dinâmico. Na arquitetura alvo utilizada, cada nodo do sistema é dado como autônomo, possuindo seu próprio escalonador EDF. Além disso, são aplicadas técnicas de voltage scaling e power managmenent para redução do consumo de energia durante o escalonamento. Durante a pesquisa do estado da arte, não foram encontradas técnicas de alocação dinâmica em NoCs com restrições temporais e minimização do consumo de energia. Por isso, esse trabalho se concentra em avaliar técnicas de alocação convencionais, como bin-packing e técnicas baseadas em teoria de grafos, no contexto de sistemas embarcados. Dessa forma, o modelo de estimativas do consumo de energia de alocações é baseado no escalonamento de grafos de tarefas, e foi utilizado para implementar a ferramenta Serpens com este propósito. Os grafos de tarefas utilizados nos experimentos são tirados do benchmark E3S – Embedded System Synthesis Benchmark Suite, composto por um conjunto de grafos de tarefas gerados aleatoriamente com a ferramenta TGFF – Task Graph for Free, a partir de dados de aplicações comuns em sistemas embarcados obtidos no EEMBC – Embedded Microprocessor Benchmark Consortium. Entre as heurísticas de bin-packing, Best-Fit, First-Fit e Next-Fit geram alocações com concentração de carga, enquanto a heurística Worst-Fit faz balanceamento de carga. O balanceamento de carga favorece a aplicação de voltage scaling enquanto a concentração favorece o power management. Como o bin-packing não contempla comunicação e dependência entre tarefas em seu modelo, o mesmo foi reformulado para atender esta necessidade. Nos experimentos, a alocação inicial com bin-packing original apresentou perdas de deadlines de até 84 % para a heurística Worst-Fit, passando para perdas em torno de 16% na alocação final, praticamente com o mesmo consumo de energia, após a reformulação do modelo. / The goal of this work is to offer dynamic allocation techniques of periodic tasks in mesh networks-on-chip, aiming to reduce the system power consumption. The main focus is the definition of an allocation heuristic, which does not consider distributed scheduling protocols, since this is the beginning of a study for the development of a dynamic partitioning tool. In the target architecture, each system node is self-contained, that is, the nodes contain their own EDF scheduler. Besides, voltage-scaling and power management techniques are applied for reducing power consumption during the scheduling. To the best of our knowledge, this is the first research effort considering both temporal constraints and power consumption minimization on the dynamic allocation of tasks in a mesh NoC. This way, our concentrates in the evaluation of dynamic allocation techniques, which are generally used in distributed systems, in the embedded systems context, as bin-packing and graph theory based techniques. Therefore, the estimation model for power consumption is based on task graph scheduling, and it was used for implementing the Serpens tool with this purpose. The task graphs used in the experiments were obtained from the E3S benchmark (Embedded System Synthesis Benchmark Suite), which is composed by a set of task graphs randomly generated with the TGFF tool (Task Graph for Free), from common application data obtained from the EEMBC (Embedded Microprocessor Benchmark Consortium). Among the bin-packing heuristics, Best-Fit, First-Fit, and Next-Fit generate allocations with load concentration, while the Worst-Fit heuristics works with load balancing. Load balancing favors the application of voltage scaling, while load concentration favors the utilization of power management. Since the bin-packing model does not consider inter-task communication and dependency, it has been modified to fulfill this need. In the experiments, the initial allocation using the original bin-packing model presented deadline losses of up to 84% for the Worst-Fit heuristic, changing for losses around 16% in the final allocation, after modification of the model, maintaining almost the same power consumption.

Teams of mobile robots have numerous applications, such as space exploration, underground mining, warehousing, and building security. Multi-robot teams can provide a number of practical benefits in such applications, including simultaneous presence in multiple locations, improved system performance, and greater robustness and redundancy compared to individual robots. This thesis addresses three aspects of coordination and navigation for teams of mobile robots: localization, the estimation of the position of each robot in the environment; motion planning, the process of finding collision-free trajectories through the environment; and task allocation, the selection of appropriate goals to be assigned to each robot. Each of these topics are investigated in the context of many robots working in a common environment. A particle-filter based system for cooperative global localization is presented. The system combines the sensor data from three robots, including measurements of the distances between robots, to cooperatively estimate the global position of each robot in the environment. The method is developed for a single triad of robots, then extended to larger groups of robots. The algorithm is demonstrated in a simulation of robots equipped with only simple range sensors, and is shown to successfully achieve global localization of robots that are unable to localize using only their own local sensor data. Motion planning is investigated for large teams of robots operating in tunnel and corridor environments, where coordinated planning is often required to avoid collision or deadlock conditions. A complete and scalable motion planning algorithm is presented and evaluated in simulation with up to 150 robots. In contrast to popular decoupled approaches to motion planning (which cannot guarantee a solution), this algorithm uses a multi-phase approach to create and maintain obstacle-free paths through a graph representation of the environment. The resulting plan is a set of collision-free trajectories, guaranteeing that every robot will reach its goal. The problem of task allocation is considered in the same type of tunnel and corridor environments, where tasks are defined as locations in the environment that must be visited by one of the robots in the team. To find efficient solutions to the task allocation problem, an optimization approach is used to generate potential task assignments, and select the best solution. The multi-phase motion planner is applied within this system as an efficient method of evaluating potential task assignments for many robots in a large environment. The algorithm is evaluated in simulations with up to 20 robots in a map of large underground mine. A real-world implementation of 3 physical robots was used to demonstrate the implementation of the multi-phase motion planning and task allocation systems. A centralized motion planning and task allocation system was developed, incorporating localization and time-dependent trajectory tracking on the robot processors, enabling cooperative navigation in a shared hallway environment.

Teams of mobile robots have numerous applications, such as space exploration, underground mining, warehousing, and building security. Multi-robot teams can provide a number of practical benefits in such applications, including simultaneous presence in multiple locations, improved system performance, and greater robustness and redundancy compared to individual robots. This thesis addresses three aspects of coordination and navigation for teams of mobile robots: localization, the estimation of the position of each robot in the environment; motion planning, the process of finding collision-free trajectories through the environment; and task allocation, the selection of appropriate goals to be assigned to each robot. Each of these topics are investigated in the context of many robots working in a common environment. A particle-filter based system for cooperative global localization is presented. The system combines the sensor data from three robots, including measurements of the distances between robots, to cooperatively estimate the global position of each robot in the environment. The method is developed for a single triad of robots, then extended to larger groups of robots. The algorithm is demonstrated in a simulation of robots equipped with only simple range sensors, and is shown to successfully achieve global localization of robots that are unable to localize using only their own local sensor data. Motion planning is investigated for large teams of robots operating in tunnel and corridor environments, where coordinated planning is often required to avoid collision or deadlock conditions. A complete and scalable motion planning algorithm is presented and evaluated in simulation with up to 150 robots. In contrast to popular decoupled approaches to motion planning (which cannot guarantee a solution), this algorithm uses a multi-phase approach to create and maintain obstacle-free paths through a graph representation of the environment. The resulting plan is a set of collision-free trajectories, guaranteeing that every robot will reach its goal. The problem of task allocation is considered in the same type of tunnel and corridor environments, where tasks are defined as locations in the environment that must be visited by one of the robots in the team. To find efficient solutions to the task allocation problem, an optimization approach is used to generate potential task assignments, and select the best solution. The multi-phase motion planner is applied within this system as an efficient method of evaluating potential task assignments for many robots in a large environment. The algorithm is evaluated in simulations with up to 20 robots in a map of large underground mine. A real-world implementation of 3 physical robots was used to demonstrate the implementation of the multi-phase motion planning and task allocation systems. A centralized motion planning and task allocation system was developed, incorporating localization and time-dependent trajectory tracking on the robot processors, enabling cooperative navigation in a shared hallway environment.

The active surveillance of public and private sites is increasingly becoming a very important and critical issue. It is therefore, imperative to develop mobile surveillance systems to protect these sites. Modern surveillance systems encompass spatially distributed mobile and static sensors in order to provide effective monitoring of persistent and transient objects and events in a given Area Of Interest (AOI). The realization of the potential of mobile surveillance requires the solution of different challenging problems such as task allocation, mobile sensor deployment, multisensor management, cooperative object detection and tracking, decentralized data fusion, and interoperability and accessibility of system nodes. This thesis proposes a market-based framework that can be used to handle different problems of mobile surveillance systems. Task allocation and cooperative target-tracking are studied using the proposed framework as two challenging problems of mobile surveillance systems. These challenges are addressed individually and collectively.

The active surveillance of public and private sites is increasingly becoming a very important and critical issue. It is therefore, imperative to develop mobile surveillance systems to protect these sites. Modern surveillance systems encompass spatially distributed mobile and static sensors in order to provide effective monitoring of persistent and transient objects and events in a given Area Of Interest (AOI). The realization of the potential of mobile surveillance requires the solution of different challenging problems such as task allocation, mobile sensor deployment, multisensor management, cooperative object detection and tracking, decentralized data fusion, and interoperability and accessibility of system nodes. This thesis proposes a market-based framework that can be used to handle different problems of mobile surveillance systems. Task allocation and cooperative target-tracking are studied using the proposed framework as two challenging problems of mobile surveillance systems. These challenges are addressed individually and collectively.