We consider the problem of enabling an autonomous mobile robot to get from one specified point in its environment to another. The solution to this problem requires the robot to build the representations of its environment to enable it to determine its current location, its destination, and how it can get from one to the other. Many pitfalls have been found trying to achieve the goal of a robustly navigating robot. Among these are: difficulty in getting good sensor information about the robot’s world and difficulty dealing with changing environments. Given these two problems, a third question emerges which is, how does the robot deal with uncertainty both in its environment and in its own position within that environment. In this paper, we report on algorithms and sensor designs intended to improve the performance of a mobile robot in navigational tasks. These include (i) a simple laser rangefinder designed to give accurate point-and-shoot range readings, (ii) an algorithm enabling the robot to identify which areas of its environment have remained static over time and those which have been particularly time-varying, and (iii) an algorithm for localization of a mobile robot using a previously constructed model of the world and current sensor readings. These ideas allow a robot to plan and perform experiments to obtain needed information about its environment. We are implementing these ideas on mobile robotic platforms at the Cornell Robotics and Vision Laboratory. All of these ideas are at least partially implemented, and preliminary experimental results are included to demonstrate proof of concept for these algorithms and sensors.