Distributed coverage of rectilinear environments

This thesis addresses a specific problem of distributed robotics---namely, the problem of using a team of identical robots to autonomously and cooperatively generate a map of their shared workspace without the use of a central controller. The problem is posed as one of sensor-based coverage, in which a complete exploration of the environment is produced without any initial information. The system that inspired this work, the minifactory, is an automated assembly system that requires the ability for complete self-calibration, a task that can be posed as sensor-based coverage. The problem addressed here is therefore specified for a class of robots similar to the minifactory's couriers---rectangular robots with intrinsic contact sensing operating in a shared rectilinear environment.; To approach this problem, first a novel sensor-based coverage algorithm for a single robot, CCR, is presented. CCR uses a reactive construction and no time-based history to perform coverage, enabling the straightforward addition of cooperation. A proof is then presented which shows that a robot under the direction of CCR will reach every point in any finite rectilinear environment with no initial knowledge. A cooperative algorithm DCR is then presented which runs independently on each robot in a team with a shared workspace. DCR uses a modified version of CCR to produce coverage, while two additional algorithmic components allow the robots to cooperate at run-time to determine their relative location in the environment and improve the efficiency of the coverage process. A proof for DCR is also presented which shows that each point in the environment will be reached by at least one robot, and that each robot will end up with a complete map to which it has registered itself. Extensions to DCR are presented which allow for the handling of collisions between robots, some position uncertainty in the robots' sensing, and teams of different sized robots. Finally, some directions for future work are presented, including the extension of CCR and DCR to different robot systems and the generalization of the proof of DCR to a class of cooperative robotic algorithms.