Deterministic rendezvous problem

The deterministic rendezvous problem is a variant of the rendezvous problem where the players, or robots, must find each other by following a deterministic sequence of instructions. Although each robot follows the same instruction sequence, a unique label assigned to each robot is used for symmetry breaking. Typically, the robots act synchronously, though non-synchronous versions of the deterministic rendezvous problem exist.

Overview

In the synchronous version of the deterministic rendezvous problem, both robots are initially placed at arbitrary nodes in a finite, connected, undirected graph. The size and structure of the graph is unknown to the robots.

The information known by a robot is as follows:

• T, the number of time steps since it has been activated
• d, the degree of the node currently occupied by the robot
• L, the label of the robot (typically taking the form of a bit string)

To solve the deterministic rendezvous problem, both robots must be given a sequence of deterministic instructions which allow the robots to use their known information to find each other. The robots are considered to have found each other if they are both occupying the same node in the graph during the same time step.

Solutions

A number of algorithms exist to solve the deterministic rendezvous problem. Some of the solutions are listed below:

Dessmark et. al

In 2006, Dessmark et. al presented a solution which solves the deterministic rendezvous problem in time proportional to ${\textstyle O\left(n^{5}{\sqrt {\tau l}}+n^{10}l\right)}$, where:

• n is the number of nodes in the graph
• τ is the difference in activation time between the two robots
• l is the length of the shorter of the labels of the robots

This solution is not ideal, since τ is an input parameter of the deterministic rendezvous problem and can therefore be arbitrarily large.

Kowalski and Malinowski

In 2008, Kowalski and Malinowski presented a solution which solves the problem in ${\textstyle O\left(n^{15}+l^{3}\right)}$ time. This is a significant improvement, since this time complexity is not dependent on τ. This solution has one major drawback, though. It makes use of backtracking, where the robots must keep track of each edge that they have traversed. This is a drawback because it places assumptions on the structure of the graph (namely, how it is labeled), and the robots' sensory and memory capabilities.

Ta-Shma and Zwick

The solution presented by Ta-Shma and Zwick in 2014 solves the problem in ${\textstyle O\left(n^{5}+l\right)}$ time. In addition to the reduced time complexity (which doesn't rely on τ), this solution also doesn't use backtracking. Instead, it uses the notion of universal traversal sequences to help solve the problem.