Uniform Dispersal of Cheap Flying Robots

摘要

In the uniform dispersal problem (or filling problem) robots enter from one or multiple an entry point called the Doors, and have to disperse to cover the whole area. The robots are injected one-by-one into an unknown area. The robots are homogeneous, anonymous, autonomous, have limited visibility radius, limited persistent memory, and cannot use explicit communication. In a previous paper the authors investigated how 'weak' those robots can be in terms of hardware requirements and still be able to solve the problem in general areas. As the algorithm did not need any special requirement, in this paper the possibilities of usage in three-dimensional areas is investigated. The final goal is to solve the uniform dispersal with flying robots, e.g. drones or quadcopters, with constant amount of memory, minimal visibility, and no communication with linear runtime. In this paper an algorithm is presented which satisfies that criteria. Then it is also shown how it can be used in case of multiple entry points.