Robots must plan and execute tasks in the presence of uncertainty. Uncertainty arises from sensing errors, control errors, and uncertainty in the geometric models of the environment and of the robot. The last, which we will call model uncertainty, has received little previous attention. In this paper we present a formal framework for computing motion strategies which are guaranteed to succeed in the presence of all three kinds of uncertainty. We show that it is effectively computable for some simple cases. The motion strategies we consider include sensor-based gross motions, compliant motions, and simple pushing motions. We show that model uncertainty can be represented by position uncertainty in a generalized configuration space. We describe the structure of this space, and how motion strategies may be planned in it. It is not always possible to find plans that are guaranteed to succeed. In the presence of model error, such plans may not even exist. For this reason we investigate Error Detection and Recovery (EDR) strategies. We characterize what such strategies are, and propose a formal framework for constructing them. Our theory represents what is perhaps the first systematic attack on the problem of error detection and recovery based on geometric and physical reasoning.