Technical Report PHD-2010-01

Title: Multi Agent Robotics In Dynamic Environments
Authors: Yaniv Altshuler
Supervisors: Alfred M. Bruckstein and Israel A. Wagner
Abstract: In this work we examine the use of a decentralized group of extremely simple robotic agents for cooperatively accomplishing missions of global properties. We show that using only local interactions, such simple robots can cope with the lack of a central supervisor, communication resources and large memory resources. Using redundancy, the systems also achieve fault tolerance (required as the robots' simplicity might also imply low hardware reliability, resulting in agents malfunctions).

We examine problems in which the agents must work in dynamic environments - where changes may take place, that are independent and certainly not caused by the agents' activity.

The main problem that is discussed in this work is the Cooperative Cleaners problem - a problem assuming a regular grid of connected rooms (pixels), part of which are "dirty", the "dirty" pixels forming a connected region of the grid. On this dirty grid region several agents move, each having the ability to "clean" the place (the "room", "tile", "pixel" or "square") it is located in.

A cleaning protocol for a decentralized group of robotic agents is presented, aiming for cooperatively cleaning a given (yet unknown) dirty region. The protocol's performance, in terms of cleaning time is analyzed, and later on also demonstrated experimentally.

Later on, the dynamic generalization of this problem is discussed, in which a deterministic evolution of the environment in assumed, simulating a spreading contamination (or spreading fire). Once again, the goal of the agents is to clean the spreading contamination in as little time as possible. After formally defining the problem, analytic lower bounds for the problem (namely, for the cleaning time of any cleaning protocol) are presented, followed by an impossibility result. Later on it is suggested that the same cleaning protocol which was presented for the static variant of the problem, can be used for the dynamic generalization as well. A variety of experimental results are presented, and compared to the analytic lower bounds.

The protocol's performance in the dynamic environment is then analyzed, resulting in several upper bounds over its cleaning time.

In addition, we discuss the Cooperative Hunters problem, in which a group of unmanned air vehicles (UAVs) should scan a pre-defined rectangular area for a group (of unknown size) of evading targets, of superior sensors and communication resources.

This problem, rooting back to World War II, is analyzed, and an scanning algorithm for it is presented. This algorithm is then shown to be very close to the theoretical optimal algorithm.

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 PHD technical reports of 2010
To the main CS technical reports page

Computer science department, Technion