m-RENDEZVOUS: Multi-Agent Asynchronous Rendezvous Search Technique

Abstract We study the problem of asynchronous rendezvous search with multiple mobile agents (robots) in the plane. The goal of the robots is to meet at a location in the environment which is not determined in advance as quickly as possible. They do not know the initial locations of each other or their own initial locations. Moreover, the initial distance between any pair of robots is also unknown. Therefore, the problem must be solved using an online approach. We study a new variant of the rendezvous search problem which we call m -RP. The objective of m -RP is exactly m n of n robots to meet. n is the total number of robots in the environment, m is the number of robots that are active and want to meet, and k = n − m is the number robots that are waiting and not required to meet. None of the n robots knows m or k . We consider the symmetric version of the problem. In this version, the robots must execute the same strategy. For this problem, we present the algorithm m -RENDEZVOUS and show that its competitive ratio is O ( ( d k ) / R ) , where d is the initial distance between the furthest robot pair in the environment and R is the communication range of each robot. m -RENDEZVOUS utilizes the waiting robots in the environment to break the symmetry, and hence to achieve deterministic rendezvous. In addition to the theoretical results, we also verify the performance of our algorithm through extensive simulations.