Symmetric rendezvous in planar environments with and without obstacles

Deniz Ozsoyeller, Volkan I Isler, Andrew Beveridge

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We study the symmetric rendezvous search problem in which two robots that are unaware of each other's locations try to meet as quickly as possible. In the symmetric version of this problem, the robots are required to execute the same strategy. First, we present a symmetric rendezvous strategy for the robots that are initially placed on the open plane and analyze its competitive performance. We show that the competitive complexity of our strategy is O(d/R) where d is the initial distance between the robots and R is the communication radius. Second, we extend the symmetric rendezvous strategy for the open plane to unknown environments with polygonal obstacles. The extended strategy guarantees a complete coverage of the environment. We analyze the strategy for square, translating robots and show that the competitive ratio of the extended strategy is O(d/D) where D is the length of the sides of the robots. In obtaining this result, we also obtain an upper bound on covering arbitrary polygonal environments which may be of independent interest.

Original languageEnglish (US)
Title of host publicationAAAI-12 / IAAI-12 - Proceedings of the 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference
Pages2046-2052
Number of pages7
StatePublished - Nov 7 2012
Event26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12 - Toronto, ON, Canada
Duration: Jul 22 2012Jul 26 2012

Publication series

NameProceedings of the National Conference on Artificial Intelligence
Volume3

Other

Other26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12
CountryCanada
CityToronto, ON
Period7/22/127/26/12

Fingerprint Dive into the research topics of 'Symmetric rendezvous in planar environments with and without obstacles'. Together they form a unique fingerprint.

  • Cite this

    Ozsoyeller, D., Isler, V. I., & Beveridge, A. (2012). Symmetric rendezvous in planar environments with and without obstacles. In AAAI-12 / IAAI-12 - Proceedings of the 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference (pp. 2046-2052). (Proceedings of the National Conference on Artificial Intelligence; Vol. 3).