Distributed algorithms for dynamic task allocation using swarm of robots.

A Inteligência de Enxame foi proposta a partir da observação do comportamento social de espécies de insetos, pássaros e peixes. A ideia central deste comportamento coletivo é executar uma tarefa complexa decompondo-a em tarefas simples, que são facilmente executadas pelos indivíduos do enxame. A realização coordenada destas tarefas simples, respeitando uma proporção pré-definida de execução, permite a realização da tarefa complexa. O problema de alocação de tarefas surge da necessidade de alocar as tarefas aos indivíduos de modo coordenado, permitindo o gerenciamento do enxame. A alocação de tarefas é um processo dinâmico pois precisa ser continuamente ajustado em resposta a alterações no ambiente, na configuração do enxame e/ou no desempenho do mesmo. A robótica de enxame surge deste contexto de cooperação coletiva, ampliada à robôs reais. Nesta abordagem, problemas complexos são resolvidos pela realização de tarefas complexas por enxames de robôs simples, com capacidade de processamento e comunicação limitada. Objetivando obter flexibilidade e confiabilidade, a alocação deve emergir como resultado de um processo distribuído. Com a descentralização do problema e o aumento do número de robôs no enxame, o processo de alocação adquire uma elevada complexidade. Desta forma, o problema de alocação de tarefas pode ser caracterizado como um processo de otimização que aloca as tarefas aos robôs, de modo que a proporção desejada seja atendida no momento em que o processo de otimização encontre a solução desejada. Nesta dissertação, são propostos dois algoritmos que seguem abordagens distintas ao problema de alocação dinâmica de tarefas, sendo uma local e a outra global. O algoritmo para alocação dinâmica de tarefas com abordagem local (ADTL) atualiza a alocação de tarefa de cada robô a partir de uma avaliação determinística do conhecimento atual que este possui sobre as tarefas alocadas aos demais robôs do enxame. O algoritmo para alocação dinâmica de tarefas com abordagem global (ADTG) atualiza a alocação de tarefas do enxame com base no algoritmo de otimização PSO (Particle swarm optimization). No ADTG, cada robô possui uma possível solução para a alocação do enxame que é continuamente atualizada através da troca de informação entre os robôs. As alocações são avaliadas quanto a sua aptidão em atender à proporção-objetivo. Quando é identificada a alocação de maior aptidão no enxame, todos os robôs do enxame são alocados para as tarefas definidas por esta alocação. Os algoritmos propostos foram implementados em enxames com diferentes arranjos de robôs reais demonstrando sua eficiência e eficácia, atestados pelos resultados obtidos.Swarm Intelligence has been proposed based on the observation of social behavior of insect species, birds and fishes. The main idea of this collective behavior is to perform a complex task decomposing it into many simple tasks, that can be easily performed by individuals of the swarm. Coordinated realization of these simple tasks while adhering to a pre-defined distribution of execution, allows for the achievement of the original complex task. The problem of task allocation arises from the need of assigning tasks to individuals in a coordinated fashion, allowing a good management of the swarm. Task allocation is a dynamic process because it requires a continuous adjustment in response to changes in the environment, the swarm configuration and/or the performance of the swarm. Swarm robotics emerges from this context of collective cooperation applied to swarms of real robots. In this approach, complex problems are solved by performing complex tasks using swarms of simple robots, with a limited processing and communication capabilities. Aiming at achieving flexibility and reliability, the allocation should emerge as a result of a distributed process. With the decentralization of the problem and the increasing number of robots in the swarm, the allocation process acquires a high complexity. Thus, the problem of task allocation can be characterized as an optimization process that assigns tasks to robots, so that the desired proportion is met at the end of the optimization process, find the desired solution. In this dissertation, we propose two algorithms that follow different to the problem of dynamic task allocation approaches: one is local and the other global. The algorithm for dynamic allocation of tasks with a local approach (ADTL) updates the task assignment of each robot based on a deterministic assessment of the current knowledge it has so far about the tasks allocated to the other robots of the swarm. The algorithm for dynamic task allocation with a global approach (ADTG) updates the allocation of tasks based on a swarm optimization process, inspired by PSO (Particle swarm optimization). In ADTG, each robot has a possible solution to the swarm allocation, which is continuously updated through the exchange of information between the robots. The allocations are evaluated for their fitness in meeting the goal proportion. When the allocation of highest fitness in the swarm is identified, all robots of the swarm are allocated to the tasks defined by this allocation. The proposed algorithms were implemented on swarms of different arrangements of real robots demonstrating their efficacy, robustness and efficiency, certified by obtained the results