We are interested in the problem of map construction of an unknown environment. Even with a complete map, navigation of real autonomous mobile robots is still conducted with imperfect information. This can be caused by various factors, such as imperfect sensors, imperfect mechanical control capabilities, and imperfect road conditions. Computational resource constraints for real time performance may also prevent us from collecting and processing complete information about the environment. A major problem caused by these issues is that accummulated errors in the robot’s self-localization may become arbitrarily large as the robot moves on. Therefore, in addition to the map, we would still need a strategy to help robots recognize the environment along the way and to guide movements toward the destination. This is called the guidance problem by Levitt and Lawton. We discuss an approach for the guidance problem using imprecise data, in the context of world models that are represented by maps with qualitative/ topological information for the global environment, and quantitative/geometric information for the local environment, as suggested by Levitt and Lawton, Kuipers and Levitt. We allow the robot to be equipped with a constant number of sensors. We consider three cost measures: mechanical, sensing, and computation in decreasing order of importance. We propose a number of algorithms with their associated cost measures using a veriety of sensor/measurement devices.