Multi-robot exploration on grids with a bounded time

Abstract

In this paper, the problem of exploring a grid environment in the offline setting has been studied. The goal is to propose an algorithm to find the minimum number of robots for exploring a rectangular grid environment with $n$ rows and $m$ columns, denoted by $R(n,m)$, in a predefined time $T$. In the case that there are no obstacles in the environment, an optimal solution has been proposed for the problem. In the other case when the environment may contain some obstacles, it has been pointed out that the problem is NP-complete and cannot be approximated within better than a factor 2. Finally, a $4$-approximation algorithm has been presented in order to explore $R(n,m)$ in the presence of obstacles.