Optimization of communication in the dynamic task allocation using swarm of robots
| Autor: | Ribeiro, Luigi Maciel |
|---|---|
| Přispěvatelé: | Nedjah, Nadia, Mourelle, Luiza de Macedo, Domingos, Roberto Pinheiro, Ayala, Helon Vicente Hultmann |
| Jazyk: | portugalština |
| Rok vydání: | 2018 |
| Předmět: |
Artificial intelligence
Topologia de comunicação communication topology Engenharia eletrônica Swarm robotics Electronic engineering Swarm intelligence Inteligência artificial Robótica de enxame Distributed computing Inteligência de enxame Computational algorithms Cluster Alocação dinâmica de tarefas Algoritmos computacionais ENGENHARIAS [CNPQ] Dynamic task allocation Computação distribuída |
| Zdroj: | Biblioteca Digital de Teses e Dissertações da UERJ Universidade do Estado do Rio de Janeiro (UERJ) instacron:UERJ |
| Popis: | Submitted by Boris Flegr (boris@uerj.br) on 2021-01-06T19:19:55Z No. of bitstreams: 1 Luigi Maciel Ribeiro.pdf: 3722818 bytes, checksum: 4e20be50c3403c7f97c335e29267d008 (MD5) Made available in DSpace on 2021-01-06T19:19:55Z (GMT). No. of bitstreams: 1 Luigi Maciel Ribeiro.pdf: 3722818 bytes, checksum: 4e20be50c3403c7f97c335e29267d008 (MD5) Previous issue date: 2018-05-30 The interest of the academic community in solving highly complex problems has been growing in recent years, putting an emphasis on the use of Swarm Intelligence. The Swarm Intelligence has a biological inspiration, proposed from the social observation of self-organizing species such as ants, bees and termites. Cooperation is the central idea, it allows the solution of complex problems with the coordinated accomplishment of small tasks, which together lead to a common goal. This coordination is only possible with an efficient Task Allocation. The allocation should be dynamic, as it must react to the problem and swarm changes, and also to have a distributed and stochastic solution, respecting the biological collective behavior that inspired the Swarm Intelligence. Particle swarm optimization (PSO) is an optimization algorithm that meets these requirements by managing a set of particles that navigate in a limited search space where the particle's current position is a possible solution. The position of each particle is adaptive in function of its own experience and the experience of the others. Inspired by the PSO, the Alocação Dinâmica de Tarefas em Cluster (ADTC) algorithm was proposed. The algorithm ADTC assigns tasks to a group of robots in a totally distributed way, where each one will represent a particle and its position of the search space will represent a feasible allocation. Based on the PSO, the ADTC performs an oriented search of the space, using the same concept of adaptive speed. However, this process requires an intense exchange of information between robots, and can hinder the task allocation for large swarms. In this dissertation, we propose the use of the cluster communication topology, capable of optimizing the communication process between robots, making the allocation of tasks of large swarms. The results obtained using the cluster topology are compared to those obtained with the complete mesh topology, showing the impact of the communication optimization on the performance of the dynamic allocation of tasks. On average, the results show an optimization of 30%. O interesse da comunidade acadêmica, em solucionar problemas de alta complexidade, vem crescendo nos últimos anos, intensificando a utilização da Inteligência de Enxame. A inteligência de Enxame possui inspiração biológica, proposta a partir da observação social de espécies auto-organizáveis, como formigas, abelhas, cupins, entre outros. A cooperação é a ideia central, pois possibilita a solução de problemas complexos com a realização coordenada de pequenas tarefas, que somadas levam a um objetivo comum. Essa coordenação só é possível com uma Alocação de Tarefas eficiente. A alocação deverá ser dinâmica, pois deve reagir às alterações do problema e do enxame, e também possuir uma solução distribuída e estocástica, respeitando o comportamento coletivo biológico que inspirou a Inteligência de Enxame. Otimização por enxame de partículas Particle swarm optimization - PSO) é um algoritmo de otimização que atende à esses requisitos, gerenciando um grupo de partículas que navegam em um espaço de busca limitado, onde a posição atual da partícula é uma possível solução. A posição de cada partícula é adaptativa em função da sua própria experiência e da experiência das demais. Com inspiração no PSO, o algoritmo Alocação Dinâmica de Tarefas em Cluster (ADTC) foi proposto. O algoritmo ADTC realiza a alocação de tarefas para um grupo de robôs de forma totalmente distribuída, onde cada um dos robôs representará uma partícula e a sua posição no espaço de busca representará uma alocação factível. Baseado no PSO, o ADTC realiza uma busca orientada do espaço, utilizando o mesmo conceito de velocidade adaptativa. Porém, esse processo exige uma intensa troca de informações entre os robôs, podendo ser um empecilho para grandes enxames. Nesta dissertação é proposta a utilização da topologia de comunicação em cluster, capaz de otimizar processos de comunicação, viabilizando a alocação de tarefas de grandes enxames. Os resultados obtidos com a topologia em cluster são comparados com os obtidos com a topologia em malha completa, mostrando o impacto da otimização da comunicação no desempenho da alocação dinâmica de tarefas. Na média, os resultados apresentam uma otimização de 30%. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|