The multi-robot coverage problem for optimal coordinated search with an unknown number of robots

This work presents a novel multi-robot coverage scheme for an unknown number of robots; it focuses on optimizing the number of robots and each path cost. Coverage problems traditionally deal with how a given number of robots covers the entire environment. This work, however, presents solutions of not only (i) how to cover the area (locations of interest) within the minimum time, but simultaneously (ii) how to find the optimal number of robots for a given time. Also, we consider the worst but realistic case of all robots starting at the same location instead of assuming randomly initialized positions. The minimum coverage time depends upon the number of robots used. Our research specifies (iii) how to find the minimum coverage time without knowing the number of robots. Finally, we present a deterministic coverage algorithm based on finding the shortest paths in order to optimize the number of robots and corresponding paths.

I. INTRODUCTION

This work investigates a multi-robot coverage problem, in which a group of an unknown number of robots needs to visit a series of search positions (locations of interest). In our work we assume that the robots aim to cover a given area in order to search for Objects Of Interest (OOIs). When considering multiple robots in real-world environments, we should manage the resources with respect to variables including the number of robots, required processing time, sensing ranges, among others. In addition, having a large number of robots is also not always a fast, effective, and efficient way to solve the problem. The Centibots [1] project that deals with approximately a hundred robots, has presented an exploration and mapping algorithm that uses one or multiple robots, but the problem of how many robots should be used at a given time is still an on-going challenge.