Rendezvous of many agents with different speeds in a cycle

Rendezvous is concerned with enabling k ≥ 2 mobile agents to move within an underlying domain so that they meet, i.e., rendezvous, in the minimum amount of time. In this paper we study a generalization from 2 to k agents of a deterministic rendezvous model first proposed by [5] which is based on agents endowed with different speeds. Let the domain be a continuous (as opposed to discrete) ring (cycle) of length n and assume that the k agents have respective speeds s1,..., sk normalized such that min{s1,..., sk} = 1 and max{s1,..., sk} = c. We give rendezvous algorithms and analyze and compare the rendezvous time in four models corresponding to the type of distribution of agents’ speeds, namely Not-All-Identical, One-Unique, Max-Unique, All-Unique. We propose and analyze the Herding Algorithm for rendezvous of k ≥ 2 agents in the Max-Unique and All-Unique models and prove that it achieves rendezvous in time at most 1/2(c+1/c-1)n, and that this rendezvous is strong in the All-Unique model. Further, we prove that, asymptotically in k, no algorithm can do better than time 2/c+3(c+1/c-1)n n in either model. We also discuss and analyze additional efficient algorithms using different knowledge based on either n, k, c as well as when the mobile agents employ pedometers