Rendezvous of Many Agents with Different Speeds in a Cycle

Rendezvous is concerned with enabling \(k \ge 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 \(s_1, \ldots , s_k\) normalized such that \(\min \{ s_1, \ldots , s_k \} = 1\) and \(\max \{ s_1, \ldots , s_k \} = 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 \ge 2\) agents in the Max-Unique and All-Unique models and prove that it achieves rendezvous in time at most \(\frac{1}{2}\left( \frac{c+1}{c-1}\right) 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 \(\frac{2}{c+3}\left( \frac{c+1}{c-1}\right) 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.