Planning Under Uncertainty: Some Key Issues

Abstract

A planner in the real world must be able to handle uncertainty. It must be able to reason about the effect of uncertainty on its plans, select plans that avoid uncertain outcomes when possible, and make contingency plans against different possible outcomes when uncertainty cannot be avoided. We have constructed such a planner, Cassandra, which has these properties. Using Cassandra, we have produced the first general solution to the keys and boxes challenge problem proposed by Michie over twenty years ago. 1 Introduction A planner in the real world must face the challenge posed by uncertainty. To be successful, it must, among other things, be able to reason about the effect of uncertainty on its plans, select plans that avoid uncertain outcomes when possible, and make contingency plans against different possible outcomes when avoidance is impossible. Classical planning has largely ignored the issue of uncertainty, 1 assuming complete and accurate knowledge of the planning context an...