Academic literature on the topic 'Multi-Task agent'

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.

La coordinació i assignació de tasques en entorns distribuïts ha estat un punt important de la recerca en els últims anys i aquests temes són el cor dels sistemes multi-agent. Els agents en aquests sistemes necessiten cooperar i considerar els altres agents en les seves accions i decisions. A més a més, els agents han de coordinar-se ells mateixos per complir tasques complexes que necessiten més d'un agent per ser complerta. Aquestes tasques poden ser tan complexes que els agents poden no saber la ubicació de les tasques o el temps que resta abans de que les tasques quedin obsoletes. Els agents poden necessitar utilitzar la comunicació amb l'objectiu de conèixer la tasca en l'entorn, en cas contrari, poden perdre molt de temps per trobar la tasca dins de l'escenari. De forma similar, el procés de presa de decisions distribuït pot ser encara més complexa si l'entorn és dinàmic, amb incertesa i en temps real. En aquesta dissertació, considerem entorns amb sistemes multi-agent amb restriccions i cooperatius (dinàmics, amb incertesa i en temps real). En aquest sentit es proposen dues aproximacions que permeten la coordinació dels agents. La primera és un mecanisme semi-centralitzat basat en tècniques de subhastes combinatòries i la idea principal es minimitzar el cost de les tasques assignades des de l'agent central cap als equips d'agents. Aquest algoritme té en compte les preferències dels agents sobre les tasques. Aquestes preferències estan incloses en el bid enviat per l'agent. La segona és un aproximació d'scheduling totalment descentralitzat. Això permet als agents assignar les seves tasques tenint en compte les preferències temporals sobre les tasques dels agents. En aquest cas, el rendiment del sistema no només depèn de la maximització o del criteri d'optimització, sinó que també depèn de la capacitat dels agents per adaptar les seves assignacions eficientment. Addicionalment, en un entorn dinàmic, els errors d'execució poden succeir a qualsevol pla degut a la incertesa i error de accions individuals. A més, una part indispensable d'un sistema de planificació és la capacitat de re-planificar. Aquesta dissertació també proveeix una aproximació amb re-planificació amb l'objectiu de permetre als agent re-coordinar els seus plans quan els problemes en l'entorn no permeti la execució del pla. Totes aquestes aproximacions s'han portat a terme per permetre als agents assignar i coordinar de forma eficient totes les tasques complexes en un entorn multi-agent cooperatiu, dinàmic i amb incertesa. Totes aquestes aproximacions han demostrat la seva eficiència en experiments duts a terme en l'entorn de simulació RoboCup Rescue.<br>Distributed task allocation and coordination have been the focus of recent research in last years and these topics are the heart of multi-agent systems. Agents in these systems need to cooperate and consider the other agents in their actions and decisions. Moreover, agents may have to coordinate themselves to accomplish complex tasks that need more than one agent to be accomplished. These tasks may be so complicated that the agents may not know the location of them or the time they have before the tasks become obsolete. Agents may need to use communication in order to know the tasks in the environment, otherwise, it may take a long time to find the tasks into the scenario. Similarly, the distributed decisionmaking process may be even more complex if the environment is dynamic, uncertain and real-time. In this dissertation, we consider constrained cooperative multi-agent environments (dynamic, uncertain and real-time). In this regard, we propose two approaches that enable the agents to coordinate themselves. The first one is a semi-centralized mechanism based on combinatorial auction techniques and the main idea is minimizing the cost of assigned tasks from the central agent to the agent teams. This algorithm takes into account the tasks' preferences of the agents. These preferences are included into the bid sent by the agent. The second one is a completely decentralized scheduling approach. It permits agents schedule their tasks taking into account temporal tasks' preferences of the agents. In this case, the system's performance depends not only on the maximization or the optimization criterion, but also on the agents' capacity to adapt their schedule efficiently. Furthermore, in a dynamic environment, execution errors may happen to any plan due to uncertainty and failure of individual actions. Therefore, an indispensable part of a planning system is the capability of replanning. This dissertation is also providing a replanning approach in order to allow agents recoordinate his plans when the environmental problems avoid fulfil them. All these approaches have been carried out to enable the agents to efficiently allocate and coordinate all their complex tasks in a cooperative, dynamic and uncertain multi-agent scenario. All these approaches have demonstrated their effectiveness in experiments performed in the RoboCup Rescue simulation environment.

In this thesis we address the problem of human robot interaction in industrial environments from collaboration perspective. This thesis, in particular, focuses on introducing novel frameworks for coordination of heterogeneous teams made of humans and robots that collaboratively aim to reach to a common goal. In the last decade, robots has received enormous attentions for being employed in both industrial environments and workplaces. Thin is mainly because of a number of reasons: (I) the shift of mass production industries toward autonomous industry units, (II) huge amount of financial and scientific investments on robotics, and (III) substitution of humans with robots to accomplish hazardous and stressful tasks. However Due to the limited cognitive knowledge and reasoning of the robots in accomplishing complex operations, they still are not able to operate in a fully autonomous fashion and independently from their human counterparts. Therefore presence of human operators, as a complementary counterparts, in workplaces becomes fundamental for robots to become utterly safe, reliable and operative. The goal of this thesis is to design and implement a framework whereby humans and/or robots can together play a complementary role, while applying their individual skills to accomplish a task. Human-robot collaboration (HRC) is defined as the purposeful interaction among humans and robots in a shared space, and it is aimed at a common goal. The design of such framework for HRC problems, requires to satisfy many requirements from which flexibility, adaptability and safety, are the primary characteristics of such framework. In this thesis we mainly focus on multi-agent robot systems task allocation and planning. We consider two main aspects in defining our objectives: on one hand we investigate on HRC, and implement alternative frameworks to model and study collaborations in industrial scenarios considering various roles of humans in coordination and collaboration with robots. On the other hand, the presence of humans is neglected and it is assumed that robots are able to fully precept the environment independently from human cognitive support, as this can be the case of future where Artificial intelligence might substitute the skills of humans. To model a HRC scenario, a smart framework is required to start, coordinate and terminate a collaborative process. This framework, in particular has to be aware of agents and their types, determine their responsibilities and roles, be aware of their physical structure, define the logical relationship among the agent and handle the collaboration process fluently. In this thesis, to address the framework described above, we propose different frameworks and evaluate their effectiveness in solving HRC problems. To formulate task planning and allocation problem , we introduce and implement three variants of AND/OR graphs, namely, c-layer AND/OR graphs, Branched AND/OR graphs, and Iteratively deepened AND/OR graphs. The first two variants aim at addressing the problem of task allocation among humans and collaborative robots in object defect inspection (ODI) scenarios in HRC context. Instead, the third variant targets Task and motion planning (TAMP) problems for heterogeneous robots. TAMP problems, compared to HRC problem, is not only responsible for allocating task among agents at higher-level, but also at lower level, it plans motions for agents and ultimately, interconnects higher levels of task planning to lower levels of motion planning and control to achieve a complete planning framework. To validate the applicability and scalability of our proposed frameworks, we design and implement various real-world and simulation experiments and we also evaluate their effectiveness in terms of achieving desired objectives, and quantitatively with other available methods in the literature.

This research involves a multi-agent based simulation modeling a large swarm of adversarial UAVs attacking a surface target and groups of friendly UAVs responding to thwart the attack. Defense systems need to cooperatively negotiate which enemy systems to engage to maximize the number of aggressor systems destroyed. Using optimal centralized task assignment methods as a baseline, various distributed methods are examined for efficiency and effectiveness. Our findings indicate that the optimality of distributed methods does approach that of centralized methods, though further study is warranted in future simulations with additional constraints, and in field experimentation with physical UAVs. We further find that the number of defender agents, the effectiveness of their weapon systems, and their speeds contribute significantly to the defender swarm’s effectiveness.

Grid computing and cloud systems are distributed systems which provide substantial widely-accessible services to resources. Quality of service is affected by the issues around resource allocation, sharing, task execution and node failure. The focus of this research is on task execution in distributed environments and the effects of node failure on service provision. Most methods in the literature which provide fault tolerance, use reactive techniques; these provide solutions to failure only after its occurrence. In contrast, this research argues that using multi-agent systems with self-organising capabilities can provide a proactive methodology which can improve task execution in open, dynamic and distributed environments. We have modelled a system of autonomous agents with heterogeneous resources and proposed a new delegation protocol for executing tasks within their time constraints. This helps avoid the loss of tasks and to improve efficiency. However, this method on its own is not sufficient in terms of task execution throughput, especially in the presence of agent failure. Hence, we propose, a self-organisation technique. This is represented in this research by two different mechanisms for creating organisations of agents with a certain structure; we suggest, in addition, the adoption of task delegation within the organisations. Adding an organisation structure with agent roles to the network enables smoother performance, increases task execution throughput and copes with agent failures. In addition, we study the failure problem as it manifests within the organisations and we suggest an improvement to the organisation structure which involves the use of another protocol and adding a new role. An exploratory study of dynamic, heterogeneous organisations of agents has also been conducted to understand the formation of organisations in a dynamic environment where agents may fail and new agents may join organisations. These conditions mean that new organisations may evolve and existing organisations may change.

L'allocation des tâches à plusieurs agents autonomes devant accomplir des tâches complexes a été l'un des domaines de recherche récents sur les systèmes multi-agents. Dans de nombreuses applications, les agents sont coopératifs et doivent effectuer des tâches qui nécessitent chacune une combinaison de différentes capacités dont peut se doter un sous-ensemble d'agents. Dans ce cas, nous pouvons utiliser la formation de coalitions comme paradigme pour affecter des coalitions d'agents à des tâches. Les solutions à ce problème d'allocation de tâches, pour les systèmes robotiques en particulier, trouvent plusieurs applications dans le monde réel et prennent de plus en plus de l'importance dans les domaines de la défense, de l'espace, de la gestion des catastrophes, de l'exploration sous-marine, de la logistique, de la fabrication de produits et de l'assistance dans les services de santé. De multiples mécanismes de formation de coalitions et d'allocation de tâches ont été introduits dans l'état de l'art, tenant rarement compte des tâches interdépendantes. Cependant, il est récurrent de trouver des tâches dont la qualité ne peut être évaluée sans considérer les autres tâches dans des applications réelles. Ces tâches sont appelées interdépendantes par opposition aux tâches indépendantes qui, elles, peuvent être évaluées individuellement, ce qui entraîne une évaluation globale de l'allocation des tâches qui additionne simplement toutes les évaluations des tâches. La recherche dans le passé a conduit à de nombreuses méthodes d'allocation de tâches qui traitent le cas des tâches indépendantes sous différents angles et sous différents paradigmes. D'autres travaux résolvent le cas des tâches interdépendantes, mais ils le font soit de manière centralisée avec une complexité très élevée, soit uniquement pour le cas des dépendances de précédence. Cependant, de nombreuses formes d'interdépendance peuvent exister entre les tâches dans les applications du monde réel. Ces applications nécessitent que les mécanismes d'allocation des tâches soient décentralisés et anytime, pouvant renvoyer une solution à tout moment quitte à l'améliorer s'il reste du temps, pour répondre à des problèmes de sensibilité au temps et de robustesse. Dans cette thèse, nous considérons des environnements multi-agents coopératifs où les tâches sont multi-agents et interdépendantes, et les méthodes d'allocation des tâches doivent être décentralisées et anytime. À cet égard, nous proposons une formalisation du problème qui considère les attributs qualitatifs et quantitatifs des agents et des tâches, et qui capture les dépendances des tâches que ça soit au niveau des exigences ou au niveau de l'évaluation des allocations. Nous introduisons une nouvelle approche avec un mécanisme de formation de coalition décentralisé anytime qui permet aux agents dotés de capacités complémentaires de former, de manière autonome et dynamique, des structures de coalitions faisables qui accomplissent une tâche globale et composite. Cette approche est basée sur la formation d'une structure de coalition faisable permettant aux agents de décider quelle coalition rejoindre et donc quelle tâche accomplir afin que toutes les tâches soient faisables. Ensuite, les structures formées sont progressivement améliorées via des remplacements d'agents pour optimiser l'évaluation globale de l'allocation, le but étant d'accomplir les tâches avec les meilleures performances possibles. Nous analysons la complexité de nos algorithmes et montrons que, bien que le problème général soit NP-complet, notre mécanisme fournit une solution dans un temps acceptable. Des scénarios d'application simulés sont utilisés pour démontrer la valeur ajoutée de notre approche<br>Task allocation among multiple autonomous agents that must accomplish complex tasks has been one of the focusing areas of recent research in multi-agent systems. In many applications, the agents are cooperative and have to perform tasks that each requires a combination of different capabilities that a subset of agents can have. In this case, we can use coalition formation as a paradigm to assign coalitions of agents to tasks. For robotic systems, in particular, solutions to this task allocation problem have several and increasingly important real-world applications in defense, space, disaster management, underwater exploration, logistics, product manufacturing, and support in healthcare facilities support. Multiple coalition formation and task allocation mechanisms were introduced in the prior art, seldom accounting for interdependent tasks. However, it is recurrent to find tasks whose quality cannot be evaluated without considering the other tasks in real-world applications. These tasks are called interdependent in contrast to independent tasks that can be individually assessed, resulting in a global evaluation of the tasks' allocation that sums all the tasks' evaluations. Research in the past has led to many task allocation algorithms that address the case of independent tasks from different angles and under different paradigms. Other works solve the case of the interdependent tasks, but they do it either centrally with very high complexity or only for the case of precedence dependencies. However, many forms of interdependence may exist between tasks in real-world applications. In addition, these applications need task allocation mechanisms to be decentralised and available at anytime to allow them to return a solution at any time and to improve it if there is time left, to respond to their time-sensitivity and robustness issues. In this dissertation, we consider cooperative multi-agent environments where tasks are multi-agent and interdependent, and task allocation methods have to be decentralized and available at anytime. In this regard, we propose a problem formalisation that considers the agents' and the tasks' qualitative and quantitative attributes and captures the tasks' dependencies on the requirements level and the allocation evaluation level. We introduce a novel approach with a token-passing anytime decentralised coalition formation mechanism. The approach enables agents with complementary capabilities to form, autonomously and dynamically, feasible coalition structures that accomplish a global, composite task. It is based on forming a feasible coalition structure that allows the agents to decide which coalition to join and thus which task to do so that all the tasks can be feasible. Then, the formed structures are incrementally improved via agent replacements to optimise the global evaluation. The purpose is to accomplish the tasks with the best possible performance. The analysis of our algorithms' complexity shows that although the general problem is NP-complete, our mechanism provides a solution within an acceptable time. Simulated application scenarios are used to demonstrate the added value of our approach

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.<br>Includes bibliographical references (p. 105-107).<br>This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.<br>This thesis examines scenarios where multiple autonomous agents collaborate in order to accomplish a global objective. In the environment that we consider, there is a network of agents, each of which offers different sets of capabilities or services that can be used to perform various tasks. In this environment, an agent formulates a problem, divides it into a precedence-constrained set of sub-problems, and determines the optimal allocation of these sub-problems/tasks to other agents so that they are completed in the shortest amount of time. The resulting schedule is constrained by the execution delay of each service, job release times and precedence relations, as well as communication delays between agents. A Mixed Integer-Linear Programming (MILP) approach is presented in the context of a multi-agent problem-solving framework that enables optimal makespans to be computed for complex classifications of scheduling problems that take many different parameters into account. While the algorithm presented takes exponential time to solve and thus is only feasible to use for limited numbers of agents and jobs, it provides a flexible alternative to existing heuristics that model only limited sets of parameters, or settle for approximations of the optimal solution. Complexity results of the algorithm are studied for various scenarios and inputs, as well as recursive applications of the algorithm for hierarchical decompositions of large problems, and optimization of multiple objective functions using Multiple Objective Linear Programming (MOLP) techniques.<br>by Mark F. Tompkins.<br>M.Eng.