Guaranteeing Rendezvous of Mobile Agents Despite Noise

Abstract

Rendezvous is process of having mutually- oblivious agents locate one another without communication in an unknown environment. Most approaches to rendezvous are either based on random walks or utilize environmental features like landmarks. We investigate the question, “can agents experiencing uncertainty in timing and uncertainty in their own locations be guaranteed to rendezvous in finite time?” We present theoretic upper bounds on the level of uncertainty agents in featureless environments can handle while guaranteeing finite-time rendezvous; we also present algorithms that realize a lower bound on uncertainty. Together, these bounds help define the impact of uncertainty on rendezvous.