Symmetric rendezvous search on the line with an unknown initial distance

Deniz Ozsoyeller, Andrew Beveridge, Volkan Isler

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 inwhich 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.

Original languageEnglish (US)
Article number6564428
Pages (from-to)1366-1379
Number of pages14
JournalIEEE Transactions on Robotics
Volume29
Issue number6
DOIs
StatePublished - Dec 2013

Keywords

  • Linear search problem
  • Lost cow problem
  • Rendezvous search
  • Symmetric rendezvous

Fingerprint Dive into the research topics of 'Symmetric rendezvous search on the line with an unknown initial distance'. Together they form a unique fingerprint.

Cite this