Eager Case Extension and Recovery

The decisions in the trace that are skipped during replay are only those that are known a priori to be unjustified. This does not guarantee that the skeletal plan which is left will ultimately be refined into a solution for the current problem. Without actually completing the search there is no way of predicting whether the constraints that are left in the skeletal plan are consistent with a complete solution. Whenever the skeletal plan is not complete (whenever there are extra goals or unsatisfied initial state conditions) the planner must undergo further planning effort to extend the plan and there is a possibility that this effort may fail, necessitating a recovery phase.

For DERSNLP+EBL, the skeletal plan is extended first, prior to recovery. This plan is backtracked over only after the search process fails to refine it into a full solution to the new problem. This strategy requires a depth limit to be placed on the search tree. Otherwise skeletal plan extension may continue indefinitely, and the planning algorithm becomes incomplete. An eager extension strategy is not, however, linked to a particular search method. For example, it may be used with best-first, depth-first or iterative deepening search. These different search methods are used in the exploration of the subtree under the skeletal plan, prior to backtracking over this plan. Once the skeletal plan is found to fail, the recovery phase that is initiated merely involves exploring the siblings of the replayed path. Like extension, recovery is not linked to a particular search strategy.