A plan consists of an ordered set of steps, where each step is a unique operator instance. Plans can be totally ordered, in which case every step is ordered with respect to every other step, or partially ordered, in which case steps can be unordered with respect to each other. We assume that a library of operators is available, where each operator has preconditions, deleted conditions, and added conditions. All of these conditions must be nonnegated propositions, and we adopt the common convention that each deleted condition is a precondition. Later in this paper we show how our results can be extended to more expressive languages, but this simple language is sufficient to establish the essence of our argument.
A linearization of a partially ordered plan is a total order over the plan's steps that is consistent with the existing partial order. In a totally ordered plan, a precondition of a plan step is true if it is added by an earlier step and not deleted by an intervening step. In a partially ordered plan, a step's precondition is possibly true if there exists a linearization in which it is true, and a step's precondition is necessarily true if it is true in all linearizations. A step's precondition is necessarily false if it is not possibly true.
A state consists of a set of propositions. A planning problem is defined by an initial state and a set of goals, where each goal is a proposition. For convenience, we represent a problem as a two-step initial plan, where the propositions that are true in the initial state are added by the first step, and the goal propositions are the preconditions of the final step. The planning process starts with this initial plan and searches through a space of possible plans. A successful search terminates with a solution plan, i.e., a plan in which all steps' preconditions are necessarily true. The search space can be characterized as a tree, where each node corresponds to a plan and each arc corresponds to a plan transformation. Each transformation incrementally extends (i.e., refines) a plan by adding additional steps or orderings. Thus, each leaf in the search tree corresponds either to a solution plan or a dead-end, and each intermediate node corresponds to an unfinished plan which can be further extended.