Communication-Constrained Multi-Robot Exploration with Intermittent Rendezvous

A challenge in Multi-Robot Exploration (MRE) tasks is formulating efficient distributed exploration strategies since, in general, robots cannot communicate freely and the environment can be dynamic and unknown. Most solutions deliver good performance at the cost of adding more robots or network relays while exploring, which helps to connect the robots through time. This paper proposes a novel intermittent rendezvous method that allows robots to explore an unknown environment while sharing maps at rendezvous points without adding relays or other robots. We propose dynamically updating the rendezvous locations throughout the exploration and designing an exploration strategy that prioritizes future rendezvous. We generate our rendezvous strategies automatically by reducing the MRE to instances of the Job Shop Schedule Problem (JSSP) with temporal connectivity graphs. We evaluate our method in simulation in various virtual urban environments and in a Gazebo simulation using the Robot Operating System (ROS). Our results suggest that our method can be better than using relays or maintaining intermittent communication with a base station since we can explore faster without additional hardware to create a relay network.