

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

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

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

Figure 8: Technical problems with Assumption Justification. In (a), an assumption replaces another assumption nonmonotonically. In (b), multiple assumption justifications for the same assumption must be supported.

local assertion j can simply be added to the assumption justification of A, as in **2. For an**
on-demand implementation, the procedure here would recur through local assertions, until all context dependencies for local assertions contributing to A **had been identified.**
The worst-case computational complexity of this algorithm **is polynomial in the number**
of assertions in the subtask. The addition of a higher-level assertion can be done in constanttime (a single pointer reference). However, **2 must uniquely add context assertions from the**
assumption justification of the local assertion. There are at most (n − **1) local assumption** justifications whenever the nth **assertion is created. Thus, the concatenation needs to be**
performed no more than (n−**1) times for any call to the assumption justification procedure.** This limit provides an upper bound of O(n**) on the complexity of the assumption justification**
procedure: the worst-case cost of building an individual assumption justification is linear in the number of assertions, n**, in the level. However, the architecture executes the assumption**
justification procedure for every assertion in the level. Thus, the worst case cost for building all the justifications in a particular level is O(1 + 2 . . . + n**) or** O(n 2).

Non-monotonic changes complicate the implementation. The **architecture must disable**
a replaced assumption, rather than delete it, because the initial assumption may need to be restored. For example, in Figure 8 (a), assume that the assertion of E **leads to both** the assertion of 2 in the local subtask and the retraction of 1 (i.e., 2 is a revision of 1**). If** the agent retracts E, Assumption Justification will retract 2**, as desired, but it must also**
re-enable 1. Thus, assumption 1 **must remain available in memory, although disabled.**
Figure 8 (b) illustrates a second problem. An assumption can **have multiple assumption justifications. These justifications can change as reasoning progresses. Assumption** 1 initially depends on assertions A, B, and C **in higher levels. Now assume that later in** the processing, the agent removes A**, which normally would result in the retraction of** 1. However, in the meantime, the context has changed such that 1 **is now also justified by** {C,
D, E}. Now when the agent removes A**, the architecture should not immediately retract** 1 but must determine if 1 **is justified from other sources.**
An implementation of Assumption Justification in Soar was completed by members of the Soar research group at the University of Michigan. Experiments using Air-Soar, a flight simulator domain (Pearson et al., 1993), showed that the overhead of maintaining all prior assumptions in a level produced a significant negative impact on agent performance. In this domain, Assumption Justification incurred significant **computational cost, requiring at**