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 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 is guaranteed to terminate in a state satisfying 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. 1