Exploration is a central issue for autonomous agents which must carry out navigation tasks in environments whose description is not known a priori. In our approach the environment is described, from a symbolic point of view, by means of a graph; clustering techniques allow for further levels of abstraction to be defined, leading to a multi-layered representation. In this work we propose an unsupervised exploration algorithm in which several agents cooperate to acquire knowledge of the environment at the different abstraction levels; a broadcast model is adopted for inter-agent communication. All agents are structurally equal and pursue the same local exploration strategy; nevertheless, the existence of multiple levels of abstraction in the environment representation allows for the agents’ behaviours to differentiate. Agents carry out exploration at different abstraction levels, aimed at reproducing an ideal exploration profile; each agent selects dynamically its exploration level, based on the current demand.