Nir Friedman and Daphne Koller
Most planners constructed up to now are qualitative: they deal with uncertainty by considering all possible outcomes of each plan, without quantifying their relative likelihood. They then choose a plan that deals with the worstcase scenario. However, it is clearly infeasible to plan for every possible contingency. Even beyond the purely computational considerations, planning for highly unlikely worst-case scenarios can force the agent to choose an overly cautious plan with low utility. One common way to avoid this problem is to make assumptions about the behavior of the world, i.e., assume that certain contingencies are impossible. In this paper, we analyze the paradigm of qualitative planning under assumptions, using decision-theoretic tools. We present conditions that guarantee the existence of optimal assumptions (ones inducing the agent to choose the plan with maximum expected utility). Finally, we sketch how assumptions can be constructed for a certain restricted class of planning problems.