Reasoning about Plans

Abstract

In classical planning we are faced with the following formal task: Given a set A of permissible actions, a description a of initial states and a description f3 of final states, determine a plan II, i.e. a finite sequence of actions from A, such that execution of II begun in any state satisfying a is guaranteed to terminate in a state satisfying f3. In this paper we extend the classical model of planning by admitting plans that are not assured to succeed. We address two basic problems connected with such plans: (1) How to determine whether a given plan is valid (i.e. always succeeds), admissible (i.e. may succeed or fail) or inadmissible (i.e. never succeeds). (2) Given an admissible plan, determine a minimal set of observations that are to be made in the initial state (or in some intermediate state, if the plan is in progress) to validate or falsify the plan .