Symmetric Linear Rendezvous with an Unknown Initial Distance

Date of Submission: 
March 28, 2011
Report Number: 
11-008
Report PDF: 
Abstract: 
Imagine two robots trying to meet. They do not know each other's locations. How should they move so that they meet as quickly as possible? This classical rendezvous problem has numerous applications in search-and-rescue, network formation, multi-robot exploration and mapping. We study symmetric rendezvous on the line and introduce a new version of the problem in which the robots do not have any information about their initial distance. Further, they must execute the same strategy. We present an algorithm that is 19.166-competitive in terms of distance traveled, and discuss further refinements. As an application of our algorithm, we present results from an experiment in which two mobile robots try to meet in a corridor.