DERSNLP+EBL is a refinement planner that solves a planning problem by navigating a space of potential solutions, each represented as a partly constructed plan. Syntactically, a plan in this space can be seen as a set of constraints (see below). Semantically, a partial plan is a shorthand notation for the set of ground operator sequences that are consistent with its constraints. The latter is called the candidate set of the partial plan, and is denoted by .In particular, a partial plan is represented as a 6-tuple, ,where
Planning consists of starting with a null plan (denoted by ) , whose candidate set corresponds to all possible ground operator sequences, and successively refining the plan by adding constraints until a solution is reached. Each planning decision represents a choice as to how to resolve an existing flaw in the plan, which is either an open condition (unachieved goal) or a threat to a causal link. To understand how these choices are validated during the replay process it is useful to think of a planning decision as an operator acting on a partly-constructed plan. The possible choices available to DERSNLP+EBL are shown in Figure 6.
Planning decisions have preconditions which are based on the existence of a flaw in the current active plan and have effects which alter the constraints so as to eliminate the flaw. For example, the precondition of an establishment choice is specified in terms of the existence of an unachieved subgoal. The effect is the addition of a causal link that achieves this open condition. The precondition of a resolution decision is a threat in that one step is clobbering an existing causal link. A threat is resolved by adding a step ordering which either promotes or demotes the clobberer relative to the causal link.
Before a decision is replayed, it is first compared with the current active plan to determine whether its precondition holds in the new context. Invalid decisions, those whose preconditions don't match, are skipped. Establishment decisions are ignored if the goals they achieve are not present as open conditions in the current active plan. Threat resolutions are skipped if the threat is not present. Previous choices which are justified in the current situation are used as guidance to direct the new search process. Replaying a valid decision involves selecting a match for that decision from the children of the current active plan, and making this child the next plan refinement.
DERSNLP+EBL's eager derivation replay strategy replays all of the applicable decisions in the trace in sequence. This replay strategy can be contrasted with that of PRODIGY/ANALOGY  where replay is alternated with from-scratch planning for extra goals not covered by a case. In eager derivation replay each previous decision is eagerly adopted if justified in the current context. Since invalid instructions have been skipped, the skeletal plan which is the end result of replay is comparable to the product of the fitting phase in plan reuse [22,13]. In contrast to plan reuse, derivation replay does not alter the underlying planning strategy. Replay merely provides search control, directing the search as to which node to visit next. This means that DERSNLP+EBL inherits all of the properties of SNLP, including soundness, completeness, and systematicity.
A sample trace of SNLP's decision process is shown in