About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ICINCO 2006
Conference paper
Shape factor's effect on a dynamic cleaners swarm
Abstract
This work discusses an impossibility result for the Dynamic Cooperative Cleaners problem, and the relation of a specific geometric feature of the problem, known as the shape factor, to the efficiency of the operating swarm. The dynamic cooperative cleaners problem assumes a grid, having "contamination" points or tiles that form a connected region of the grid. Several agents move in this contaminated region, each having the ability to "clean" the place it is located in. The "contaminated" tiles expand deterministically, simulating a spreading of contamination, or fire. This problem, as well as a cooperative cleaning protocol for it and its analysis, were first introduced in [1]. The equivalence of this problem to another interesting multi agents problem was demonstrated in [2] by utilizing results relevant to the problem in order to design a cooperative hunting protocol for a swarm of UAVs. The results of [1] contain a generic lower bound for the cleaning time of any multi agents system which is designed to entirely clean an expanding contaminated area. This work enhances this bound, while discussing the effect of the region's shape factor (i.e. the ratio between the region's boundary and its area) and the swarm's cleaning efficiency. As a result, a tighter lower bound is produced, establishing a new and more generic impossibility result for the problem.