A robot uses a map to localize its position. Maps can be loaded into the robot, but often the robot must create a map by itself. Maps are represented using either a grid showing which cells are occupied and which are free or a continuous map containing the coordinates of the obstacles. For a grid map the frontier algorithm enables the robot to explore its environment in order to determine the probability that each cell is occupied or free. A robot can use knowledge of its environment, for example, that it is in a building with rectangular rooms, to facilitate building a map. Algorithms for simultaneous localization and mapping enable a robot to perform these two tasks together, using data from localization and its sensor to extend the map and data from the map to achieve accurate localization.