We are interested in the problem of how an agent organizes its sensorimotor experiences in order to create a spatial representation. Our approach to solve this problem is the Spatial Semantic Hierarchy (SSH), an ontological hierarchy of representations for knowledge of large-scale space. At the SSH topological level, space is represented by places and connectivity relationships among them. Places are arranged into paths so that the topological representation looks like the street network of a city. Grouping places into regions allows an agent to reason efficiently about its spatial knowledge. Regions can be organized in a hierarchical structure suitable for hierarchical planning and human-level interface. In this paper we show how a hierarchy of regions can be automatically created by an agent. We extend the SSH axiomatic theory to include regions as first order objects at the SSH topological level. Based on this formalization, an implementation using Annotated Hierarchical graphs (AH-graphs) is proposed. The AH-graph model is chosen for its eficiency to perform basic operations like path planning, its facility to integrate information needed by different agent’s tasks, and because it provides a large indexed database of knowledge about the world with a friendly flow of information from and to human operators.