Attempts to apply classical planning techniques to realistic environments have met with two major difficulties. The first is that of average-case inadequacy. As one might expect, the (worst-case) computational characteristics of planning problems are ugly at best; a system that is to operate on problems of any reasonable size must rely on heuristics to reduce the average-case complexity of the problem. The second difficulty is that of uncertainty, or what to do when the real world doesn't work as expected. We have shown in earlier work that particular machine learning techniques are a viable means of addressing the problem of average-case inadequacy [Segre88] in domains without uncertainty. This paper describes a planner operating in a realistic environment that is intended to support the same kind of learning. We report some preliminary experimental results comparing our planner with other approaches to planning in the presence of uncertainty.