In robotics uncertainty exists at both planning and execution time. Effective planning must make sure that enough information becomes available to the sensors during execution, to allow the robot to correctly identify the states it traverses. It requires selecting a set of states, associating a motion command with every state, and synthesizing functions to recognize state achievement. These three tasks are often interdependent, causing existing planners to be either unsound, incomplete, and/or computationally impractical. In this paper we partially break this interdependence by assuming the existence of landmark regions in the workspace. We define such regions as “islands of perfection” where position sensing and motion control are accurate. Using this notion, we propose a sound and complete planner of polynomial complexity. Creating landmarks may require some prior engineering of the robot and/or its environment. Though we believe that such engineering is unavoidable in order to build reliable practical robot systems, its cost must be reduced as much as possible. With this goal in mind, we also investigate how some of our original assumptions can be eliminated. In particular, we show that sensing and control do not have to be perfect in landmark regions. We also study the dependency of a plan on control uncertainty and we show that the structure of a reliable plan only changes at critical values of this uncertainty. Hence, any uncertainty reduction between two consecutive such values is useless. The proposed planner has been implemented. Experimentation has been successfully conducted both in simulation and using a NOMAD-200 mobile robot.