Planning operations for an autonomous agent is a much-studied problem. Most solutions require that the agent’s domain be fully known at the time of planning and fixed during execution. For many domains, however, this is not possible. One approach to the problem is to construct an initial plan based on the best information a priori and revise the plan during execution as better information becomes available. In this paper, we show that this approach yields good average case performance compared to competing approaches for certain problems of interest. We also discuss the uses for this approach to planning and describe qualitative conditions for making it tractable.