

![0_image_0.png](0_image_0.png)

Assumption Justification is a form of dependency-directed backtracking (Stallman &
Sussman, 1977). In dependency-directed backtracking, regardless of the chronological order in which an architecture makes assertions, the architecture can identify and retract those assertions that contributed to failure in a search and retain all other assertions. In Assumption Justification, the architecture retracts only those assumptions that are directly affected by a change in the context. Assumptions created later in the processing, not dependent on the change, are unaffected. Consider the examples in Figure 10. In (a), assumptions 1 and 2 each depend upon disjoint sets of assertions. With Assumption Justification, removal of any assertion in 1**'s assumption justification will result in the retraction of** 1; 2 is unchanged, even if the architecture asserted 2 **after** 1.

Dynamic Hierarchical Justification is similar to backjumping **(Gaschnig, 1979). Backjumping heuristically determines the state to which a current search should backtrack or**
"backjump." The heuristics used by backjumping are based on **syntactic features of the**
problem. For instance, in constraint satisfaction problems, the backjumping algorithm identifies which variable assignments are related to other variable assignments via the constraints specified in the problem definition. When a violation is discovered, the algorithm backtracks to the most recent, related variable (Dechter, 1990). Intervening variable assignments are discarded. In DHJ, when an assertion in the hierarchy changes, the system
"backjumps" in its knowledge search to the highest subtask in the hierarchy not dependent on the change. In Figure 10 (a) all dependent assertions are collected in the support set for the subtask. If any of the higher level assertions change, the entire subtask is removed.

When using DHJ, as in backjumping, some previous knowledge search may need to be repeated after backtracking. Assume the removal of the subtask in Figure 10 (a) was due to a change in A. If a similar subtask is reinitiated, assumption 2 **may need to be** regenerated. This regeneration is unnecessary because 2 **did not need to be retracted**
to avoid inconsistency. Under Dynamic Hierarchical Justification, the agent retracts all reasoning in the dependent subtask (and all lower levels in the hierarchy); assertions not dependent on the change in the context can also be removed. Thus, like backjumping, DHJ uses a syntactic feature of reasoning (decomposition into subtasks) to choose a backtracking point and this backtracking is not always as conservative as **possible.**
Although the subtask decomposition is a syntactic feature of the knowledge search, it is a strongly principled one, reflecting a semantic analysis **of the task by a knowledge designer. Hierarchical task decomposition is based on the premise that tasks can be broken**
down into discrete units that have little interaction with other units; they are nearly decom-