Complete Distributed Coverage of Rectilinear Environments

Abstract

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 ro­ bots this ability. DCr is applicable to teams of square robots operating in finite rectilinear environments and executes independently on each robot in the team, di­ recting the individual robots so as to cooperatively cover their shared environment relying only on intrinsic con­ tact sensing to detect boundaries. DCr exploits the structure of this environment along with reliable posi­ tion sensing to become the first algorithm capable of generating cooperative coverage without the use of ei­ ther a central controller or knowledge of the robots’ initial positions. We present a completeness proof of DCr , which shows that the team of robots will always completely cover their environment. DCr has also been implemented successfully in simulation, and future ex­ tensions are presented which will enable instantiation on a real-world system.