Multi-robot Symmetric Rendezvous Search on the Line with an Unknown Initial Distance
This work addresses coordination challenges for multiple robots in search scenarios, but it is incremental as it builds directly on existing symmetric rendezvous algorithms.
The paper tackles the multi-robot symmetric rendezvous search problem on a line with unknown initial distances, extending a prior algorithm to handle more than two robots in both synchronous and asynchronous cases. It presents theoretical competitive ratios of O(n^0.67) for the synchronous algorithm and O(n^1.5) for the asynchronous one, with simulations confirming these results.
In this paper, we study the symmetric rendezvous search problem on the line with n > 2 robots that are unaware of their locations and the initial distances between them. In the symmetric version of this problem, the robots execute the same strategy. The multi-robot symmetric rendezvous algorithm, MSR presented in this paper is an extension our symmetric rendezvous algorithm, SR presented in [23]. We study both the synchronous and asynchronous cases of the problem. The asynchronous version of MSR algorithm is called MASR algorithm. We consider that robots start executing MASR at different times. We perform the theoretical analysis of MSR and MASR, and show that their competitive ratios are $O(n^{0.67})$ and $O(n^{1.5})$, respectively. Finally, we confirm our theoretical results through simulations.