Swarm ant robotics for a dynamic cleaning problem-analytic lower bounds and impossibility results

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 [1]). 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. Several impossibility results for the problem are shown. In addition, a cleaning protocol for the problem is presented, as well as an analytic lower bound on its performance. ©2009 IEEE.