The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and collaborative autonomous manufacturing. In these MRS applications, there are realistic constraints on robots and tasks that must be taken into account both from the modeling perspective and the algorithmic perspective. From the modeling aspect, such constraints include (a) Task group constraints: where tasks form disjoint groups and each robot can be assigned to at most one task in each group. One example of the group constraints comes from tightly-coupled tasks, where multiple micro tasks form one tightly-coupled macro task and need multiple robots to perform each simultaneously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically and the payoffs of future tasks are unknown. Such tasks arise in scenarios like searchrescue, where new victims are found dynamically. (d) Robot budget constraints: where the number of tasks each robot can perform is bounded according to the resource it possesses (e.g., energy). From the solution aspect, there is often a need for decentralized solution that are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to avoid single-point failure or be adaptive to environmental changes. Most existing algorithms either do not consider the above constraints in problem modeling, are centralized or do not provide formal performance guarantees. In this thesis, I propose methods to address these issues for two classes of problems, namely, the constrained linear assignment problem and constrained generalized assignment problem. Constrained linear assignment problem belongs to P, while constrained generalized assignment problem is NP-hard. I develop decomposition-based distributed auction algorithms with performance guarantees for both problem classes. The multi-robot assignment problem is decomposed into an optimization problem for each robot and each robot iteratively solving its own optimization problem leads to a provably good solution to the overall problem. For constrained linear assignment problem, my approaches provides an almost optimal solution. For constrained generalized assignment problem, I present a distributed algorithm that provides a solution within a constant factor of the optimal solution. I also study the online version of the task allocation problem with task group constraints. For the online problem, I prove that a repeated greedy version of my algorithm gives solution with constant factor competitive ratio. I include simulation results to evaluate the average-case performance of the proposed algorithms. I also include results on multi-robot cooperative package transport to illustrate the approach.

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

Sistemas multiagente são construídos para atingir objetivos complexos e abrangentes, que estão além da capacidade de um único agente. Estes objetivos podem ser representados através de tarefas, que devem ser realizadas pelos agentes de forma a otimizar o desempenho do sistema. Em muitos ambientes reais, a escala do problema envolve tanto uma grande quantidade de agentes, quanto uma grande quantidade de tarefas. Além disto, os agentes devem lidar com informações incompletas, realizando tarefas em tempo hábil. O termo extreme teams foi introduzido na literatura para designar as seguintes quatro características da alocação de tarefas: oa ambientes são dinâmicos; os agentes podem realizar múltiplas tarefas; os agentes podem possuir funcionalidades sobrepostas; e podem existir interrelacionamentos entre tarefas, impondo, por exemplo, necessidade de realização simultânea. Abordagens existentes na literatura tratam, efetivamente, apenas as três primeiras características de extreme teams. Esta dissertação apresenta um algoritmo para alocação de tarefas, chamado eXtreme-Ants, que trata todas as quatro características de extreme teams. O algoritmo é inspirado no sucesso ecológico dos insetos sociais, e utiliza as metáforas de divisão de trabalho e recrutamento para transporte cooperativo. A metáfora de divisão de trabalho proporciona decisões rápidas e eficientes, atendendo as três primeiras características de extreme teams. O recrutamento permite formar grupos de agentes comprometidos com a realização simultânea de tarefas que exigem esforço conjunto, atendendo a quarta característica: inter-relacionamentos entre tarefas. Com isto, concretiza-se de fato o conceito completo de extreme teams. Experimentos foram realizados em dois ambientes distintos: um simulador independente de domínio e o simulador RoboCup Rescue. Os resultados obtidos demonstraram que a eficiência do eXtreme-Ants é balanceada com relação ao desempenho, quantidade de comunicação e esforço computacional. / Multiagent systems aim at achieving complex and broad goals, which are beyond the capability of a single agent. These goals can be represented by tasks, which must be performed by the agents in order to optimize the performance of the system. In many real-world environments, the scale of problems involves both a large number of agents and a large number of tasks. Besides, the agents must reason with incomplete and uncertain information, in a timely fashion. The expression extreme teams was introduced in the literature to describe the following four characteristics regarding task allocation: dynamic environments; agents may perform multiple tasks; agents can have overlapping functionality; and inter-task constraints (such as simultaneous execution requirements) may be present. Existing approaches effectively deal with just the three first characteristics of extreme teams. This dissertation presents an algorithm for allocating tasks to agents, called eXtreme- Ants, which deals with all the four characteristics of extreme teams. The algorithm is inspired in the ecological success of social insects, and uses the metaphors of division of labor and recruitment for cooperative transport. The metaphor provides fast and efficient decision-making, complying to the first three characteristics. The recruitment ensures the formation of groups of agents committed to the simultaneous execution of tasks that require joint efforts, complying to the fourth characteristic: inter-task constraints. Thus, the full concept of extreme teams is indeed realized. Experiments were performed in two distict environments: a domain independent simulator, and the RoboCup Rescue simulator. The results shown that eXtreme-Ants achieves a balanced efficiency regarding performance, communication, and computational effort.

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

Sistemas multiagente são construídos para atingir objetivos complexos e abrangentes, que estão além da capacidade de um único agente. Estes objetivos podem ser representados através de tarefas, que devem ser realizadas pelos agentes de forma a otimizar o desempenho do sistema. Em muitos ambientes reais, a escala do problema envolve tanto uma grande quantidade de agentes, quanto uma grande quantidade de tarefas. Além disto, os agentes devem lidar com informações incompletas, realizando tarefas em tempo hábil. O termo extreme teams foi introduzido na literatura para designar as seguintes quatro características da alocação de tarefas: oa ambientes são dinâmicos; os agentes podem realizar múltiplas tarefas; os agentes podem possuir funcionalidades sobrepostas; e podem existir interrelacionamentos entre tarefas, impondo, por exemplo, necessidade de realização simultânea. Abordagens existentes na literatura tratam, efetivamente, apenas as três primeiras características de extreme teams. Esta dissertação apresenta um algoritmo para alocação de tarefas, chamado eXtreme-Ants, que trata todas as quatro características de extreme teams. O algoritmo é inspirado no sucesso ecológico dos insetos sociais, e utiliza as metáforas de divisão de trabalho e recrutamento para transporte cooperativo. A metáfora de divisão de trabalho proporciona decisões rápidas e eficientes, atendendo as três primeiras características de extreme teams. O recrutamento permite formar grupos de agentes comprometidos com a realização simultânea de tarefas que exigem esforço conjunto, atendendo a quarta característica: inter-relacionamentos entre tarefas. Com isto, concretiza-se de fato o conceito completo de extreme teams. Experimentos foram realizados em dois ambientes distintos: um simulador independente de domínio e o simulador RoboCup Rescue. Os resultados obtidos demonstraram que a eficiência do eXtreme-Ants é balanceada com relação ao desempenho, quantidade de comunicação e esforço computacional. / Multiagent systems aim at achieving complex and broad goals, which are beyond the capability of a single agent. These goals can be represented by tasks, which must be performed by the agents in order to optimize the performance of the system. In many real-world environments, the scale of problems involves both a large number of agents and a large number of tasks. Besides, the agents must reason with incomplete and uncertain information, in a timely fashion. The expression extreme teams was introduced in the literature to describe the following four characteristics regarding task allocation: dynamic environments; agents may perform multiple tasks; agents can have overlapping functionality; and inter-task constraints (such as simultaneous execution requirements) may be present. Existing approaches effectively deal with just the three first characteristics of extreme teams. This dissertation presents an algorithm for allocating tasks to agents, called eXtreme- Ants, which deals with all the four characteristics of extreme teams. The algorithm is inspired in the ecological success of social insects, and uses the metaphors of division of labor and recruitment for cooperative transport. The metaphor provides fast and efficient decision-making, complying to the first three characteristics. The recruitment ensures the formation of groups of agents committed to the simultaneous execution of tasks that require joint efforts, complying to the fourth characteristic: inter-task constraints. Thus, the full concept of extreme teams is indeed realized. Experiments were performed in two distict environments: a domain independent simulator, and the RoboCup Rescue simulator. The results shown that eXtreme-Ants achieves a balanced efficiency regarding performance, communication, and computational effort.

Sistemas multiagente são construídos para atingir objetivos complexos e abrangentes, que estão além da capacidade de um único agente. Estes objetivos podem ser representados através de tarefas, que devem ser realizadas pelos agentes de forma a otimizar o desempenho do sistema. Em muitos ambientes reais, a escala do problema envolve tanto uma grande quantidade de agentes, quanto uma grande quantidade de tarefas. Além disto, os agentes devem lidar com informações incompletas, realizando tarefas em tempo hábil. O termo extreme teams foi introduzido na literatura para designar as seguintes quatro características da alocação de tarefas: oa ambientes são dinâmicos; os agentes podem realizar múltiplas tarefas; os agentes podem possuir funcionalidades sobrepostas; e podem existir interrelacionamentos entre tarefas, impondo, por exemplo, necessidade de realização simultânea. Abordagens existentes na literatura tratam, efetivamente, apenas as três primeiras características de extreme teams. Esta dissertação apresenta um algoritmo para alocação de tarefas, chamado eXtreme-Ants, que trata todas as quatro características de extreme teams. O algoritmo é inspirado no sucesso ecológico dos insetos sociais, e utiliza as metáforas de divisão de trabalho e recrutamento para transporte cooperativo. A metáfora de divisão de trabalho proporciona decisões rápidas e eficientes, atendendo as três primeiras características de extreme teams. O recrutamento permite formar grupos de agentes comprometidos com a realização simultânea de tarefas que exigem esforço conjunto, atendendo a quarta característica: inter-relacionamentos entre tarefas. Com isto, concretiza-se de fato o conceito completo de extreme teams. Experimentos foram realizados em dois ambientes distintos: um simulador independente de domínio e o simulador RoboCup Rescue. Os resultados obtidos demonstraram que a eficiência do eXtreme-Ants é balanceada com relação ao desempenho, quantidade de comunicação e esforço computacional. / Multiagent systems aim at achieving complex and broad goals, which are beyond the capability of a single agent. These goals can be represented by tasks, which must be performed by the agents in order to optimize the performance of the system. In many real-world environments, the scale of problems involves both a large number of agents and a large number of tasks. Besides, the agents must reason with incomplete and uncertain information, in a timely fashion. The expression extreme teams was introduced in the literature to describe the following four characteristics regarding task allocation: dynamic environments; agents may perform multiple tasks; agents can have overlapping functionality; and inter-task constraints (such as simultaneous execution requirements) may be present. Existing approaches effectively deal with just the three first characteristics of extreme teams. This dissertation presents an algorithm for allocating tasks to agents, called eXtreme- Ants, which deals with all the four characteristics of extreme teams. The algorithm is inspired in the ecological success of social insects, and uses the metaphors of division of labor and recruitment for cooperative transport. The metaphor provides fast and efficient decision-making, complying to the first three characteristics. The recruitment ensures the formation of groups of agents committed to the simultaneous execution of tasks that require joint efforts, complying to the fourth characteristic: inter-task constraints. Thus, the full concept of extreme teams is indeed realized. Experiments were performed in two distict environments: a domain independent simulator, and the RoboCup Rescue simulator. The results shown that eXtreme-Ants achieves a balanced efficiency regarding performance, communication, and computational effort.

付記する学位プログラム名: グローバル生存学大学院連携プログラム / 京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第22771号 / 工博第4770号 / 新制||工||1746(附属図書館) / 京都大学大学院工学研究科機械理工学専攻 / (主査)教授 松野 文俊, 教授 椹木 哲夫, 教授 泉田 啓 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

This thesis addresses the improvement of cooperative task allocation to vehicles in multiple-vehicle, multiple-target scenarios through the use of more effective preplanned tours. Effective allocation of vehicles to targets requires knowledge of both the team objectives and the contributions that individual vehicles can make toward accomplishing team goals. This is primarily an issue of individual vehicle path planning --- determining the path the vehicles will follow to accomplish individual and team goals. Conventional methods plan optimal point-to-point path segments that often result in lengthy and suboptimal tours because the trajectory neither considers future tasks nor the overall path. However, cooperation between agents is improved when the team selects vehicle assignments based on the ability to complete immediate and subsequent tasks. This research demonstrates that planning more efficient tour paths through multiple targets results in better use of individual vehicle resources, faster completion of team objectives, and improved overall cooperation between agents. This research presents a method of assigning unmanned aerial vehicles to targets to improve cooperation. A tour path planning method was developed to overcome shortcomings of traditional point-to-point path planners, and is extended to the specific tour-planning needs of this problem. The planner utilizes an on-line learning heuristic search to find paths that accomplish team goals in the shortest flight time. The learning search planner uses the entire sensor footprint, more efficiently plans tours through closely packed targets, and learns the best order for completion of the multiple tasks. The improved planner results in assignment completion times that range on average between 1.67 and 2.41 times faster, depending on target spread. Assignments created from preplanned tours make better use of vehicle resources and improve team cooperation. Path planning and assignment selection are accomplished in near real-time through the use of path heuristics and assignment cost estimates to reduce the problem size to tractable levels. Assignments are ordered according to estimated or predicted value. A reduced number of ordered assignments is considered and evaluated to control problem growth. The estimates adequately represent the actual assignment value, effectively reduce problem size, and produce near-optimal paths and assignments for near-real-time applications.

In highly autonomous robotic systems, human operators are able to attend to their own, separate tasks, but robots still need occasional human intervention. In this scenario, it may be difficult for human operators to determine the status of the system and environment when called upon to aid the robot. The resulting lack of situation awareness (SA) is a problem common to other automated systems, and it can lead to poor performance and compromised safety. Existing research on this problem suggested that reliable automation of information processing, called diagnostic aiding, leads to better operator SA. The effects of unreliable diagnostic aiding, however, were not well understood. These effects are likely to depend on the ability of the operator to perform the task unaided. That is, under conditions in which the operator can reconcile their own sensing with that of the robot, the influence of unreliable diagnostic aiding may be more pronounced. When the robot is the only source of information for a task, these effects may be weaker or may reverse direction. The purpose of the current experiment was to determine if SA is differentially affected by unreliability at different levels of unaided human performance and at different stages of diagnostic aiding. This was accomplished by experimentally manipulating the stage of diagnostic aiding, robot reliability, and the ability of the operator to build SA unaided. Results indicated that while reliable diagnostic aiding is generally useful, unreliable diagnostic aiding has effects that depend on the amount of information available to operators in the environment. This research improves understanding of how robots can support operator SA and can guide the development of future robots so that humans are most likely to use them effectively.

Embodied agents are agents acting in the physical world, such as persons, robots, unmanned air or ground vehicles and so on. These types of agents are subject to spatio-temporal constraints, which do not exist for agents acting in a virtual environment. The movement of embodied agents is limited by obstacles and maximum velocity, while their communication is limited by the transmission range of their wireless devices. This dissertation presents contributions to the techniques of coalition formation and teamwork coordination for embodied agents. We considered embodied agents in three different settings, each of them representative of a class of practical applications. First, we study coalition formation in the one dimensional world of vehicles driving on a highway. We assume that vehicles can communicate over short distances and carry agents which can advise the driver on convoy formation decisions. We introduce techniques which allow vehicles to influence the speed of the convoys, and show that this yields convoys which have a higher utility for the participating vehicles. Second, we address the problem of coalition formation in the two dimensional world. The application we consider is a disaster response scenario. The agents are forming coalitions through a multi-issue negotiation with spatio-temporal components where the coalitions maintain a set of commitments towards participating agents. Finally, we discuss a scenario where embodied agents form coalitions to optimally address dynamic, non-deterministic, spatio-temporal tasks. The application we consider is firefighters acting in a disaster struck city.