TY - GEN

T1 - Symmetric rendezvous in planar environments with and without obstacles

AU - Ozsoyeller, Deniz

AU - Isler, Volkan I

AU - Beveridge, Andrew

PY - 2012/11/7

Y1 - 2012/11/7

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

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

UR - http://www.scopus.com/inward/record.url?scp=84868291290&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84868291290&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84868291290

SN - 9781577355687

T3 - Proceedings of the National Conference on Artificial Intelligence

SP - 2046

EP - 2052

BT - AAAI-12 / IAAI-12 - Proceedings of the 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference

T2 - 26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12

Y2 - 22 July 2012 through 26 July 2012

ER -