Optimal deterministic protocols for mobile robots on a grid.
This paper studies a system of m robots operating in a set of n work locations connected by aisles in a nxn grid, where mn.Form time to the robots need to move along the aisles, in order to visit disjoint sets of locations. The movement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse a grid edge at the same time; (2) a robot's sensory capability is limited to detecting the presence of another robot at a neighboring node. We present a deterministic protocol that, for any small constant e > 0, allows m(1-e)n targets and no target is visited by more than one robot. We also prove a lower bound showing that our protocols were known only for m n, while for general m n only a suboptimal randomized protocols were known.
Introduction
A Multi Robot Grid system (shortly, MRG) consists of m robots that operate in a set of
locations connected by aisles in a
n \Theta
grid [ST95]. At any time, the
robots are located at distinct grid nodes, and from time to time each robot is given a set of
work locations (targets) to be visited. The target sets are disjoint and no particular order
is prescribed for visiting the targets in each set. Moreover, robots may end up at arbitrary
locations, once their visits are completed. We may regard the system as representing a
warehouse or a tertiary storage (e.g., tape) system, where robots are employed to gather
or redistribute items. For simplicity, we assume that the system is synchronous, that is,
all robots are provided with identical clocks. Control is distributed in the sense that each
robot's moves are scheduled locally by a processor embedded in the robot. Our goal is
to design an efficient distributed on-line protocol that every robot must follow in order to
visit the assigned targets while avoiding deadlocks and conflicts with other robots. More
specifically, the protocol must comply with the following rules:
ffl At any time all the robots reside in the grid, i.e., no robot can leave the grid or enter
from outside.
ffl No two robots can occupy a grid node or traverse a grid edge at the same time.
ffl A robot cannot exchange information with other robots directly. However, each
robot is equipped with a short-range sensor that is able to detect the presence of
other robots occupying nodes at (Manhattan) distance one from its current location.
ffl In one time unit, a robot can perform a constant amount of internal computation,
read the output of its short-range sensor, and decide whether to remain at the current
grid node, or to move to a neighboring node.
In an MRG(n; m; d) problem, each of m  n robots in an MRG system is required to
visit (at most) d  n targets, with no grid node being target for more than one robot. For
the sake of simplicity, we assume that n is a power of 4 so that the grid can be recursively
decomposed into subgrids whose size is still a power of 4. The general case of n being any
even power can be handled with minor modifications.
1.1 Related Work
The MRG(n; m; d) problem was originally introduced in [ST95] as a practical case study
within the general quest for social laws to coordinate agents sharing a common environment
in a distributed rather than centralized fashion. While central control relies on a single
arbiter that regulates all possible interactions among the agents, distributed control is
based on a set local rules which must be complied with in order to avoid conflicts. The
need for distributed control stems from a number of shortcomings which may limit the
applicability of a central protocol, such as the need of reprogramming the system when
the set of agents changes over time, or the overhead in computation and communication
introduced by the arbiter. In fact, a distributed protocol may exploit better the intrinsic
parallelism of the problem, since each agent can be programmed independently of the
others to follow the common set of rules. In order to be efficient, a distributed protocol
must require a minimal amount of communication to regulate the interaction between the
agents. Hence, the protocol must be based on simple rules that can be applied locally and
quickly.
Although the MRG(n; m; d) problem entails routing robots on a two-dimensional grid, it
exhibits, however, some fundamental differences from classical message routing problems.
The nodes of a network used to exchange messages are typically processing units able
to compute, maintain a local status and, in many cases, temporarily buffer messages in
transit. In contrast, in an MRG system the grid nodes are passive entities with no status or
computing power, and robots, which are the active agents in the system, must orchestrate
their movements solely based on their processing and sensory capabilities. Moreover, in
message routing, packets travelling through the network can be destroyed and replicated
as long as each message is eventually delivered to its destination(s), while this is clearly
not admissible when dealing with robots.
For the above reasons, as was also observed in [PU96], none of the many message routing
protocols known in the literature appears to be directly applicable to the MRG(n; m; d)
problem (see [Lei92] and [Sib95] for comprehensive surveys of grid protocols). Even hot-potato
protocols, which require only very simple operations at the nodes and do not employ
internal buffers, are not directly applicable since they work under the assumption that in
one time unit a node may receive a packet from each neighbor, manipulate the information
carried by the packet headers and redistribute the packets, suitably permuted, to the
neighbors (e.g., see [NS95]). Nevertheless, we will show in this paper that techniques
employed in message routing can be suitably, yet not trivially, adapted to devise efficient
solutions for the MRG(n; m; d) problem.
Any instance of the MRG(n; m; d) problem can be trivially completed in
by letting the robots circulate along a directed Hamiltonian cycle traversing all the grid
nodes. In fact, Preminger and Upfal [PU96] proved that any deterministic protocol in
which robots are completely blind (i.e., a robot cannot detect the presence of other robots
at any distance)
requires\Omega (n) time, thus implying the optimality of the trivial strategy
in this case.
If the robots are not
n) time is necessary in the worst case due to the grid
diameter. Clearly, a single robot with a single destination (MRG(n; 1; 1) problem) can
achieve this bound by simply traversing a shortest path from its source to its target. For a
larger number m of robots and a single destination per robot (MRG(n; m; 1) problem) two
optimal \Theta (
n)-time protocols are presented in [ST92] and [ST95] for two special cases:
The first protocol is designed for m  n 1=4 robots, while the second one works for m
robots, as long as they initially reside in distinct columns.
The only known protocol that deals with an arbitrary number of m  n robots and
a single destination is given in [PU96]. The algorithm is randomized and solves any
problem in suboptimal O (
log n) time, with high probability. However,
the algorithm works under a relaxed set of rules. Specifically, it assumes that a robot's
short-range sensor is able to detect the presence of other robots at distance at most two,
that a robot may initially stay outside the grid for an arbitrary amount of time, and that
robots disappear from the grid as soon as they have visited their target. No deterministic
protocol that takes o(n) time and works under the stricter rules described in this paper is
known for the MRG(n; m; 1) problem.
For the case of d ? 1 targets, one could repeat the single-target protocol d times.
However, as we will show in the paper, this strategy does not achieve optimal performance.
To the best of our knowledge, no specific algorithm for the case of d ? 1 targets has been
developed so far.
1.2 Our Results
We devise a simple and general protocol for the MRG(n; m; 1) problem, with m  n=4,
which attains optimal \Theta (
n) time. The algorithm implements a routing strategy in a
way that fully complies with the constraints imposed by an MRG system. Our protocol
improves upon the work of [PU96] in several directions. First, the protocol is deterministic,
hence it provides a worst-case guarantee on performance. Second, it achieves optimality in
the general case, thus reducing the running time of [PU96] by an O (log n) factor. Third,
it works in a weaker model in which the robots reside in the grid all the time and their
sensors can detect other robots at distance one.
Next, we consider the case of d ? 1 targets. If we put a constraint on the order of the
visits that fixes a priori the sequence of targets to reach for each robot, a simple argument
based on diameter considerations suffices to prove that any protocol for the problem re-
quires\Omega (d
n) time, in the worst case. Consequently, applying our optimal MRG(n; m; 1)
protocol d times yields an optimal \Theta (d p
n)-time general solution in this case. However, if
the robots can arbitrarily rearrange the order of their targets, the latter approach becomes
suboptimal. Indeed, we prove
an\Omega ip
lower bound to the MRG(n; m; d) problem and
provide an optimal \Theta
ip
-time protocol that matches the lower bound for any d  n
and m  is an arbitrarily fixed constant. Ours is the first
nontrivial solution to the most general case of the MRG problem.
It must be remarked that our protocols require a common clock governing all robots'
movements, while the results in [PU96] and [ST95] can be adapted to hold under a slightly
weaker notion of synchronicity.
The paper is organized as follows. Section 2 describes an optimal deterministic protocol
for the MRG(n; m; 1) problem under the assumption m  n=4. In Section 3 the protocol is
extended to handle the more general MRG(n; m; d) problem with d  n and
The section also proves the lower bound showing the optimality of the extended protocol.
Some final conclusions and open problems are drawn in Section 4.
2 The Case of Single Targets
Consider an arbitrary instance of the MRG(n; m; 1) problem, for m  n=4. The basic idea
behind our protocol is to perform the routing through sorting, which is a typical strategy
employed in the context of packet routing. However, we need to develop specific primitives
in order to implement such a strategy under the restrictive rules of an MRG system. In
the following, we assume that at any time each robot knows the coordinates of its current
location.
Let us consider the grid as partitioned into n=4 2 \Theta 2 subgrids, which we call tiles. The
protocol has a simple high-level structure consisting of the four phases outlined below:
ffl Phase I - Balancing: The robots relocate in the grid so that each robot ends up in
the top-left node of a distinct tile.
ffl Phase II - Sorting-by-Row: The robots sort themselves by target row. The sorted
sequence of robots is arranged on the grid (one robot per tile) according to the Peano
indexing [Mor66] shown pictorially in Figure 1 and described mathematically later.
In other words, at the end of the sorting, the i-th robot in the sorted order occupies
the top-left corner of the tile of Peano index i.
ffl Phase III - Permuting: The sorted sequence of robots permutes from the Peano
indexing to the row-major indexing.
ffl Phase IV - Routing: The robots first circulate within columns of tiles to reach
the rows containing their targets. Then, they circulate around the rows to visit the
targets.
Before describing the four phases in more detail, we show how to perform some basic
primitives in an MRG system which will be needed to implement the above phases.
Pack Given q  t robots on a t-node linear array, pack them into q consecutive nodes at
one end of the array.
Solution: Each robot repeatedly crosses an edge towards the designated end whenever its
short-range sensor detects that the node across the edge is empty. No collisions arise in
this way. Moreover, a simple argument shows that after t time steps all the robots have
completed the packing. 2
Count Given q  t robots on a t-node linear array, make q known to each robot.
Solution: The robots first pack at one end of the array and then at the other. A robot
that ends up at the i-th location from one end and at the j-th location from the other,
sets primitive requires no more than 2t steps. 2
Compare-Swap Given a tile with two robots in it, sort the two robots so that the one
associated with the smaller target row goes to the top left corner, while the other goes to
the bottom left corner.
Solution: Suppose that the two robots start at the top and bottom left corners of the
tile. The robots execute a number of rounds until they "learn" their relative order in the
sorted sequence. Specifically, in the i-th round, the robots "implicitly compare" the i-th
most significant bit of the binary representation of their respective target row as follows.
A robot positions itself at the left corner (in the same row) of the tile if its bit is 0, while
it positions itself at the right corner if its bit is 1. Then each robot can infer the other
robot's bit by simply checking for its presence in the same column. The first time that
the robots find different bits, the robot whose bit is 0 moves to the top left corner, while
the other moves to the bottom left corner, and the algorithm ends. If the robots have the
same target row (i.e., all bits are equal) they stay in their starting positions. Overall, the
computation takes no more than log n steps. 2
In the following subsections, we describe the four phases of our protocol in more detail.
2.1 Phase I: Balancing
In this phase, the m  n=4 robots start at arbitrary positions in the grid and must
distribute themselves among the n=4 tiles so that each tile contains at most one robot in
its top-left node. This is accomplished in log steps, numbered from 0 to
log according to the following inductive scheme. At the beginning of Step i, with i
even, the robots are already distributed evenly among square subgrids of size
by induction. (This clearly holds for During the step, the robots work independently
within each square subgrid, and partition themselves evenly among rectangular subgrids
of size
n=2 i+2 . Analogously, in Step i with i odd, the robots work independently
within each rectangular subgrid of size
partition themselves evenly
among square subgrids of size
. Clearly, at the end of Step log
the robots are evenly partitioned among the subgrids of size 2 \Theta 2 (the tiles), with at most
one robot per tile. At this point, each robot moves to the top-left corner of its tile.
We now describe the implementation of Step i, with i odd (the implementation of a
balancing step of even index requires only minor modifications). Consider an arbitrary
t \Theta t=2 rectangular subgrid, with
suppose that there are p robots in
the subgrid. Let the rows (resp., columns) of the subgrid be numbered from 1 to t (resp.,
t=2). At the end of the step we want to have bp=2c robots in the upper half (top t=2 rows)
and the remaining dp=2e in the lower half (bottom t=2 rows) of the subgrid. This is done
through the following substeps:
(1) The robots in each row pack towards the left.
(2) The robots in each column pack towards the bottom.
Comment: After this step, the robots form a "staircase" descending from northwest
to southeast in the subgrid.
(3) In each column k ! t=2, each robot determines the number of robots in the column.
If this number is odd, the topmost robot (referred to as leftover) moves to the top
of the column.
leftovers pack towards the right of the topmost row. Then they move down along
column t=2 towards the bottom. Then, in column t=2, each robot determines the
number of robots in the column.
Comment: If p  t 2 =4 (which is always the case) then there is enough room in column
t=2 to hold all leftovers.
(5) For every column k, let x be number of robots in the column after Step 4. (Note
that x may be odd only for t=2, the robots pack around the column
center, i.e., on rows t=2, the robots
pack so that bx=2c of them end up in the upper half and the remaining dx=2e end
up in the lower half.
Lemma 1 Phase I takes O (
n) time.
Proof: The correctness of the above strategy is immediate. The resulting time bound is a
geometrically decreasing sum, whose i-th term is the cost O
of balancing step i,
which is implemented in terms of the Pack and Count primitives presented before. 2
2.2 Phase II: Sorting-by-Row
At the end of the balancing phase, the robots are spread among the grid nodes in such
a way that there is at most one robot in each tile, parked in the tile's top-left corner.
The robots will now sort themselves according to their target row, with ties broken ar-
bitrarily. The sorting algorithm relies upon a grid implementation of Batcher's bitonic
sorting algorithm [Bat68] for sequences of size n=4 or smaller. We recall that Batcher's
algorithm is structured as a cascade of log merging stages. At the beginning of the
i-th merging stage, 1  i  log the robots are partitioned into (n=4)=2
subsequences each of size 2 i\Gamma1 . Then, pairs of subsequences are merged independently so
that, at the end of the stage, there are (n=4)=2 i sorted subsequences each of size 2 i . In
turn, the i-th merging stage is made of a sequence of i steps, called (i; j)-compare-swap for
specifically, an (i; j)-compare-swap step compares and swaps
pairs of elements at distance 2 j in each subsequence (the direction of the compare/swap
operator is fixed a priori and depends on the values of i and j).
In order to efficiently implement Batcher's algorithm on the grid, we number the n=4
tiles according to the Peano indexing , which can be defined as follows (see Figure 1).
Split the set of indices I four equally sized subsets of consecutive
indices I
I 1g. Similarly, split the grid into four quadrants of n=16 tiles each
and assign the four subsets of indices to the four quadrants, namely, H t'
, and
H br , where t stands for "top," b for "bottom," ' for "left," and r for "right." Assign the set
of indices I 0 to H t' , I 1 to H b' , I 2 to H tr and I 3 to H br . Then proceed recursively within the
quadrants until quadrants of one tile each are reached. An easy argument shows that two
tiles with indices h and h \Phi 2 j in the Peano indexing, where \Phi denotes bitwise exclusive-or,
lie on the same row or column of tiles (depending on the parity of j) at distance O
ip
from each other.
An (i; j)-compare-swap step can be performed as follows. Let k denote any integer in
binary representation has 0 in position j. The following substeps

Figure

1: The 64 tiles of a 16 \Theta 16 grid ordered according to the Peano indexing. Each
square represents a tile with 2 \Theta 2 grid nodes and contains one robot at most, after the
balancing phase.
are executed in parallel for all such values of k:
(1) The robot residing in tile k in the Peano indexing (if any) moves to tile k.
(2) The robots in tile k execute the Compare-Swap primitive according to their target
row, with ties being broken arbitrarily. When only one robot is in the tile, it moves
directly to the tile's top left corner.
(3) The robot with the larger or smaller target (if any) moves to tile k depending
on the direction of the (i; j)-compare-swap operator.
The routing implied by Step 1 above is easily performed by the robots without collisions.
In particular, when j is odd, the robot in tile k first moves to the bottom-left corner
of its tile, and then moves left until it reaches the bottom-left corner of tile k (which is
on the same row as tile k our numbering). When j is even, the robot in tile
first moves to the top-right corner of the tile and then moves upwards along the
column, until it reaches the bottom-right corner of tile k. From there, it then positions
itself at the bottom-left of the tile. Step 3 can be accomplished analogously. Thus, Steps 1
and 3 require O
ip
time overall. By using the Compare-Swap primitive discussed before,
Step 2 requires O (log n) time.
Phase II takes O (
n) time.
Proof: The i-th merging stage of the sorting algorithm, 1  i  log consists of a
sequence of (i; j)-compare-swap steps, for As an (i; j)-compare-swap
step takes O
ip
time, the total running time of the algorithm is
log n\Gamma2
O
ip
O
:2.3 Phase III: Permuting
After the sorting phase, the robots reside in distinct tiles, sorted by target row according
to the Peano indexing. In Phase III, the robots permute in such a way that the sorted
sequence is rearranged according to the row-major indexing. Let us call t-column (resp., t-
row) a column (resp., row) of tiles. The permutation is executed according to the following
recursive protocol. If permutation is trivial. Consider
(1) Each robot in H tr swaps positions with the one occupying the corresponding position
in H b'
(2) Within each quadrant, the sorted subsequence of robots recursively permutes from
Peano to row-major indexing.
(3) Within each quadrant, the robots permute so that those in odd t-rows pack to the
top, while those in even t-rows pack to the bottom of the quadrant.
Each robot in the lower half of H t'
positions with the one occupying
the corresponding position in the top half of H tr , (resp., H br ).
The correctness of the permutation protocol is easily established by induction. Below,
we give a pictorial illustration of the steps for robots:
Initial configuration
43
26 28 50 52 58
22
After Step 1
28
43
34 36 42 44 50 52 58
After Step 2
28
After Step 3
28
After Step 4
26
Lemma 3 Phase III takes O (
n) time.
Proof: The movements of robots implied by Step 1, Step 3 and Step 4 can be executed
in a conflict-free fashion in O (
n) time as one robot at most is in each tile. Since the
recursive Step 2 is executed in parallel and independently within subgrids of geometrically
decreasing side, we conclude that the overall permutation time is also O (
n). 2
2.4 Phase IV: Routing
The routing phase starts with the m robots sorted by target row and occupying the first
tiles in the row-major indexing, with at most one robot per tile (in the tile's top-left
corner). We number the t-columns (resp., the t-rows) from 1 to
n=2. Note that, due to
sorting, each t-column holds no more than two robots with targets in the same row. The
routing is performed by first moving the robots to their target row and then to their final
target. This is accomplished in parallel as follows:
(1) For 1  i
n=2, the robot residing in t-column 2i and t-row j
moves to the top-right corner of the tile in t-column 2i \Gamma 1 and t-row j.
Comment: After this step, in any odd-numbered t-column there can be up to four
robots destined for the same row, while the even-numbered t-columns are empty.
(2) The robots in each odd-numbered t-column circulate along a directed Hamiltonian
cycle traversing all of the nodes in the t-column. When a robot traveling on the right
side of the t-column reaches its target row, it attempts to shift right to the adjacent
tile and then moves to the rightmost unoccupied node in such tile.
Comment: Within an odd-numbered t-column, no more than two robots with the
same target row are able to move to the adjacent t-column.
(3) The robots in each t-row circulate along a directed Hamiltonian cycle traversing all
the nodes in the t-row, therefore visiting their target locations.
(4) All the robots go back to the t-columns they occupied at the end of Step 1.
Steps 2-3 are repeated to deliver the robots that have not visited their targets yet.
To this end, the robots that have already completed their task will not attempt to
shift right during Step 2.
Comment: All robots that have not visited their targets at the beginning of Step 5
are now able to do so.
Lemma 4 Phase IV takes O ( p
n) time.
Proof: Steps 1-3 require O (
n) time altogether and are executed at most twice each (due
to Step 5). Step 4 can be executed as follows. In each odd-numbered t-column, the robots
in each row pack to the left. Then, robots in each even-numbered t-column circulate along
a directed Hamiltonian cycle traversing all the nodes in the t-column, and when a robot
sees an empty spot in the adjacent t-column (to the left) it moves into such a spot packing
to the left. Thus, Step 4 requires O (
n) time. This implies that the whole routing phase
also takes O ( p
n) time. 2
The following theorem is an immediate consequence of Lemmas 1, 2, 3 and 4.
Theorem 1 Any instance of the MRG(m; n; 1) problem, with m  n=4, can be solved in
time O (
n) in the worst case.
The simple diameter-based argument shows that the running time stated in the above
theorem is optimal. Moreover, the result is easily extended to the case in which m 0  m
robots have one target to reach, while the remaining ones do not have any visit to
perform. It is sufficient to associate the latter robots with a fictitious destination whose
row is
n+1 and let them participate to the various phases of the protocol. Clearly, there
is no increase in the running time.
3 The Case of Multiple Targets
In this section we devise a protocol for the more general MRG(n; m; d) problem where each
of m robots needs to visit up to d grid nodes, with each grid node being visited by at most
one robot. The protocol is first presented for the case m  n=4, and then extended to
handle up to m  n(1 \Gamma ffl) robots, for any constant 0 arbitrarily fixed. Before
describing the protocols, we prove a lower bound on the running time of any protocol for
the MRG(n; m; d) problem. The lower bound will be employed later to show the optimality
of the proposed protocols.
Lemma 5 For every choice of integers n; m; d, with 1  m; d  n, there exists an instance
of the MRG(n; m; d) problem whose solution
time.
Proof: If n ! 4 or d ! 4, the bound follows from the diameter argument. Therefore, let
us examine the case n; d  4. Let n 0 ; d 0 be the largest powers of 4 such that n 0  n and
d. Note that n 0  n=4, d 0  d=4 and d 0  n 0 . Consider a square subgrid of n 0 nodes,
partitioned into d 0 square tiles of size
suppose that one of the m
robots has the d 0 centers of the tiles among its targets, where the center of a tile is the
node in the (
row and in the (
=2)-th column of the tile. In order to
visit its targets the robot must traverse at least
nodes in each of d
or more, for an overall time requirement
=\Omega ip
3.1 An Optimal Protocol for m  n=4
Consider an instance of the MRG(n; m; d) problem with d  n and m  n=4, and let
dc. The protocol is structured as a sequence of k stages of geometrically
increasing running time. For 0  i  k, in Stage i all robots having to visit at least 4 i and
less than 4 i+1 destinations, accomplish their task. We call such robots active in Stage i,
whereas the remaining robots are called inert in Stage i. Note that since all robots reside
on the grid at all times, the protocol must orchestrate the movement for both active and
inert robots in every stage.
Stage 0 and Stage 1 are executed by simply running the single-target protocol fifteen
times, one for every possible target of each robot active in these stages. Clearly, inert
robots will participate in the protocol by associating themselves to "fake" destinations, as
described at the end of Section 2.
In Stage i, 2  i  k, at most n=4 i robots are active. Let ffi i
regard the
grid as being conceptually partitioned into 4 square subgrids of ffi i nodes each, which
we refer to as ffi i -tiles. Observe that all robots active in this stage fit in one quadrant of a
-tile. Stage i is executed in two rounds. In the first round, the inert robots pack in the
lower half of the grid, while the active robots tour all
-tiles in the upper half of the grid,
stopping in each ffi i -tile for a time sufficient to visit all of their destinations in the tile, and
progressively accumulating in the first tile of the lower half as they complete their tour.
Clearly, different robots may stop in a ffi i
-tile for different amounts of time, depending on
the number of their targets in the tile. Similarly, in the second round the inert robots pack
in the upper half of the grid while the active robots visit their destinations in the lower
half.
We describe in detail the operations performed by the robots in the first round of
Stage i, omitting the description for the second round, which is virtually identical. For
denote the j-th
-tile based on a snake-like ordering of the
-tiles
which proceeds alternatively left-to-right and right-to-left. Note that the ffi i -tiles in the
upper half of the grid are those of indices j  4
(1) The robots relocate in the grid so that all active robots end up in T 1 , while the inert
robots pack to tiles T j
, with 4
(2) The following sequence of substeps is repeated 17 \Delta 4 i\Gamma1 times, in parallel for each
(2.a) Each active robot with unvisited targets in T j visits one arbitrary such target.
(2.b) Robots that visited all of their targets in T j move to the top-left quadrant of
, while each robot that has still some unvisited targets in T j
moves to the
bottom-right quadrant of T j
(2.c) Robots that visited all of their targets in T j
move to the top-left quadrant of
T j+1 .
(2.d) (Only for The robots newly arrived in T j+1
pack to the
tile's bottom-right quadrant.
Lemma 6 For 2  i  k, Stage i is correct and is completed in O
ip
time.
Proof: Fix some i, 2  i  k, and consider the first round of Stage i (the argument for the
second round is identical). Note that, since i  2, the
comprise (n=4 nodes altogether, hence all inert robots fit in such
tiles. Step (1) is easily accomplished in O (
n) time through the balancing and sorting
techniques described in Section 2. Substep (2.a) is executed independently within
and entails one execution of the single-target protocol of Section 2, which takes O
time. Substeps (2.b), (2.c) and (2.d) can be executed through balancing and sorting within
-tiles and simple relocations between adjacent
-tiles, in time O
. The correctness
of these substeps follows from observing that at any time there cannot be more than
robots in each tile T j , with 1  j  4 and that at the beginning of Substep (2.d)
all robots in T 4 i\Gamma1 =2+1 are packed into the tile's bottom-right quadrant.
It remains to show that 17 \Delta 4 i\Gamma1 iterations of Step (2) are sufficient for each active robot
to visit its targets in the upper half of the grid. Consider an active robot and let d j
be the
number of its targets in the T j , for 1  j  4 =2. The robot will stay in such a tile for
iterations, hence the total number of iterations needed to visit all of its targets
is
Thus, Step (2) takes O
O
ip
time overall. Since the complexity of Step (2)
dominates that of Step (1), O
ip
is also the running time for the entire round. 2
We have:
Theorem 2 Any instance of the MRG(n; m; d) problem with m  n=4 and d  n can be
solved in optimal \Theta
ip
time, in the worst case.
Proof: Stage 0 and Stage 1 can be correctly performed in \Theta (
n) time by Theorem 1. The
correctness and complexity of Stage i, for 1  i  k, is established in Lemma 6. The
total cost is therefore O
O
ip
, and the optimality follows from
Lemma 5. 2
3.2 Extension to m
Let ffl be a fixed constant, consider an instance of the MRG(n; m; d) problem
with robots. Let c be the smallest power of 2 larger than or equal to 3=ffl, and
We regard the grid as conceptually partitioned into c 2 ffi-tiles of size ffi, with
each ffi-tile in turn divided into four (ffi=4)-tiles of size ffi=4. Let the (ffi=4)-tiles be numbered
from 1 to 4c 2 . In order to visit their targets the robots can employ the following protocol.
(1) The robots pack first towards the left in each row and then towards the bottom in
each column, thus ending in a "staircase" configuration descending from northwest
to southeast in the grid. Let A and B denote the two ffi-tiles at the northeast corner
of the grid (see Figure 2).
Comment: It will be shown that at the end of Step (1), A and B are empty.
(2) The following sequence of substeps is repeated for each index i, 1  i
(2.a) Let R i
denote the set of robots occupying the i-th (ffi=4)-tile. All robots move
within the grid so that robots of R i end up in ffi-tile A, while all other robots
return to their positions at the beginning of the step.

Figure

2: Configuration of robots after Step (1)
(2.b) For c 2 times do:
(2.b.1) The robots of R i visit their targets within the ffi-tile where they currently
reside, using the protocol from the previous subsection.
(2.b.2) The robots in each ffi-tile move to corresponding positions in the next ffi-tile,
according to some predetermined Hamiltonian circuit of the ffi-tiles.
(2.c) The robots of R i
move back to the grid nodes which they occupied at the
beginning of Substep (2.a).
The running time of the above protocol is analyzed in the following theorem.
Theorem 3 Any instance of the MRG(n; m; d) problem with m  n(1 \Gamma ffl) and d  n can
be solved in optimal \Theta
ip
time, in the worst case.
Proof: The row and column packings of Step (1) are easily accomplished in O (
n) time.
At the end Step (1) ffi-tiles A and B must be empty, or otherwise there would be more than
c
c
robots on the grid, which is impossible, since m  ffl). Consider an arbitrary iteration
of Step (2). By exploiting the empty ffi-tile B and repeatedly moving robots between
adjacent ffi-tiles, with each robot maintaining the same relative positions within the tile,
it is not difficult to orchestrate a relocation on the grid where ffi-tile A is always kept
empty, and for any fixed ffi-tile T , the robots initially in T end up in a tile adjacent to
A after O (
n) time. Based on this observation it is easily seen that Substep (2.a) can
be executed in time O ( p
n). By Theorem 2, Substep (2.b.1) takes O
ip
time. Since
an empty ffi-tile is always present in the grid during Step (2), it is easy for the robots to
execute Substep (2.b.2) in time O (
n). Since c
ip
time overall. Finally, Substep (2.c) mirrors Substep (2.a), hence it takes time O (
n) as
well. Thus, one iteration of Step (2) is completed in time O
ip
. The theorem follows
because Substeps (2.a) \Xi (2.c) are iterated 4c times. 2
Conclusions
We studied the complexity of moving a set of m robots with limited sensory capabilities,
in a multi robot grid system of size p
n \Theta
n. We provided an O
ip
deterministic
protocol that governs the movement of m  n(1 \Gamma ffl) robots, where each robot may visit
up to d distinct locations, but not two robots visit the same location. We also proved a
lower bound showing that the protocol is optimal. It would be interesting to extend the
protocol to handle any number of robots our protocol could be
employed to this end if the rules governing the system were relaxed so to allow a robot
to stay initially outside the grid for an arbitrary amount of time, and to disappear from
the grid as soon as it visits its targets. Finally, another interesting open problem concerns
the extension of the protocol to allow distinct robots to visit the same location. To the
best of our knowledge, no result is known for this setting, except for the trivial O (n)-time
protocol based on a Hamiltonian tour of the grid nodes.

Acknowledgments

The authors would like to thank Elena Lodi, Fabrizio Luccio, Linda
Pagli and Ugo Vaccaro for many interesting discussions and comments during the early
stages of this work, and the referees, who provided a number of useful suggestions.



--R

"Proceedings, AFIPS Spring Joint Computer Conference,"
"Introduction to Parallel Algorithms and Architectures: Arrays ffl Trees ffl Hypercubes,"
"A computer oriented geodetic data base and a new technique in file sequencing,"

"Proceedings, 5th Scandinavian Workshop on Algorithm Theory,"
"Overview of mesh results,"
"Artificial intelligence planning systems: Proceedings of the first international conference,"
On social laws for artificial agent societies: Off-line design
--TR
Introduction to parallel algorithms and architectures
On traffic laws for mobile robots
On social laws for artificial agent societies
Hot-Potato Algorithms for Permutation Routing
Safe and Efficient Traffic Laws for Mobile Robots

--CTR
Kieran T. Herley , Andrea Pietracaprina , Geppino Pucci, One-to-Many routing on the mesh, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.31-37, July 2001, Crete Island, Greece
social laws;multirobot grid system;computational agents;routing protocol