Decentralised allocation of structured tasks in heterogeneous agent teams

Abstract

Sistemas multiagentes permitem o desenvolvimento de soluções flexíveis e robustas e têm sido utilizados há vários anos na academia e na indústria para projetar e implementar sistemas distribuídos complexos em vários domínios. No entanto, ainda há desafios no desenvolvimento de estratégias apropriadas para que times de agentes operem de maneira eficiente. Um aspecto crítico é a coordenação entre os agentes, que, apesar dos esforços dos pesquisadores, ainda hoje é um desafio. Agentes precisam se coordenar para alcançar objetivos que não conseguem realizar sozinhos, devido à falta de conhecimento sobre o mundo ou por qualquer outro motivo, como recursos limitados ou distância espacial. Na robótica, sistemas com múltiplos robôs também carecem de complexos métodos de coordenação, sem os quais se torna impossível construir verdadeiros times de robôs. Existem diferentes abordagens propostas para a coordenação em sistemas multiagentes e em sistemas multi-robôs, dentre as quais muitas lidam diretamente com o problema de alocação de tarefas. De fato, a alocação de tarefas é uma importante área de pesquisa quando se lida com o problema de coordenar grupos de agentes ou robôs. Além disso, cenários do mundo real geralmente requerem o uso de entidades heterogêneas e a execução de tarefas com estruturas e complexidades diferentes.Assim, é necessário desenvolver métodos que permitam projetar e implantar aspectos relacionados a alocação de tarefas tornando os sistemas cada vez mais eficientes. Considerando essa necessidade, apresentamos um mecanismo decentralizado para a alocação de diferentes tipos de tarefas entre múltiplos agentes heterogêneos que desempenham papéis e executam tarefas de acordo com suas capacidades. A avaliação do nosso mecanismo de alocação de tarefas foi realizada através de várias simulações. Também avaliamos nosso mecanismo em uma simulação com tarefas relacionadas ao cenário de busca e resgate em desastres naturais por inundação, onde vários robôs autônomos podem ser empregados para apoiar a equipe de resgate. Os resultados mostram que o mecanismo proposto fornece alocações próximas ao resultado ótimo.

Multi-agent systems allow the development of flexible and robust solutions and have been used for several years in academia and industry to design and implement complex distributed systems in various domains. However, there are many challenges in developing appropriate strategies for multi-agent teams so that they operate efficiently. One critical aspect is the coordination between agents, which despite much research effort is still a challenge. Agents need to coordinate to achieve goals that, for whatever reason, cannot be accomplished alone, due to the lack of knowledge about the world or for any other reason, such as limited resources and spatial distance. In robotics, systems with multiple robots also require complex coordination methods, without which it is impossible to build real robotic teams. There are many approaches proposed in the literature for MAS and multi-robot system coordination, many of them directly related to task allocation problems. In fact, task allocation is an important research area in dealing with the problem of coordinating a group of agents or robots. Besides that, realworld scenarios usually require the use of heterogeneous entities and the execution of tasks with different structures and complexities.Thus, it is necessary to develop further methods to support the design and implementation of aspects related to task allocation. Taking that into account, we present a decentralised task allocation mechanism considering different types of tasks for heterogeneous agent teams where agents play different roles and carry out tasks according to their own capabilities. We have run several experiments in order to evaluate the proposed mechanism. We also evaluate our task allocation mechanism in a simulation with tasks related to the search and rescue scenario in natural disaster by flooding where multiple autonomous robots can be employed to support human rescuers. The results show that the proposed mechanism provides near-optimal allocations.