Flight over Bristol

Bristol Algorithms Days 2010
Feasibility Workshop

15 - 16 February 2010

  •    •    •  

Asynchronous rendezvous in 2D-spaces

Leszek Gasieniec

We study efficient rendezvous of two anonymous agents located in a discrete Euclidean 2D-space 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 space-covering sequences embedded into a discrete 2D-space 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 2D-space.


  The University of Bristol   EPSRC