Treffer: Infinite grid exploration with synchronous myopic robots without chirality.

In this paper, we consider the exploration of an infinite grid by a swarm of fully-synchronous robots with weak capabilities: they are disoriented, opaque, do not communicate explicitely, have limited visibility, and cannot occupy the same position at the same time. Our first result shows that, in this context, minimizing the visibility range and the number of used colors are two orthogonal issues: it is impossible to design a solution to our exploration problem that is optimal w.r.t. both parameters simultaneously. Consequently, we address optimality of these two criteria separately by proposing two algorithms; the former being optimal in terms of visibility range, the latter being optimal in terms of number of used colors. More precisely, the first algorithm solves the problem using eight oblivious robots under visibility range two (this visibility being optimal when considering oblivious robots), and the second algorithm solves the problem under visibility range one using six robots and two colors (which is optimal under this visibility range). Finally, we also tackle the optimality in terms of number of robots. According to the lower bound given in Bramas et al. (2020), we propose an algorithm working with a minimum number of robots (five) under visibility range one. This latter uses twelve colors and also guarantees that nodes are visited infinitely often. • The infinite grid exclusive exploration by synchronous oblivious robots is impossible under visibility range one whatever by their number. • The infinite grid exclusive exploration can be achieved by eight synchronous oblivious robots under the optimal visibility range two. • The infinite grid exclusive exploration can be achieved by six synchronous robots under visibility range one using only two colors. • The infinite grid exclusive exploration can be achieved by only five synchronous robots under visibility range one, yet using twelve colors. [ABSTRACT FROM AUTHOR]