

Bristol Algorithms Days 2010 Feasibility Workshop
15  16 February 2010

Asynchronous rendezvous in 2Dspaces
Leszek Gasieniec
We study efficient rendezvous of two anonymous agents located in a discrete
Euclidean 2Dspace represented by a two dimensional grid with integer
coordinates. This model is equivalent to a standard geometric model in which
the agents have limited visibility allowing them to observe one another at a
close (e.g., unit) range. It is assumed here that each agent is aware of its
own initial integer coordinates, however, the agents are not aware of positions
of one another. We present an efficient explicit construction of spacecovering
sequences embedded into a discrete 2Dspace that allow two robots located at
distance d to meet after adopting a trajectory of length O(d^{2+e}), for any
constant e > 0. This upper bound is complemented by a simple lower bound
argument preventing two robots from meeting each other along a route of length
o(d^2), in the worst case. We also show how to adopt our rendezvous algorithm to
efficient gathering of a larger number of agents in 2Dspace.
Back
 