Swarm ant robotics for a dynamic cleaning problem — upper bounds

Abstract

Several recent works considered multi a(ge)nt robotics in static environments. In this work we examine ways of operating in dynamic environments, in which changes take place independently of the agents' activity. The work focuses on a dynamic variant of the known Cooperative Cleaners problem (described and analyzed by Wagner and Bruckstein in [12]). This problem assumes a grid, having “dirty” pixels or tiles, that form a connected region of the grid. Several agents move in this dirty region, each having the ability to “clean” the place it is located in. The dynamic variant of the problem involves a deterministic expansion of dirt in the environment, simulating a spreading of contamination, or fire. A cleaning protocol for the problem is presented, as well as a variety of analytic upper bounds on its performance.