Sensor based planning incorporates sensor information into a robot's planning process, in contrast to classical planning which assumes the robot already has full knowledge about its environment. Many classical planners are complete, in that they can find a path in finite time or determine no such path exists. Most sensor based planners are heuristic algorithms that work well in a variety of environments, but have no proofs of correctness to guarantee a path can be found. Furthermore, they have no thresholds for when the heuristics fail. Typical complete sensor based planners do not consider real world issues such as sensor error. Moreover, they assume sensors have unlimited range and infinite resolution. The purpose of this research is to include ``real world'' issues into a complete sensor based planner. Such real world issues include dead reckoning, sensor limitations, and sensor error. This research will exploit properties of a geometric structure, termed a roadmap, to consider these issues. Although current work uses mobile robots as a test-bed, the results of this work can also be applied to highly articulated robots.
