Collaborative exploration in grid domains: Constructive conjecture of a polynomial time complexity

Abstract

This work discusses the problem of exploration of an unknown environment using a collaborative group of simple agents. While this problem was known to be of a non-polynomial time complexity, it was speculated in the past that in grid domains the completion time of this problem is much lower (although analytic proofs were not available hitherto). In this work we present a preliminary result concerning a constructive analytic constraint for guaranteeing that the time complexity of this problem in grid domains is indeed polynomial.