Symmetric Rendezvous Search on the Line With an Unknown Initial Distance

Abstract

In the rendezvous search problem, two robots at unknown locations must successfully meet somewhere in the environment. We study the symmetric version of the problem in which they must use the same strategy. We provide a new algorithm for the symmetric rendezvous problem on the line. Our symmetric strategy has a competitive ratio of 17.686 for total distance traveled and a competitive ratio of 24.843 for total time. Both are improvements over the previously best-known algorithm, which has (time and distance) a competitive ratio of 26.650. Our algorithm can be adapted for bounded linear environments and simple closed curves with the same performance guarantees. It is also robust with respect to errors in motion and differences in robots' starting times. We confirm our theoretical results through simulations and show that our algorithms are practical by reporting the results of real robot deployments in indoor environments.