Decentralized Autonomous Navigation Strategies for Multi-Robot Search\n and Rescue

Abstract

In this report, we try to improve the performance of existing approaches for\nsearch operations in multi-robot context. We propose three novel algorithms\nthat are using a triangular grid pattern, i.e., robots certainly go through the\nvertices of a triangular grid during the search procedure. The main advantage\nof using a triangular grid pattern is that it is asymptotically optimal in\nterms of the minimum number of robots required for the complete coverage of an\narbitrary bounded area. We use a new topological map which is made and shared\nby robots during the search operation. We consider an area that is unknown to\nthe robots a priori with an arbitrary shape, containing some obstacles. Unlike\nmany current heuristic algorithms, we give mathematically proofs of convergence\nof the algorithms. The computer simulation results for the proposed algorithms\nare presented using a simulator of real robots and environment. We evaluate the\nperformance of the algorithms via experiments with real robots. We compare the\nperformance of our own algorithms with three existing algorithms from other\nresearchers. The results demonstrate the merits of our proposed solution. A\nfurther study on formation building with obstacle avoidance for a team of\nmobile robots is presented in this report. We propose a decentralized formation\nbuilding with obstacle avoidance algorithm for a group of mobile robots to move\nin a defined geometric configuration. Furthermore, we consider a more\ncomplicated formation problem with a group of anonymous robots; these robots\nare not aware of their position in the final configuration and need to reach a\nconsensus during the formation process. We propose a randomized algorithm for\nthe anonymous robots that achieves the convergence to a desired configuration\nwith probability 1. We also propose a novel obstacle avoidance rule, used in\nthe formation building algorithm.\n