Multi-robot exploration with constrained communication

Abstract

Abstract : Over the last two decades, several methods for exploration with Multi-Robot Systems (MRS) have been proposed, most of them based on the allocation of frontiers (exploration targets) and typically applying local optimization policies. However, communication issues have usually been neglected. This thesis investigates multi-robot exploration by considering that robots have limited communication radius. Two methods, one based on a flat network architecture (DSM) and another based on a hierarchical architecture (HSM), were proposed to share map information. While DSM considers a propagation scheme to share information and synchronize the map of robots, HSM organizes robots in a hierarchical architecture where some robots act as leaders (clusterheads) and are responsible for synchronizing the maps of the robots in the network. Formal proof that both methods guarantee the synchronization of the map of all robots in a network is presented. In addition, experiments were conducted by considering systems with different number of robots, network topologies and different map's sizes. The results show that both methods are able to synchronize the map of the robots when they can lose communication links, but HKM usually presents smaller convergence time, number of exchanged messages and amount of transmitted data. We also propose Hierarchical K-Means (HKME), a method for multi-robot coordination in exploration tasks that handles communication problems, such as link losses. To handle communication among robots, HKME arranges them into clusters and elects leaders for each. Clusters evolve dynamically as robots lose or establish communication with their peers. HKME uses HSM to guarantee that the map of the robots are synchronized and also uses the hierarchical organization of the robots to coordinate them in order to minimize the variance of the time at which they reach all regions of the workspace, while balancing their workload and decreasing the exploration time. Experiments were conducted by considering different types of workspace and communication radius. The results show that HKME behaves like a centralized algorithm when communication is granted, while being able to withstand severe degradation in communication radius.<br>

Ao longo das últimas décadas, vários métodos de exploração com os Sistemas Multi-robôs (SMR) têm sido propostos, a maioria deles com base na alocação de fronteiras (alvos de exploração) e normalmente aplicando políticas de otimização locais. No entanto, os problemas de comunicação têm geralmente sido negligenciados. Esta tese investiga a exploração multi-robô, considerando que os robôs têm raio de comunicação limitado. Dois métodos, um baseado em uma arquitetura de rede plana (DSM) e outro baseado em uma arquitetura hierárquica (HSM), foram propostos para compartilhar informações de mapa. Enquanto o DSM considera um esquema de propagação para compartilhar informações e sincronizar o mapa dos robôs, o HSM organiza robôs em uma arquitetura hierárquica, onde alguns robôs atuam como líderes (clusterheads) e são responsáveis por sincronizar os mapas dos robôs na rede. A prova formal de que ambos os métodos garantem a sincronização do mapa de todos os robôs na rede é apresentada. Além disso, experimentos foram conduzidos considerando sistemas com diferentes números de robôs, topologias de rede e tamanhos de mapa. Os resultados mostram que ambos os métodos são capazes de sincronizar o mapa dos robôs quando eles podem perder links de comunicação, mas o HKM geralmente apresenta menor tempo de convergência, o número de mensagens trocadas e a quantidade de dados transmitidos. Propomos também Hierarchical K-Means (HKME), um método de coordenação multi-robô em tarefas de exploração que lida com problemas de comunicação, tais como perdas de links. Para lidar com a comunicação entre robôs, o HKME os organiza em clusters e elege os líderes de cada um. Clusters evoluem dinamicamente a medida que os robôs perdem ou estabelecem links de comunicação. O HKME usa o HSM para garantir que o mapa dos robôs se mantenham sincronizados e também usa a organização hierárquica dos robôs para coordená-los, a fim de minimizar a variância do momento em que eles atinjem todas as regiões do espaço de trabalho, ao mesmo tempo que equilibra a carga de trabalho e diminui o tempo de exploração. Experimentos foram realizadas considerando diferentes tipos de espaço de trabalho e raios de comunicação. Os resultados mostram que o HKME comporta-se como um algoritmo centralizada quando a comunicação é garantida, sendo capaz de lidar com uma degradação severa no raio de comunicação.