protocols, which were presented in previous works [1, 2].
1
Introduction
Several works considered multi agents robotics in static environments. The Dy-
namic Cooperative Cleaners problem however, is one of the rst problems in
which agents are required to work in dynamic environments an environment
in which changes may take place regardless of the agents activity. This problem
is a dynamic variant of the known Cooperative Cleaners problem, which is de-
scribed and analyzed in [1] (including a cleaning protocol called the CLEAN).
This problem assumes a grid, part of which is dirty, where the dirty part is
a connected region of the grid. On this dirty grid region several agents move,
each having the ability to clean the place (tile, pixel or square) it is located
in. The dynamic variant of the problem involves a deterministic evolution of
the environment, simulating a spreading contamination (or spreading re).
The Dynamic Cooperative Cleaners problem was rst introduced in [2],
which also included a cleaning protocol for the problem, called the SWEEP
protocol, as well as several analytic bounds for the time it takes agents which
use this protocol to clean the entire grid.
This work contains a discussion concerning several issues regarding the cor-
rectness of the SWEEP protocol and its bounds, as well as some clarications
regarding low level details of the SWEEP and CLEAN protocols. The work is
organized as follows section 2 contains a description of the dynamic cooper-
ative cleaners problem, while section 3 present the SWEEP cleaning protocol,
(as appears in [2]). The following sections contains the various issues to be
discussed. Section 5 examines the Danger Zones problem and present a criteria
for initial shapes, which must hold for the bounds of the cleaning protocol (de-
scribed in [2]) to hold. Sections 7 and 8 discuss delicate issues which concern
the low level operation of the agents employing the SWEEP protocol, which
1 must be taken care of, in order for the correct operation of the agents to be
guaranteed.
2
Dynamic Cooperative Cleaners Problem
Following is the description of the Dynamic Cooperative Cleaners problem, as
appears in [2].
Let us assume that the time is discrete. Let G be a two dimensional grid,
whose vertices have a binary property of contamination. Let cont
t
(v) state the
contamination state of the vertex v in time t, taking either the value on or
o . Let F
t
be the dirty sub-graph of G at time t, i.e. F
t
= {v G | cont
t
(v) =
on}. We assume that F
0
is a single connected component. Our algorithm will
preserve this property along its evolution. We assume that F
0
is also simply
connected.
Let A be a group of k agents that can move across the grid G (moving from
a vertex to its neighbor in one time step), such that at time t
0
all the agents
are located in F
0
. Each agent is equipped with a sensor capable of telling the
condition of the square it is currently located in, as well as the condition of the
squares in the 8N eighbors group of the this square. An agent is also aware
of other agents which are located in its square, and all the agents agree on a
common north. Each square can contain any number of agents simultaneously.
When an agent moves to a vertex v, it has the ability of causing cont(v) to
become o. The agents do not have any prior knowledge of the shape or size of
the sub-graph F
0
except that it is a single connected component.
Every d time steps the contamination spreads. That is, if t = nd for some
positive integer n, then (v F
t
, u 4N eighbors(v) : cont
t+1
(u) = on).
The agents goal is to clean G by eliminating the contamination entirely, so
that (t
success
: F
t
success
= ). In addition, it is desired that this t
success
will
be minimal.
We demand that there is no central control and that the system is fully de-
centralized (i.e. all agents are identical and there is no explicit communication
between agents).
3
Cleaning Protocol
For solving the Dynamic Cooperative Cleaners problem the SWEEP cleaning
protocol was suggested. The protocols can be described as follows. Generaliz-
ing an idea from computer graphics (presented in [3]), the connectivity of the
contaminated region is preserved by preventing the agents from cleaning crit-
ical points points which disconnect the graph of contaminated grid points
(see section 4). This ensures that the agents stop only upon completing their
mission. An important advantage of this approach, in addition to the simplicity
of the agents, is fault-tolerance even if almost all the agents cease to work
2 before completion, the remaining ones will eventually complete the mission, if
possible.
At each time step, each agent cleans its current location (assuming this is
not a critical point), and moves to its rightmost neighbor a local movement
rule, creating the eect of a clockwise traversal of the contaminated shape. As a
result, the agents peel layers from the shape, while preserving its connectivity,
until the shape is cleaned entirely.
4
Denitions
Let S
t
denote the size of the contaminated region F in time t, namely the
number of grid points (or squares) in F
t
.
The boundary of the contaminated region F is denoted as F , dened as
F = {(x, y) | (x, y) F (x, y) has an 8N eighbor in (G \ F )}.
Let d denote the number of time steps between two contamination spreads.
A path in F is dened to be a sequence (v
0
, v
1
, . . . , v
n
) of squares in F
such that every two consecutive squares are 4 Connected (meaning that the
Manhattan distance between them is 1). A length of a path is dened to be the
number of squares in it.
Let square v be called a critical point if v
1
, v
2
4N eighbors(v) where
all the paths connecting v
1
and v
2
, which are included in 8N eighbors(v), pass
through v.
The term rightmost means: starting from the previous boundary point
scan the neighbors of (x, y) in a clockwise order until you nd another boundary
point
The protocol is being used by the agent a
i
which in time t is located in (x, y).
The protocol, as appears in [2], is presented in gure 1.
The connectivity of the region yet to be cleaned, F , is preserved by allowing
an agent to clean only non-critical points. This guarantees both full cleanness
and agreement of completion (since having no contaminated neighbors implies
that F = ). Also, should several agents malfunction and halt, as long as there
are still functioning agents, the mission will still be handled, albeit slower.
Since we only allow agents to clean points which are in F , we guarantee
that no new holes will be created. The simple-connectivity of F , if such exists,
should thus be kept.
Note that when several agents are located in the same square, only the last
one who exits it cleans it, in order to prevent agents from being thrown out
of the contaminated region. This problem could also be solved by implement-
ing a contamination seeking mechanism (i.e. by applying methods such as
suggested in [4]). That solution, however, would have been far less elegant and
would have added additional diculties to the analysis process.
3 Protocol SWEEP(x, y) :
If (not is-critical(x, y)) and ((x, y) F ) and (there are
no other agents in (x, y)) then
Set cont(x, y) to o ;
/*Clean current position*/
If (x, y) has no contaminated neighbors then STOP;
If (there are no other agents in (x, y)) or (the agent has the
highest priority among agents in (x, y)) then
If �((x, y) F ) and in the previous time step the
agents square was in F then
/* Spread had occurred. Search for F */
Move in 90 counterclockwise to the previous
movement and skip the rest of the protocol;
If �((x, y) F ) and in the previous time step the
agents square was not in F then
/* Keep seeking F */
Move on the same direction as in the previous
movement and skip the rest of the protocol;
If (x, y) F then
Go to the rightmost neighbor of (x, y);
End SWEEP;
Function is-critical(x, y) :
If (x, y) has two contaminated squares in its 4N eighbors
which are not connected via a sequence of contaminated
squares from its 8N eighbors then
Return TRUE
Else
Return FALSE;
End is-critical;
Function priority(i) :
(x
0
, y
0
) =
i
(t 1);
(x
1
, y
1
) =
i
(t);
Return (2 � (x
0
x
1
) + (y
0
y
1
));
End priority;
Procedure INITIALIZE() :
Choose a starting point on F , p
0
;
Put all the agents in p
0
;
For (i = 1; i k; i + +) do
Start agent i according to the SWEEP protocol;
Wait 2 time steps;
End INITIALIZE;
Figure 1: The SWEEP cleaning protocol
4 5
Danger Zones
In the static cooperative cleaners problem, if F
0
was simply connected then
at any time t > 0, F
t
is known to be simply connected. While examining
the dynamic cooperative cleaners problem, and the cleaning protocols designed
for solving it, this is not necessarily the case. In this case, there arises the
question whether the original contaminated shape, F
0
, assumed to be simply
connected, can cease to be such, as a result of the cleaning of the agents and the
spreading of the contamination. If the above happens, we are also interested
in the consequences (i.e the eect it has on the cleaning time of the agents,
etc).
An example of such a case appears in gure 2.
Figure 2: An example of a danger zone. Notice that when the contamination
spreads, it might trap one or more agents inside a hole that will be created.
In order to tackle this issue, we rst assume that p
0
, the square in which the
agents are placed, is not positioned inside such danger zones this can be
assured by positioning p
0
on the bounding rectangle of F
0
.
Let T our
0
be a path, traversing F
0
.
For each non-critical points v
1
, v
2
two s