Grid Exploration

The grid exploration problem consists in finding a shortest possible tour which visits every cell of a grid at least once. Solutions to this problem can be applied in scenarios where an autonomous robot must perform tasks such as mowing the lawn or cleaning a room. We distinguish two variants of grid exploration. In the offline variant, the entire grid is given as input, whereas in the online variant the robot has limited visibility and must acquire information about the initially unknown grid as it explores it. We provide an overview of currently known results for offline and online grid exploration. We also develop new techniques to prove bounds for the length of shortest exploration tours and show how to combine them to get stronger bounds. Previous results for the online variant assume that the robot is initially located at the boundary of the grid. We give a new algorithm which does not make this assumption and achieves the same competitive ratio.