Zack J. Butler, Carnegie Mellon University, Pittsburgh, PA

Alfred A. Rizzi, Carnegie Mellon University, Pittsburgh, PA

Ralph L. Hollis, Carnegie Mellon University, Pittsburgh, PA

Complete coverage of an unknown environment is a valuable skill for a variety of robot tasks such as floor cleaning and mine detection. Additionally, for a team of robots, the ability to cooperatively perform such a task can significantly improve their efficiency. This paper presents a complete algorithm DC _R (distributed coverage of rectilinear environments) which gives robots this ability. DC _R is applicable to teams of square robots operating in finite rectilinear environments and executes independently on each robot in the team, directing the individual robots so as to cooperatively cover their shared environment relying only on intrinsic contact sensing to detect boundaries. DC _R exploits the structure of this environment along with reliable position sensing to become the first algorithm capable of generating cooperative coverage without the use of either a central controller or knowledge of the robots' initial positions. We present a completeness proof of DC _R, which shows that the team of robots will always completely cover their environment. DC _R has also been implemented successfully in simulation, and future extensions are presented which will enable instantiation on a real-world system.