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.
