Online multi-robot exploration of grid graphs with rectangular obstacles

Abstract

We consider the multi-robot exploration problem of an unknown n x n grid graph with oriented disjoint rectangular obstacles. All robots start at a given node and have to visit all nodes of the graph. The robots are unrestricted in their computational power and storage. In the local communication model the robots can exchange any information if they meet at the same node. In the global communication model all robots share the same knowledge.