Rendezvous in planar environments with obstacles and unknown initial distance

摘要

In the rendezvous search problem, two or more robots at unknown locations should meet somewhere in the environment as quickly as possible. We study the symmetric rendezvous search problem in unknown planar environments with polygonal obstacles. In the symmetric version of the problem, the robots must execute the same rendezvous strategy. We consider the case where the initial distance between the robots is unknown, and the robot is unaware of its and the other robots' locations in the environment. We first design a symmetric rendezvous strategy for two robots and perform its theoretical analysis. We prove that the competitive ratio of our strategy is O(d/D). Here, d is the initial distance between the robots and D is the length of the sides of the square robots. In unknown polygonal environments, robots should explore the environment to achieve rendezvous. Therefore, we propose a coverage algorithm that guarantees the complete coverage of the environment. Next, we extend our symmetric rendezvous strategy to n robots and prove that its competitive ratio is O(d/(nD)). Here, d is the maximal pairwise distance between the robots. Finally, we validate our algorithms in simulations.