Assembly tasks typically involve tight fits and precise positioning beyond the capability of position-controlled robots. The motions required for such tasks, called fine-motions, may be performed by means other than pure position control. Fine-motions must overcome the inherent uncertainty in the robot's position relative to its environment. This uncertainty results from errors in sensing, modeling, and control. If bounds on these errors are known or can be estimated accurately, motions may be planned that will perform fine-motion tasks despite the uncertainty. Automatic planning of robot motions to perform these tasks prevents the tedious, error-prone process of constructing a plan for each task by hand. This paper presents an approach to fine-motion planning and an implementation of the algorithms in a planning system. A simple method is explored to plan and perform assembly tasks in the presence of uncertainty using a geometric model of the task, error bounds, and a model of compliant behavior. The principal ingredients of the method are algorithms that manipulate graph representations of the task to find, and choose from, a small number of alternative plans. The approach is implemented in a system that generates plans from task descriptions of two degree-of-freedom operations.