Search Results

Two mobile agents, modeled as points moving in the plane, have to meet at some point. Computationally, agents are identical deterministic finite automata. Each agent has a compass showing the cardinal directions. Agents start at two different points, chosen by the adversary. Each agent makes a series of moves. Before each move it takes a snapshot, which is the disc of radius 1 centered at the current position of the agent. This snapshot is an input that causes the automaton to possibly change state and make the next move in a chosen direction at a chosen distance. Moves of the agents are asynchronous: the adversary controls the possibly variable speed of an agent during each move. Without the possibility of leaving marks, meeting is often impossible, e.g. if agents start simultaneously at a distance larger than 1 and move at the same speed. Hence we allow the agents to use movable pebbles. All pebbles used by an agent are identical and they differ between the agents. A pebble of an agent can be dropped by it, and later possibly picked up again. Our main result shows that, using a constant number of pebbles, deterministic rendezvous is always possible, regardless of the actions of the asynchronous adversary. The cost of a rendezvous algorithm executed by the agents is the worst-case length of the trajectory of both agents, over all adversary’s decisions. We show that our rendezvous algorithm has cost O(D²), if the initial positions of the agents are at a distance at most D. This complexity is optimal. As a by-product, we obtain the solution of the leader election problem between two anonymous agents modeled as automata asynchronously navigating in the plane.