Exploration of an unknown environment is one of the major applications of multi-robot systems. Many works have proposed multi-robot coordination algorithms to accomplish exploration missions based on multi-agent techniques. Some of these works focus on multi-robot exploration under communication constraints. In this paper, we propose an original way to formalize and solve this issue. Our proposal relies on distributed constraint satisfaction problems (disCSP) which are an extension of classical constraint satisfaction problems (CSP). Compared to other works, our proposal is fully distributed and guaranties the exploration of an unknown environment with maintenance of connectivity between all the members of a robots' team.

Maintaining the network connectivity in mobile Multi-Robot Systems (MRSs) is a key issue in many robotic applications. In our view, the solution to this problem consists of two main steps: (i) making robots aware of the network connectivity; and (ii), making use of this knowledge to plan robots tasks without compromising connectivity. In this paper, we view the ad-hoc network connectivity as an abstraction that is independent from application issues. We propose a new distributed algorithm executing on individual robots to build the connectivity-awareness. The correctness and theoretical analysis of the proposed algorithm are given. We also show how our solution allows checking network bi-connectivity more efficiently than existing work and can be used, for example, during distributed control motion.