We propose a landmark-based representation of maps to be used for robotnavigation and exploration. Our approach is aimed towards mobilerobots that operate over expansive, imprecisely known terrain without asingle ``global'' map. Instead, a map is pieced together fromlocal terrain and navigation data stored in a directed graph. Each of thegraph's vertices contains information describing a landmark locally (e.g. adetailed map of that landmark's immediate surroundings). Thegeometric relationships between landmarks are unknown. Graph edgesstore language-based directions that enable a robot to steerbetween landmarks. These directions are written in the motiondescription language MDLe, reducing the complexity of the map and makingnavigation programs robot-independent. Furthermore, the proposedarchitecture iseconomical with respect to the amount of storage required to describefar-flung areas of interest. We present preliminary resultsdemonstrating our ideas using an indoor robot.