We are interested in designing autonomous mobile robots for industrial applications. Building useful robots for real-world tasks will require developing efficient methods for representing and reasoning about space. Pervasive among spatial representation schemes suggested to date is the assumption that the robot has some built-in mechanism that allows it to uniquely identify different locations in the world. This paper extends one such rep-resentation, developed by Smith and Cheeseman , to account for uncertainty in the identification of locations. We will begin with a brief account of Smith and Cheeseman's model.