Deterministic rendezvous problem

The deterministic rendezvous problem is a problem in computer science and robotics that involves two or more robots or players that must find each other by following a predetermined set of instructions. The goal is for the robots to meet at a specific location, or rendezvous point, without knowing the location of the other robot or robots. In the deterministic rendezvous problem, each robot follows the same set of instructions, but each robot is assigned a unique label or identifier to differentiate them from each other [2]. This unique label is used to break the symmetry of the problem, as it allows the robots to distinguish themselves from each other and to follow the instructions in a specific order [3].

The deterministic rendezvous problem is typically solved by the robots acting synchronously, meaning that they all follow the instructions at the same time [4]. However, there are also non-synchronous versions of the problem, where the robots may act at different times or may have different internal clocks [5].

The deterministic rendezvous problem has applications in a wide range of fields, including robotics, distributed systems, and computer networks [6]. It is often used as a benchmark for evaluating the performance of algorithms and protocols for rendezvous and coordination in these fields [7].

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 [math]\displaystyle{ O\left(n^5\sqrt{\tau l}+n^{10}l\right) }[/math], 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 [math]\displaystyle{ O\left(n^{15}+l^3\right) }[/math] 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 [math]\displaystyle{ O\left(n^{5}+l\right) }[/math] 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.

A universal traversal sequence is a sequence of instructions comprising a graph traversal for any regular graph with a set number of vertices and for any starting vertex. Since the robots may not be in a regular graph, a universal traversal sequence for n nodes and degree d is used, where d is the maximum degree of the graph. Any instructions in the chosen universal traversal sequence which specify that the robot travels to a neighbor of the current node which doesn't exist (i.e., the current node has degree < d) are ignored. By doing this, all nodes in the graph with degree less than d are treated as having enough self-loops to bring their total degree up to d, effectively allowing the graph to be treated as regular for the purpose of universal traversals.

The basic idea of Ta-Shma and Zwick's solution is that if one of the robots completes a complete traversal of the graph while the other robot remains idle, or rests, then the two robots are guaranteed to meet. Since the size of the graph is unknown, the robots run universal traversal sequences for increasing values of n, while periodically resting. Whether a robot rests before or after a traversal depends upon the value of its label.

For example, one of the robots could run the sequence: [math]\displaystyle{ U_10^{u_1}U_20^{u_2}U_40^{u_4}U_80^{u_8}...U_{2^i}0^{u_{2^i}}... }[/math] while the other robot runs the sequence: [math]\displaystyle{ 0^{u_1}U_10^{u_2}U_20^{u_4}U_40^{u_8}U_8...0^{u_{2^i}}U_{2^i}... }[/math] where U_i is a universal traversal sequence for a graph with i nodes, u_i is the number of steps in that universal traversal sequence, and 0^k represents k steps where the robot rests. The universal traversal sequence for the size of the actual graph will be run by one robot while the other rests for the number of steps in that traversal. However, this only works if the two robots are activated at the same time.

To cover the case where the robots are activated at different times, the sequence to run will include rest periods of length u_i after each step (in the traversal and the rest period). For example, one of the robots would run the sequence: [math]\displaystyle{ \sigma_10^{u_1-1}\sigma_20^{u_1-1}\sigma_30^{u_1-1}...\sigma_{u_1}0^{u_1-1}0^{2u_1}\pi_10^{u_2-1}\pi_20^{u_2-1}\pi_30^{u_2-1}...\pi_{u_2}0^{u_2-1}0^{2u_2} }[/math] where σ_i is the i^th step of U₁ and π_i is the i^th step of U₂.

In order to formally present the sequence that each robot will run, some additional notation is needed. Let:

• σ^b = 0 if b = 0
• σ^b = σ if b = 1
• [math]\displaystyle{ \bar{L} = 1 - L }[/math]
• [math]\displaystyle{ \sigma^{m_1..m_k}=\sigma_1^m...\sigma_k^m }[/math]
• [math]\displaystyle{ D_k(\sigma_1...\sigma_m)=\sigma_10^k...\sigma_m0^k }[/math]

Assuming that one robot's label is 0 and that the other robot's label is 1, the sequence that each robot would run is: [math]\displaystyle{ D_{u_1-1}((U_1U_1)^{L\bar{L}})D_{u_2-1}((U_2U_2)^{L\bar{L}})...D_{u_{2^k}-1}((U_{2^k}U_{2^k})^{L\bar{L}})... }[/math]

The sub-sequence [math]\displaystyle{ D_{u_i-1}((U_iU_i)^{L\bar{L}}) }[/math] is known as a block and can be rewritten as [math]\displaystyle{ D_{u_i-1}((U_iU_i)^L(U_iU_i)^{\bar{L}}) }[/math].

If σ = U_i and m = u_i, the block can be further simplified to: [math]\displaystyle{ (\sigma_10^{m-1}...\sigma_m0^{m-1}\sigma_10^{m-1}...\sigma_m0^{m-1})^L }[/math] [math]\displaystyle{ (\sigma_10^{m-1}...\sigma_m0^{m-1}\sigma_10^{m-1}...\sigma_m0^{m-1})^{\bar{L}} }[/math] Both of the above lines are known as chunks. One chunk consists of a universal traversal sequence with interleaved rest periods, while the other chunk is a rest period of length 2m².

If the robot's label is 0, then each block it runs is equal to: [math]\displaystyle{ 0^{2m^2}\sigma_10^{m-1}...\sigma_m0^{m-1}\sigma_10^{m-1}...\sigma_m0^{m-1} }[/math] If the label is 1, then each block it runs is equal to: [math]\displaystyle{ \sigma_10^{m-1}...\sigma_m0^{m-1}\sigma_10^{m-1}...\sigma_m0^{m-1}0^{2m^2} }[/math]

Analysis

The sequence of instructions listed above will allow two robots with labels 0 and 1 to meet after O(n^2c) time steps.

Ta-Shma and Zwick show how to extend this solution to allow the robots to meet after only O(n^c) time steps and how to deal with arbitrary labels (which increases the time until the robots meet to O(n⁵+l) time steps).