Limited communication, multi-robot team based coverage

Abstract

This paper presents an algorithm for the complete coverage of free space by a team of mobile robots. Our approach is based on a single robot coverage algorithm, which divides the target two-dimensional space into regions called cells, each of which can be covered with simple back-and-forth motions; the decomposition of free space in a collection of such cells is known as Boustrophedon decomposition. Single robot coverage is achieved by ensuring that the robot visits every cell. The new multi-robot coverage algorithm uses the same planar cell-based decomposition as the single robot approach, but provides extensions to handle how teams of robots cover a single cell and how teams are allocated among cells. This method allows planning to occur in a two-dimensional configuration space for a team of N robots. The robots operate under the restriction that communication between two robots is available only when they are within line of sight of each other.