Collaborative robot exploration and rendezvous: Algorithms, performance bounds and observations

We consider the problem of how two heterogeneous robots can arrange to meet in an unknown environment from unknown starting locations: that is, the pr oblem of arranging a robot rendezvous. We are interested, in particular, in allowing two robots to rendezvous so that they can collaboratively explore an unknown environment. Specifically, we address the problem of how a pair of exploring agents that cannot communicate with one another over long dis tances can meet if they start exploring at different unknown locations in a n unknown environment. We propose several alternative algorithms that robots could use in attempti ng to rendezvous quickly while continuing to explore. These algorithms exem plify different classes of strategy whose relative suitability depends on c haracteristics of the problem definition. We consider the performance of ou r proposed algorithms analytically with respect to both expected- and worst -case behavior. We then examine their behavior under a wider set of conditi ons using both numerical analysis and also a simulation of multi-agent expl oration and rendezvous. We examine the exploration speed, and show that a m ulti-robot system can explore an unknown environment faster than a single-a gent system, even with the constraint of performing rendezvous to allow com munication. We conclude with a demonstration of rendezvous implemented on a pair of act ual robots.