Symmetric Rendezvous Search on the Line With an Unknown Initial Distance
Küçük Resim Yok
Tarih
2013
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ieee-Inst Electrical Electronics Engineers Inc
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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.
Açıklama
Anahtar Kelimeler
Linear search problem, lost cow problem, rendezvous search, symmetric rendezvous
Kaynak
Ieee Transactions on Robotics
WoS Q Değeri
Q1
Scopus Q Değeri
Cilt
29
Sayı
6
