Uniform dispersal of silent oblivious robots

Abstract

Consider the Filling problem, in which a set of mobile robots enter an unknown area and have to disperse in that area. The robots are homogeneous, anonymous, autonomous, have limited visibility radius, and do not use explicit communication. Moreover, these robots are oblivious, i.e. they do not have any bits of persistent memory. It is already known that these limitations prevent the creation of a deterministic algorithm to solve the Filling problem. In this paper an algorithm is presented, which is the first to overcome those limitations, to fill the area with oblivious robots. The algorithm is collision-free, has an expected termination time of O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) rounds, where n is the number of robots (and the number of cells in the area).