Multi-agent Cooperative Cleaning of Expanding Domains

Abstract

Several recent works considered multi-a(ge)nt robotics in static environments. In this work we examine ways of operating in dynamic environments, where changes take place independently of the agents’ activity. The work focuses on a dynamic variant of the cooperative cleaners problem, a problem that requires several simple agents to clean a connected region of “dirty” pixels inZ 2 . A number of simple agents move in this dirty region, each having the ability to “clean” the place it is located in. Their goal is to jointly clean the given dirty region. The dynamic variant of the problem involves a deterministic expansion of dirt in the environment, simulating spreading of contamination or fire. Theoretical lower bounds for the problem are presented, as well as various impossibility results. A cleaning protocol for the problem is presented, and a wealth of experimental results testing its performance in comparison to the lower bounds. Several analytic upper bounds for the proposed protocol are also presented, accompanied with appropriate experimental results.