In this research paper, the authors consider planar sceneries as an approach to the problem of multi-robot exploration of an unknown n x n grid graph with oriented disjoint rectangular obstacles. Multi-robot exploration of such sceneries in general graphs is an interesting research area, so this work on finding an efficient navigation algorithm seems to be quite worthwhile.

Although the authors’ approach to robot exploration is based on the fact that the robots know their locations, it turns out that--even for trees--the question of how well an unknown graph can be explored is wide open. Results range between the lower bound for the competitive time ratio of (log k= log log k) and the upper bound of O(k= log k) for k robots. In particular, the authors present an online algorithm that explores such areas with a time overhead of factor O(log2 n) compared to the optimal solution in an n x n grid. The algorithm is a divide-and-conquer algorithm that uses a single robot exploration strategy based on online navigation in a room, from an earlier work by Bar-Eli et al. [1]. The authors measure the efficiency of their robot exploration strategy using a competitive ratio based on dividing the number of steps needed by the robots in parallel following an exploration strategy on an unknown graph by the number of steps needed by the robots following an optimal exploration strategy on a well-known graph. The authors provide a section on related work; however, their contribution is clearly distinguished.

The overall research work is very well documented and I believe it would be quite useful for researchers interested in multi-robot exploration with disjoint oriented rectangular obstacles in planar scenery. An appendix is provided with detailed descriptions of all of the theorem proofs of the proposed exploration algorithm. Although references are provided, they could possibly be further updated.