Technical Report MSC-2012-10

Title: Multi agents systems in dynamic stochastic environments
Authors: Eyal Regev
Supervisors: Alfred M.Bruckstein, Yaniv Altshuler
Abstract: In this work we study the strengths and limitations of collaborative teams of simple agents. In particular, we discuss the efficient use of “ant robots” for covering a connected region on the Z2 grid, whose area is unknown in advance and which expands stochastically. Specifically, we discuss the problem where an initial connected region of S0 boundary tiles expand outward with probability p at every time step. On this grid region a group of k limited and simple agents operate, in order to clean the unmapped and dynamically expanding region. A preliminary version of this problem was discussed in [4, 5], involving a deterministic expansion of a region in the grid. In this work we extend the model and examine cases where the spread of the region is done stochastically, where each tile has some probability p to expand, at every time step. For this extended model we show an analytic probabilistic lower bounds for the minimal number of agents and minimal time required to enable a collaborative coverage of the expanding region, regardless of the algorithm used and the robots hardware and software specifications. In addition, we present an impossibility result, for a variety of regions that would be impossible to completely clean, regardless of the algorithm used. Finally, we validate the analytic bounds using extensive empirical computer simulation results.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2012
To the main CS technical reports page

Computer science department, Technion