Tesis sobre el tema "Multi-Task agent"

Coordination of multiple agents for dynamic task allocation is an important and challenging problem, which involves deciding how to assign a set of agents to a set of tasks, both of which may change over time (i.e., it is a dynamic environment). Moreover, it is often necessary for heterogeneous agents to form teams to complete certain tasks in the environment. In these teams, agents can often complete tasks more efficiently or accurately, as a result of their synergistic abilities. In this thesis we view these dynamic task allocation problems as a multi-agent system and investigate coordination techniques for such systems. In more detail, we focus specially on the distributed constraint optimisation problem (DCOP) formalism as our coordination technique. Now, a DCOP consists of agents, variables and functions agents must work together to find the optimal configuration of variable values. Given its ubiquity, a number of decentralised algorithms for solving such problems exist, including DPOP, ADOPT, and the GDL family of algorithms. In this thesis, we examine the anatomy of the above-mentioned DCOP algorithms and highlight their shortcomings with regard to their application to dynamic task allocation scenarios. We then explain why the max-sum algorithm (a member of the GDL family) is the most appropriate for our setting, and define specific requirements for performing multi-agent coordination in a dynamic task allocation scenario: namely, scalability, robustness, efficiency in communication, adaptiveness, solution quality, and boundedness. In particular, we present three dynamic task allocation algorithms: fast-max-sum, branchand-bound fast-max-sum and bounded fast-max-sum, which build on the basic max-sum algorithm. The former introduces storage and decision rules at each agent to reduce overheads incurred by re-running the algorithm every time the environment changes. However, the overall computational complexity of fast-max-sum is exponential in the number of agents that could complete a task in the environment. Hence, in branchand- bound fast-max-sum, we give fast-max-sum significant new capabilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents, at the expense of additional storage. Despite this, fast-max-sum is only proven to converge to an optimal solution on instances where the underlying graph contains no cycles. In contrast, bounded fast-max-sum builds on techniques found in bounded max-sum, another extension of max-sum, to find bounded approximate solutions on arbitrary graphs. Given such a graph, bounded fast-max-sum will run our iGHS algorithm, which computes a maximum spanning tree on subsections of a graph, in order to reduce overheads when there is a change in the environment. Bounded fast-max-sum will then run fast-max-sum on this maximum spanning tree in order to find a solution. We have found that fast-max-sum reduces the size of messages communicated and the amount of computation by up to 99% compared with the original max-sum. We also found that, even in large environments, branch-and-bound fast-max-sum finds a solution using 99% less computation and up to 58% fewer messages than fast-max-sum. Finally, we found bounded fast-max-sum reduces the communication and computation cost of bounded max-sum by up to 99%, while obtaining 60{88% of the optimal utility, at the expense of needing additional communication than using fast-max-sum alone. Thus, fast-max-sum or branch-and-bound fast-max-sum should be used where communication is expensive and provable solution quality is not necessary, and bounded fast-max-sum where communication is less expensive, and provable solution quality is required. Now, in order to achieve such improvements over max-sum, fast-max-sum exploits a particularly expressive model of the environment by modelling tasks in the environment as function nodes in a factor graph, which need to have some communication and computation performed for them. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as RjjCmax). In this thesis, we draw parallels between unrelated parallel machine scheduling and the computation distribution problem, and, in so doing, we present the spanning tree decentralised task distribution algorithm (ST-DTDA), the first decentralised solution to RjjCmax. Empirical evaluation of a number of heuristics for ST-DTDA shows solution quality achieved is up to 90% of the optimal on sparse graphs, in the best case, whilst worst-case quality bounds can be estimated within 5% of the solution found, in the best case

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.
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
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.
Includes bibliographical references (p. 105-107).
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
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.
by Mark F. Tompkins.
M.Eng.

Agir de manière autonome dans notre monde 3D requiert un large éventail de compétences, parmi lesquelles se trouvent la perception du milieu environnant, sa représentation précise et suffisamment efficace pour garder une trace du passé, la prise de décisions et l’action en vue d’atteindre des objectifs. Les animaux, par exemple les humains, se distinguent par leur robustesse lorsqu’il s’agit d’agir dans le monde. En particulier, ils savent s’adapter efficacement à de nouveaux environnements, mais sont aussi capables de maîtriser rapidement de nombreuses tâches à partir de quelques exemples. Ce manuscrit étudiera comment les réseaux neuronaux artificiels peuvent être entrainés pour acquérir un sous-ensemble de ces capacités. Nous nous concentrerons tout d’abord sur l’entrainement d’agents neuronaux à la cartographie sémantique, à la fois à partir d’un signal de supervision augmenté et avec des représentations neuronales de scènes. Les agents neuronaux sont souvent entrainés par apprentissage par renforcement (RL) à partir d’un signal de récompense peu dense. Guider l’apprentissage des capacités de cartographie d’une scène en ajoutant au signal de supervision des tâches auxiliaires favorisant le raisonnement spatial aidera à naviguer plus efficacement. Au lieu de travailler sur le signal d’entrainement des agents neuronaux, nous verrons également comment l’incorporation de représentations neuronales spécifiques de la sémantique et de la géométrie à l’architecture de l’agent peut contribuer à améliorer les performances de navigation sémantique. Ensuite, nous étudierons la meilleure façon d’explorer un environnement 3D afin de construire des représentations neuronales de l’espace qui soient aussi satisfaisantes que possible sur la base de métriques pensées pour la robotique que nous proposerons. Enfin, nous passerons d’agents de navigation à des agents multi-tâches et nous verrons à quel point il est important d’adapter les caractéristiques visuelles extraites des observations de capteurs à chaque tâche à accomplir pour réaliser une variété de tâches, mais aussi pour s’adapter à de nouvelles tâches inconnues à partir de quelques démonstrations. Ce manuscrit abordera donc différentes questions : Comment représenter une scène 3D et garder une trace de l’expérience passée dans un environnement ? – Comment s’adapter de manière robuste à de nouveaux environnements, scénarios et potentiellement de nouvelles tâches ? – Comment entrainer des agents à des tâches séquentielles à horizon long ? – Comment maîtriser conjointement toutes les sous-compétences requises ? – Quelle est l’importance de la perception en robotique ?
Autonomously behaving in the 3D world requires a large set of skills, among which are perceiving the surrounding environment, representing it precisely and efficiently enough to keep track of the past, making decisions and acting to achieve specified goals. Animals, for instance humans, stand out by their robustness when it comes to acting in the world. In particular, they can efficiently generalize to new environments, but are also able to rapidly master many tasks of interest from a few examples. This manuscript will study how artificial neural networks can be trained to acquire a subset of these abilities. We will first focus on training neural agents to perform semantic mapping, both from augmented supervision signal and with proposed neural-based scene representations. Neural agents are often trained with Reinforcement Learning (RL) from a sparse reward signal. Guiding the learning of scene mapping abilities by augmenting the vanilla RL supervision signal with auxiliary spatial reasoning tasks will help navigating efficiently. Instead of modifying the training signal of neural agents, we will also see how incorporating specific neural-based representations of semantics and geometry within the architecture of the agent can help improve performance in goal-driven navigation. Then, we will study how to best explore a 3D environment in order to build neural representations of space that are as satisfying as possible based on robotic-oriented metrics we will propose. Finally, we will move from navigation-only to multi-task agents, and see how important it is to tailor visual features from sensor observations to the task at hand to perform a wide variety of tasks, but also to adapt to new unknown tasks from a few demonstrations. This manuscript will thus address different important questions such as: How to represent a 3D scene and keep track of previous experience in an environment? – How to robustly adapt to new environments, scenarios, and potentially new tasks? – How to train agents on long-horizon sequential tasks? – How to jointly master all required sub-skills? – What is the importance of perception in robotics?

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-05-08T18:37:11Z No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5)
Approved for entry into archive by Caroline Xavier (caroline.xavier@pucrs.br) on 2018-05-15T19:07:36Z (GMT) No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5)
Made available in DSpace on 2018-05-15T19:14:18Z (GMT). No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5) Previous issue date: 2018-03-27
Sistemas multiagentes freq?entemente cont?m ambientes complexos e din?micos, nos quais os planos dos agentes podem falhar a qualquer momento durante a execu??o do sistema. Al?m disso, novos objetivos podem aparecer para os quais n?o existem nenhum plano dispon?vel. T?cnicas de planejamento s?o bem adequadas para lidar com esses problemas. H? uma quantidade extensa de pesquisa em planejamento centralizado para um ?nico agente, por?m, at? ent?o planejamento multiagente n?o foi completamente explorado na pr?tica. Plataformas multiagentes tipicamente proporcionam diversos mecanismos para coordena??o em tempo de execu??o, frequentemente necess?rios em planejamento online. Neste contexto, planejamento multiagente descentralizado pode ser eficiente e eficaz, especialmente em dom?nios fracamente acoplados, al?m de garantir algumas propriedades importantes em sistemas de agentes como privacidade e autonomia. N?s abordamos esse problema ao apresentar uma t?cnica para planejamento multiagente online que combina aloca??o de objetivos, planejamento individual utilizando rede de tarefas hier?rquicas (HTN), e coordena??o em tempo de execu??o para apoiar a realiza??o de objetivos sociais em sistemas multiagentes. Especificamente, n?s apresentamos um framework chamado Decentralised Online Multi-Agent Planning (DOMAP). Experimentos com tr?s dom?nios fracamente acoplados demonstram que DOMAP supera quatro planejadores multiagente do estado da arte com respeito a tempo de planejamento e tempo de execu??o, particularmente nos problemas mais dif?ceis.
Multi-agent systems often contain dynamic and complex environments where agents? course of action (plans) can fail at any moment during execution of the system. Furthermore, new goals can emerge for which there are no known plan available in any of the agents? plan library. Automated planning techniques are well suited to tackle both of these issues. Extensive research has been done in centralised planning for singleagents, however, so far multi-agent planning has not been fully explored in practice. Multi-agent platforms typically provide various mechanisms for runtime coordination, which are often required in online planning (i.e., planning during runtime). In this context, decentralised multi-agent planning can be efficient as well as effective, especially in loosely-coupled domains, besides also ensuring important properties in agent systems such as privacy and autonomy. We address this issue by putting forward an approach to online multi-agent planning that combines goal allocation, individual Hierarchical Task Network (HTN) planning, and coordination during runtime in order to support the achievement of social goals in multi-agent systems. In particular, we present a planning and execution framework called Decentralised Online Multi-Agent Planning (DOMAP). Experiments with three loosely-coupled planning domains show that DOMAP outperforms four other state-of-the-art multi agent planners with regards to both planning and execution time, particularly in the most difficult problems.

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.

Mes travaux s'intègrent aux recherches menées dans l'équipe SMAC de CRIStAL en Intelligence Artificielle Distribuée.Les sciences des données exploitent de larges volumes de données sur lesquelles des calculs sont effectués en parallèle par différents nœuds. Ces applications mettent à l'épreuve l'informatique distribuée en ce qui concerne l'allocation de tâches et l'équilibrage de charge. J'étudie dans cette thèse le problème de l'allocation continue de jobs concurrents, composés de tâches situées, sous-jacent au déploiement d'applications de traitement de données massives sur une grappe de serveurs. L'objectif est de minimiser le délai moyen de réalisation de ces jobs, appelée flowtime.Je propose dans ce document un modèle multi-agents d'assignation tâches-exécutants où les nœudsde calcul sont contrôlés par des agents collaboratifs, appelés agents-nœuds, qui négocient des réallocations locales pour aboutir à une meilleure répartition des tâches. Ces négociations se déroulent au fil de l'exécution des tâches. Grâce à leur modèle des pairs, les agents-nœuds sont capables d'identifier des opportunités au sein de l'allocation courante pour marchander des délégations voire des échanges de tâches avec leurs semblables. Pour améliorer la réactivité (responsiveness) de la stratégie multi-agents qui repose sur l'exécution asynchrone de comportements individuels en interaction, le processus de négociation s'appuie sur de multiples négociations bilatérales concurrentes.Mes campagnes d'expérimentation permettent de valider empiriquement l'efficacité de la réactivitéde ma stratégie multi-agents. En effet, ma méthode favorise un réordonnancement rapide des tâches,plutôt que la recherche de la solution optimale, ce qui permet une adaptation rapide. Mes expérimentations montrent que, lorsqu'elle est exécutée de manière concurrente au processus de consommation,notre stratégie de réallocation : (1) réduit significativement le temps de réordonnancement ; (2) améliorele délai moyen de réalisation ; (3) ne pénalise pas la consommation ; (4) est robuste aux aléas d'exécution ; et (5) s'adapte à la libération de jobs
My work is part of the research done by the SMAC team in the laboratory CRIStAL in Distributed Artificial Intelligence.Data sciences exploit large datasets on which computations are performed in parallel by differentnodes. These applications challenge distributed computing in terms of task allocation and load-balancing.In this thesis, I study the problem of continuous allocation of concurrent jobs, composed of situated tasks,underlying the deployment of massive data processing applications on a cluster of servers. The objectiveis to minimise the mean flowtime of these jobs.In this paper, I propose a multi-agent task-worker assignment model where computing nodes are controlled by collaborative agents, called node agents, which negotiate local task reallocations to achieve a bettertask distribution. These negotiations take place during the tasks execution. Thanks to their peer modelling,node agents are able to identify opportunities within the current allocation to negotiate task delegationsor even swaps with their peers. To improve the responsiveness of the multi-agent strategy, which is basedon the asynchronous execution of interacting individual behaviours, the negotiation process is based onmultiple concurrent bilateral negotiations.My experimental campaigns allow me to empirically validate the efficiency of the reactivity of mymulti-agent strategy. This is because my method encourages rapid reordering of tasks, rather than thesearch for the optimum solution, which allows responsiveness. My experiments show that, when executedconcurrently with the consumption process, our reallocation strategy : (1) significantly reduces the rescheduling time ; (2) improves the flowtime ; (3) does not penalise the consumption ; (4) is robust to executionhazards ; and (5) adapts to the release of jobs

The problem of determining who should do what given a set of tasks and a set of agents is called the task allocation problem. The problem occurs in many multi-agent system applications where a workload of tasks should be shared by a number of agents. In our case, the task allocation problem occurs as an integral part of a larger problem of determining if a task can be delegated from one agent to another. Delegation is the act of handing over the responsibility for something to someone. Previously, a theory for delegation including a delegation speech act has been specified. The speech act specifies the preconditions that must be fulfilled before the delegation can be carried out, and the postconditions that will be true afterward. To actually use the speech act in a multi-agent system, there must be a practical way of determining if the preconditions are true. This can be done by a process that includes solving a complex task allocation problem by the agents involved in the delegation. In this thesis a constraint-based task specification formalism, a complex task allocation algorithm for allocating tasks to unmanned aerial vehicles and a generic collaborative system shell for robotic systems are developed. The three components are used as the basis for a collaborative unmanned aircraft system that uses delegation for distributing and coordinating the agents' execution of complex tasks.

L’évolution du contexte de défense aéronaval nécessite une modification majeure de l’architecture des systèmes de senseurs actuels afin de maitriser les futures menaces et d’intégrer les nouveaux dispositifs et senseurs à venir. Ces senseurs, hétérogènes, complémentaires et embarqués sur des plateformes navales ou aériennes, sont essentiels pour l’acquisition de données de l’environnement et l’établissement de la situation tactique. Dans ce contexte, les plateformes peuvent collaborer et partager leurs ressources senseurs pour accomplir de nouvelles fonctionnalités et établir un panorama global de la situation. Dans cette thèse, nous avons conçu et développé un système multi-agent pour l’allocation de tâches à des ressources distribuées sur des plateformes distinctes dans le but d’accomplir des capacités collaboratives. Nous présentons des scénarios illustrant les besoins opérationnels auxquels l’architecture doit répondre, établissant ainsi un cahier des charges. Ensuite, nous détaillons les étapes de la conception et de l’implémentation de cette nouvelle architecture, en décrivant chaque type d’agent et les interactions possibles entre eux. Nous proposons un algorithme d’enchère nécessitant des échanges entre les agents, soumis aux contraintes de bande passante et de latence. Enfin, nous présentons un banc d’essai intégrant des outils de capture et de visualisation de métriques du système, permettant l’évaluation des concepts d’agents et de leurs mécanismes de communication. L’objectif est de démontrer que notre architecture répond aux besoins opérationnels spécifiés, notamment le passage à l’échelle des algorithmes et des interfaces de communications des agents, la résistance aux pannes et la performance du système
The changing context of naval and aerial defense requires a major modification of current sensor system architectures to overcome future threats and to integrate next generation devices and sensors. These sensors, heterogeneous, complementary, and embedded on naval or aerial platforms, are essential for acquiring data from the environment in order to establish the tactical situation. In this context, platforms can collaborate and share their sensor resources to achieve new functionalities and set up a global overview of the situation. In this thesis, we have designed and developed a multi-agent system for allocating tasks to distributed resources on distinct platforms in order to accomplish collaborative capabilities. We present scenarios illustrating the operational needs that the architecture must meet, thus establishing a set of specifications. Then, we detail the steps involved in designing and implementing this new architecture, describing each type of agent and the possible interactions between them. We propose an auction algorithm requiring exchanges between agents, subject to bandwidth and latency constraints. Finally, we present a test bed integrating tools for capturing and display system metrics, allowing the evaluation of agent concepts and their communication mechanisms. The objective is to demonstrate that our architecture meets the specified operational requirements, in particular the scalability of the agents’ algorithms and communication interfaces, fault tolerance, and system performance

Alors que les robots deviennent toujours plus présents dans les environnements humains, endossant toujours plus de tâches telles que le nettoyage, la surveillance ou encore le service en salle, leurs limites actuelles n’en deviennent que plus évidentes. Une de ces limites concerne leur capacité à naviguer en présence d’obstacles: ils chercheront systématiquement à les éviter, et resteront bloqués à défaut. Ce constat a mené à la création d’algorithmes de NAvigation en milieu MOdifiable (NAMO), devant permettre aux robots de manipuler les obstacles pour faciliter leurs déplacements. Néanmoins, ces algorithmes ont été conçus sous l’hypothèse qu’un seul robot agîsse dans l’environnement, biaisant les algorithmes à n’optimiser que son seul coût de déplacement – sans considération pour les humains ou d’autres robots. S’il est souhaitable que les robots puissent bénéficier de la capacité humaine à déplacer des obstacles, ils doivent néamoins le faire dans le respect des normes et règles sociales humaines. Nous avons donc étendu le problème de NAMO pour prendre en compte ces nouveaux aspects sociaux et multi-robots. En nous basant sur le concept d’espaces d’affordance, nous avons développé un modèle de coût d’occupation sociale permettant d’évaluer l’impact des objets déplacés sur la navigabilité de l’environnement. Nous avons implémenté (et amélioré) des algorithmes NAMO de référence, dans notre outil de simulation open source, puis les avons modifiés afin qu’ils puissent trouver un compromis entre coût de déplacement et coût d’occupation des obstacles manipulés – résultant en une amélioration de la navigabilité. Nous avons également développé une stratégie de coordination permettant d’exécuter ces mêmes algorithmes tels quels, sur plusieurs robots en parallèle, en absence de communication explicite, tout en préservant la garantie d’absence de collisions; vérifiant la pertinence de notre modèle de coût social en présence effective d’autres robots. Ces travaux constituent les premiers pas d’une NAMO Sociale et Multi-Robots
As robots become ever more commonplace in human environments, taking care of ever more tasks such as cleaning, security or food service, their current limitations only become more apparent. One such limitation is of their navigation capability in the presence of obstacles: they always avoid them, and freeze in place when avoidance is impossible. This is what brought about the creation of Navigation Among Movable Obstacles (NAMO) algorithms, expected to allow robots to manipulate obstacles as to facilitate their own movement. However, these algorithms were designed under the hypothesis of a single robot per environment, biasing NAMO algorithms into only optimizing the single robot's displacement cost - without any consideration for humans or other robots. While it is desirable to endow robots with the human capability of moving obstacles, they must however do so while respecting social norms and rules of humans. We have thus extended the NAMO problem as to take into account these new social and multi-robots aspects. By relying on the concept of affordance spaces, we have developed a social occupation cost model allowing the evaluation of the impact of moved objects on the environment's navigability. We implemented (and improved) reference NAMO algorithms, in our open source simulation tool, and modified them so that they may plan compromises between robot displacement cost and social occupation cost of moved obstacles - resulting in improved navigability. We also developed an implicit coordination strategy allowing the concurrent execution of these same algorithms by multiple robots as is, without any explicit communication requirements, while preserving the no-collision guarantee; verifying the relevance of our social occupation cost model in the actual presence of other robots. As such, this work constitutes the first steps towards a Social and Multi-Robot NAMO

Unmanned Aerial Vehicle (UAV), also called drones, are used for Search And Rescue (SAR) missions, mainly in the form of a pilot manoeuvring a single drone. However, the increase in labour to cover larger areas quickly would result in a very high cost and time spent per rescue operation. Therefore, there is a need for an easy to use, low-cost, and highly autonomous swarm of drones for SAR missions where the detection and rescue times are kept to a minimum. In this thesis, a Subsumption-based architecture is proposed, which combines multiple behaviours to create more complex behaviours. An investigation of (1) what are the critical aspects of controlling a swarm of drones, (2) how can a combination of different behavioural algorithms increase the performance of a swarm of drones, and (3) what benchmarks are necessary when evaluating the fitness of the behavioural algorithms. The proposed architecture was simulated in AirSim using the SimpleFlight flight controller through experiments that evaluated the individual layers and missions that simulated real-life scenarios. The results validate the modularity and reliability of the architecture, where the architecture has the potential for improvements in future iterations. For the search area of 400×400meters, the swarm consistently produced an average area coverage of at least 99.917% and found all the missing people in all missions, with the slowest average being 563 seconds. Compared to related work, the result produced similar or better times when scaled to the same proportions and higher area coverage. As comparisons of results in SAR missions can be difficult, the introduction of Active time can serve as a benchmark for others in future swarm performance measurements.

With the promise to shape the future of industry, multi-agent robotic technologies have the potential to change many aspects of daily life. Over the coming decade, they are expected to impact transportation systems, military applications such as reconnaissance and surveillance, search-and-rescue operations, or space missions, as well as provide support to emergency first responders. Motivated by the latest developments in the field of robotics, this thesis contributes to the evolution of the future generation of multi-agent robotic systems as they become smarter, more accurate, and diversified in terms of applications. But in order to achieve these goals, the individual agents forming cooperative robotic systems need to be specialized in what they can accomplish, while ensuring accuracy and preserving the ability to perform diverse tasks. This thesis addresses the problem of task allocation in swarm robotics in the specific context where specialized capabilities of the individual agents are considered. Based on the assumption that each individual agent possesses specialized functional capabilities and that the expected tasks, which are distributed in the surrounding environment, impose specific requirements, the proposed task allocation mechanisms are formulated in two different spaces. First, a rudimentary form of the team members’ specialization is formulated as a cooperative control problem embedded in the agents’ dynamics control space. Second, an advanced formulation of agents’ specialization is defined to estimate the individual agents’ task allocation probabilities in a dedicated specialization space, which represents the core contribution of this thesis to the advancement and practice in the area of swarm robotics. The original task allocation process formulated in the specialization space evolves through four stages of development. First, a task features recognition stage is conceptually introduced to leverage the output of a sensing layer embedded in robotic agents to drive the proposed task allocation scheme. Second, a matching scheme is developed to best match each agent’s specialized capabilities with the corresponding detected tasks. At this stage, a general binary definition of agents’ specialization serves as the basis for task-agent association. Third, the task-agent matching scheme is expanded to an innovative probabilistic specialty-based task-agent allocation framework to generalize the concept and exploit the potential of agents’ specialization consideration. Fourth, the general framework is further refined with a modulated definition of the agents’ specialization based on their mechanical, physical structure, and embedded resources. The original framework is extended and a prioritization layer is also introduced to improve the system’s response to complex tasks that are characterized based on the recognition of multiple classes. Experimental validation of the proposed specialty-based task allocation approach is conducted in simulation and on real-world experiments, and the results are presented and discussed in light of potential applications to demonstrate the effectiveness and efficiency of the proposed framework.

Made available in DSpace on 2016-06-02T19:06:14Z (GMT). No. of bitstreams: 1 6183.pdf: 2878708 bytes, checksum: f9bc336337651cbba67af52d8acb7ec2 (MD5) Previous issue date: 2014-06-10
Financiadora de Estudos e Projetos
Vehicle fleets are an important component in several applications, moving materials and people. Examples include material handling in warehouses, factories and port terminals, people transportation as in taxi fleets and emergency services, such as medical assistance, fire-fighters and police. Fleet operation is crucial for these applications: it can mean loss of money and commercial partners in case of industry, os loss of lives in case of emergency services. Controlling the fleet to achieve efficient levels of performance is a difficult problem, though, and becomes even harder as the fleet grows. Research in the area has been linking vehicle fleet operation to Multi-Agent Systems, because vehicle fleets are naturally distributed and Multi-agent System is a convenient abstraction to cope with distributed Artificial Intelligence problems. Therefore, it is proposed a Multi-Agent System to control vehicle fleets, focusing on material handling application in warehouses. The proposed system has three types of agents: Vehicle Agent, Loading Point Agent and Storage Point Agent. Agents interact amongst themselves through messages, trying to efficiently realize the material handling in a warehouse. System implementation is done through a simulation of a warehouse operation, built on top of MASON multi-agent system simulation platform. Task assignment strategies is also an important problem, therefore four strategies are shown and tested using the simulation: CNET, Fuzzy, DynCNET and FiTA. To enable comparison among these strategies, a Genetic Algorithm is employed to systematically search good parameters for each strategy. The proposed system, as well as the simulation, are offered as a framework for development of other vehicle fleets controlling multi-agent systems and/or task assignment strategies.
Em várias aplicações, frotas de veículos são um componente importante, transportando materiais e pessoas. Exemplos incluem o manejo de materiais em depósitos, fabricas e terminais portuários, o transporte de pessoas como em frotas de taxis e serviços de emergência, como socorro medico, bombeiros e polícia. A operacao da frota e crucial para essas aplicações: pode significar perda de dinheiro e parceiros comerciais no caso dos exemplos na indústria, ou perda de vidas, no caso de serviços de emergência. Porem, controlar a frota de modo que ela opere eficientemente e um problema difícil, que se torna ainda mais custoso com o aumento da frota. Pesquisas na área tem ligado a operação de frotas de veículos a Sistema Multiagente, notando os fatos de que frotas de veículos são naturalmente distribuídas e que o conceito de Agentes (e, consequentemente, Sistemas Multiagentes) e uma abstração conveniente para lidar com problemas de Inteligencia Artificial de forma distribuída. Com base nisto, e proposto um Sistema Multiagente para controle de frotas de veículos, focando a aplicação dessa frota no manejo de materiais em um depósito. O sistema proposto possui três tipos agentes: Agente de Veículo, Agente de Ponto de Carga e Agente de Ponto de Armazenamento. Os agentes interagem entre si, trocando mensagens a fim de realizar o manejo dos materiais no deposito de forma eficiente. O sistema e implementado na forma de uma simulação de operação de um deposito, construída na plataforma de simulação de sistemas multiagentes MASON. Como a estrategia de associação de tarefas também e um problema importante, quatro estratégias são mostradas e testadas através da simulação: CNET, Fuzzy, DynCNET e FiTA. Para possibilitar comparações entre as estrategias, um Algoritmo Genetico foi utilizado para sistematicamente encontrar bons parâmetros para as quatro estrategias. O sistema proposto, bem como a simulação, são oferecidos como framework para construção de outros sistemas multiagentes para frotas de veículos e/ou estrategias de associação de tarefas.

Decision making problems are amongst the most common challenges facing managers at different management levels in the organisation: strategic, tactical, and operational. However, prior reaching decisions at the operational level of the management hierarchy, operations management departments frequently have to deal with the optimisation process to evaluate the available decision alternatives. Industries with complex supply chain structures and service organisations that have to optimise the utilisation of their resources are examples. Conventionally, operational decisions used to be taken centrally by a decision making authority located at the top of a hierarchically-structured organisation. In order to take decisions, information related to the managed system and the affecting externalities (e.g. demand) should be globally available to the decision maker. The obtained information is then processed to reach the optimal decision. This approach usually makes extensive use of information systems (IS) containing myriad of optimisation algorithms and meta-heuristics to process the high amount and complex nature of data. The decisions reached are then broadcasted to the passive actuators of the system to put them in execution. On the other hand, recent advancements in information and communication technologies (ICT) made it possible to distribute the decision making rights and proved its applicability in several sectors. The market-based approach is as such a distributed decision making mechanism where passive actuators are delegated the rights of taking individual decisions matching their self-interests. The communication among the market agents is done through market transactions regulated by auctions. The system’s global optimisation, therefore, raise from the aggregated self-oriented market agents. As opposed to the centralised approach, the main characteristics of the market-based approach are the market mechanism and local knowledge of the agents. The existence of both approaches attracted several studies to compare them in different contexts. Recently, some comparisons compared the centralised versus market-based approaches in the context of transportation applications from an algorithm perspective. Transportation applications and routing problems are assumed to be good candidates for this comparison given the distributed nature of the system and due to the presence of several sources of uncertainty. Uncertainty exceptions make decisions highly vulnerable and necessitating frequent corrective interventions to keep an efficient level of service. Motivated by the previous comparison studies, this research aims at further investigating the features of both approaches and to contrast them in the context of a distributed task allocation problem in light of environmental uncertainty. Similar applications are often faced by service industries with mobile workforce. Contrary to the previous comparison studies that sought to compare those approaches at the mechanism level, this research attempts to identify the effect of the most significant characteristics of each approach to face environmental uncertainty, which is reflected in this research by the arrival of dynamic tasks and the occurrence of stochasticity delays. To achieve the aim of this research, a target optimisation problem from the VRP family is proposed and solved with both approaches. Given that this research does not target proposing new algorithms, two basic solution mechanisms are adopted to compare the centralised and the market-based approach. The produced solutions are executed on a dedicated multi-agent simulation system. During execution dynamism and stochasticity are introduced. The research findings suggest that a market-based approach is attractive to implement in highly uncertain environments when the degree of local knowledge and workers’ experience is high and when the system tends to be complex with large dimensions. It is also suggested that a centralised approach fits more in situations where uncertainty is lower and the decision maker is able to make timely decision updates, which is in turn regulated by the size of the system at hand.

The field of swarm robotics has been growing fast over the last few years. Using a swarm of simple and cheap robots has advantages in various tasks. Apart from performance gains on tasks that allow for parallel execution, simple robots can also be smaller, enabling them to reach areas that can not be accessed by a larger, more complex robot. Their ability to cooperate means they can execute complex tasks while offering self-organised adaptation to changing environments and robustness due to redundancy. In order to keep individual robots simple, a control algorithm has to keep expensive communication to a minimum and has to be able to act on little information to keep the amount of sensors down. The number of sensors and actuators can be reduced even more when necessary capabilities are spread out over different agents that then combine them by cooperating. Self-organised differentiation within these heterogeneous groups has to take the individual abilities of agents into account to improve group performance. In this thesis it is shown that a homogeneous group of versatile agents can not be easily replaced by a heterogeneous group, by separating the abilities of the versatile agents into several specialists. It is shown that no composition of those specialists produces the same outcome as a homogeneous group on a clustering task. In the second part of this work, an adaptation mechanism for a group of foragers introduced by Labella et al. (2004) is analysed in more detail. It does not require communication and needs only the information on individual success or failure. The algorithm leads to self-organised regulation of group activity depending on object availability in the environment by adjusting resting times in a base. A possible variation of this algorithm is introduced which replaces the probabilistic mechanism with which agents determine to leave the base. It is demonstrated that a direct calculation of the resting times does not lead to differences in terms of differentiation and speed of adaptation. After investigating effects of different parameters on the system, it is shown that there is no efficiency increase in static environments with constant object density when using a homogeneous group of agents. Efficiency gains can nevertheless be achieved in dynamic environments. The algorithm was also reported to lead to higher activity of agents which have higher performance. It is shown that this leads to efficiency gains in heterogeneous groups in static and dynamic environments.

The primary focus of this research is on the distributed allocation of dynamically arriving interdependent tasks to the agents of a heterogeneous multi-agent system in an uncertain environment. This dissertation consists of three parts. First, we develop a centralized task allocation model which explicitly considers the communication between the agents in coordinated problem solving. The tasks enter the system with certain payment and specific processing requirements. The agents are grouped into different types based on their processing capabilities. A task can only be processed by an appropriate agent. Processing of the tasks incurs certain operational cost on the multi-agent system resulting from processing and communication costs. The performance of an agent system is defined as the discounted sum of rewards over an infinite time horizon. We formulate the task assignment problem as a Markov decision problem and show that a stationary policy exists. An action elimination procedure is proposed that decreases the action space for each state. Moreover, a heuristic policy is proposed based on certain structural properties and is shown to perform close to 1% of the policy obtained from computational methods. The second part of the dissertation studies different distributed task allocation models and shows that distributed task allocation may be preferable over centralized task allocation despite their lower performance for the agent system. Each of these decision methods are evaluated based on the computational costs incurred in the decision making and the information exchange cost between the agents. The task allocation methods are classified into different scopes such as system level, group level, and individual level. For each level of scope, we consider both off-line and on-line decision procedures. The composite performance of each model is computed in order to evaluate cost effectiveness of a decision method. We show that centralized methods may not be preferred due to excessive decision costs involved. We also investigate the performance of multi-agent systems under partial information about other agents in the system. The third and final part of the dissertation investigates the effect of organizational structures on the performance of multi-agent systems. We study different organizational structures resulting from coalition formation between individual agents in the multi-agent systems. The coalitions are formed between agents to benefit from the increased state information. (Abstract shortened by UMI.)

碩士
國立臺灣大學
資訊工程學研究所
94
Coalition formation is a process to form a group and solve a problem via cooperation. Because the rising of network, each computing device can communicate through network. We can integrate resources of network and use it by coalition formation. In recent years, many researches focus on this topic. New method to decompose task, to gather resources and to form a coalition within various kind of environment are proposed. However, once a task requires a large amount of time to execute, we must form a coalition for a long period of time. Beside, in a high mobility network, forming a coalition and accomplish the task is challenge because the movable feature. In this thesis, we propose a new model which integrates case-based reasoning, negotiation, and reinforcement learning to improve the coalition formation process. Coalitions in our model suit for executing long term task or for accomplishing a task in high mobility networks. In this model, we search for and reuse the past solutions to apply to the problem we are facing currently. When the solution is found, required resources are gathered through negotiation. Then, the coalition is formed and task is executed. No matter the execution is successful or not, we extract experiences from this coalition formation process by reinforcement learning and reuse it if similar problems appear in the future. In this way, we can form coalitions with long period of lifetime or with stable characteristic. Our experiments also show the advantage of our model in these two different environments.

碩士
朝陽科技大學
資訊管理系碩士班
89
There has been much research on the cooperation issue for multi-agent robotic systems. Most of them focused on a single cooperation mechanism to solve their problems. In reality, it is very difficult that a single cooperation mechanism for a group under unknown and dynamic situations works in high performance. In order to obtain high performance of cooperation in unknown and dynamic environments, it is better to utilize several cooperation algorithms and select a suitable one for each different situation than a single one for all the situations. This thesis provided a method of adaptive coordination for multi-agent systems to solve the Object-Sorting Task. It coordinated the agents to move objects to destinations efficiently and effectively. Adaptive coordination is achieved by looking up a relationship table from which a relative best coordination algorithm can be found to perform the object-sorting tasks. Adaptive resonance theory network is utilized to cluster the object distribution so as to help constructing the relationship table. Java-based mobile agents are utilized to implement the simulation environment for solving the OST problem. The key issues of the simulation environment include the ART grouping, cooperation algorithms, and their relationship. By using the adaptive rules for performing the OST, experimental results showed that the agents work more efficient than any single coordination solution developed before. The analysis for object distributions of OST provided a concrete result to make agents perform the OST with the best performance.

Rapidly evolving technologies in the autonomous operation of Uninhabited Aerial Vehicles (UAVs) and associated developments in low-cost sensors have created significant interest among researchers in using them for various civil and military applications. With the autonomy and presence of various sensing equipment, onboard UAVs lead to problems in the privacy, safety, and security of many safety-critical infrastructures. A critical infrastructure that needs to be protected is approximated by the convex region and called territory. A team of UAVs that protects the territory is called the defenders and UAVs which try to enter the territory are called the intruders. A team of defenders operates inside and, on the perimeter, and protects the territory from intruders by capturing intruders on the perimeter is referred as the Perimeter Defense Problem (PDP). The velocity of intruders is used to predict the arrival location on the perimeter and arrival time. In this way, each intruder generates a spatio-temporal task for the defenders to reach tha= t specific location at a specific time to neutralize that intruder. So, PDP is formulated as the spatio-temporal multi-task assignment (STMTA) problem. In the STMTA problem, some minimum number of defenders (robots) are required to execute the given spatio-temporal tasks; without this minimum number of defenders, STMTA problem is ill-posed. The proposed Dynamic REsource Allocation with Multi-task assignment (DREAM) algorithm solves the bottleneck issue of iterative computation for the required number of robots and provides the two-step solution to compute the required minimum number of robots and their optimal assignments to execute given spatio-temporal tasks. Next, the trajectory generation algorithm has been developed to compute the trajectory of each defender. Furthermore, it is proved that all the computed trajectories of homogeneous agents, operating in the convex region, are collision-free. For highly maneuvering intruders, the errors in the prediction of tasks deteriorate the performance of DREAM. In the P-DREAM approach, a dedicated defender is assigned to each prioritized intruder by enforcing the prioritized intruder as a first task. A prioritized intruder must be delegated to the reserve defender before it becomes infeasible for the reserve defender. The static design for PDP computes the minimum number of reserve stations, their optimal location, priority region, monitoring region, and the minimum number of defenders required for monitoring. The quantification of priority and monitoring region will be helpful in practical implementations. For protecting a large territory, more defenders are required, also each defender has a limited sensing range to detect and track intruders. To address these issues of partial observability and scalability the decentralized spatio-temporal multi-task assignment approach is proposed. A modified consensus-based bundle algorithm has been proposed to solve the STMTA problem. Finally, the thesis demonstrates the working of the DREAM approach for heterogeneous pick-up and just-in-time delivery (PJITD) problems. Just-in-time tasks have been used to improve operational efficacy for static (priorly known) tasks. The non-iterative solution of modified DREAM overcomes the bottleneck problem of the iterative (and hence offline) solution and provides a real-time implementable solution. The cost function is modified to include the traveling time, operating time, and heterogeneous skills required to execute the tasks. The working of modified DREAM is illustrated using high-fidelity ROS2-GAZEBO simulations and lab-scale hardware experiments.