Robot control systems are subject to significant uncertainty and error. Typical robots are also equipped with sensors-force sensors, kinesthetic positions sensors, tactile sensors, vision, and so forth. However, these sensors are also subject to significant uncertainty. Finally, the geometrical models of the robot and the environment (part, obstacles, etc.) cannot be exact-they are accurate only to manufacturing tolerances, or to the accuracy of the sensors used to acquire the models. Uncertainty is an absolutely fundamental problem in robotics, and plans produced under the assumption of no uncertainty are meaningless. What is needed is a principled theory of planning in the presence of uncertainty. Such a theory must not only be computational, but must also take uncertainty into account a priori. In motion planning with uncertainty, we exploit compliant motion-sliding on surfaces-in order to effect a "structural" reduction in uncertainty. Such compliant motion plans can be synthesized from a computational analysis of the geometry of the holonomic constraints. We will present a precise framework for motion planning with uncertainty. In particular, given geometric bounds on the uncertainty in sensing and control, we develop algorithms for generating and verifying compliant motion strategies that are guaranteed to succeed as long as the sensing and control uncertainties lie within the specified bounds. The first results in this theory begin with Lozano-Perez, Mason, and Taylor [LMT], with subsequent contributions by Mason [MA2], Erdmann [E], Donald [D], and others. This research has led to a theoretical computational framework for motion planning with uncertainty, which we explore in this focused survey paper.