
$$\begin{array}{r l}{{}}&{{}={\sum_{{\overset{P a i n t i n g^{\prime}}{}}}P_{\mathrm{{point}}}(P a i n t i n g^{\prime}\mid\mathbf{x})\rho(P a i n t i n g^{\prime});}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{}={\sum_{{\overset{P a i n t i n g^{\prime}}{}}}P_{\mathrm{{point}}}(P a i n t i n g^{\prime}=d o n e,\mathbf{x})\ .}}\end{array}$$
$0\rangle.\quad\blacksquare$
$$(23)$$

Note that the product of these simple rules is equivalent to the decision tree CPD shown in Figure 11(a). Hence, this product is equal to 0 **in most contexts, for example, when electricity**
is not done at time t**. The product in non-zero only in one context: in the context associated**
with rule η3**. Thus, we can express the result of the backprojection operation by a rule-based**
function with a single rule:
RuleBackprojpaint(ρ) = hPlumbing ∧ *Electrical* **: 95**i.

Similarly, the backprojection of ρ **when the action is not paint can also be represented by a**
single rule:
RuleBackproj¬paint(ρ) = hPlumbing ∧ Electrical ∧ *Painting* **: 90**i.

Using this algorithm, we can now write the backprojection of the rule-based basis function hj as:
$$g_{j}^{a}({\bf x})=\sum_{i}R u e B a c k p r o j_{a}(\rho_{i}^{(h_{j})}),$$
i), **(23)**
where g a j is a sum of rule-based functions, and therefore also a rule-based function. For simplicity of notation, we use g a j = RuleBackproja (hj ) to refer to this definition of backprojection. Using this notation, we can write Qa(x) = Ra(x) + γPj wjg a j
(x**), which is again a**
rule-based function.

## 8.4 Rule-Based Maximization Over The State Space

The second key operation required to extend our planning algorithms to exploit CSI is to modify the variable elimination algorithm in Section 4.2.1 **to handle the rule-based representation. In Section 4.2.1, we showed that the maximization of a linear combination**
of table-based functions with restricted scope can be performed efficiently using non-serial dynamic programming (Bertele & Brioschi, 1972), or variable elimination. To exploit structure in rules, we use an algorithm similar to variable elimination in a Bayesian network with context-specific independence (Zhang & Poole, 1999).

Intuitively, the algorithm operates by selecting the value **rules relevant to the variable**
being maximized in the current iteration. Then, a local maximization is performed over this subset of the rules, generating a new set of rules without the current variable. The procedure is then repeated recursively until all variables **have been eliminated.**
More precisely, our algorithm "eliminates" variables one by one, where the elimination process performs a maximization step over the variable's domain. Suppose that we are eliminating Xi, whose collected value rules lead to a rule function f, and f **involves**
additional variables in some set B, so that f's scope is B ∪ {Xi}**. We need to compute**
the maximum value for Xifor each choice of b ∈ Dom[B]. We use MaxOut (f, Xi) to denote a procedure that takes a rule function f(B, Xi) and returns a rule function g(B**) such**