Only the first term is nonzero, since the others correspond to states of execution that are inconsistent with the observed message:
x Pr(m sg, Y t +1, X t, done(X, t + 1)|E)
We can rewrite this joint probability as a product of conditional probabilities:

$$\begin{array}{l}{{\propto\operatorname*{Pr}\left(m\,s g\big|X_{t},d o n\,e\big(X,t\,+1\,\big),Y_{t+1},{\mathcal{E}}\,\right)}}\\ {{\quad\cdot\operatorname*{Pr}\left(Y_{t+1}\big|X_{t},d o n\,e\big(X,t\,+1\,\big),{\mathcal{E}}\,\right)}}\\ {{\quad\cdot\operatorname*{Pr}\left(X_{t},d o n\,e\big(X,t\,+1\,\big)\big|{\mathcal{E}}\,\right)}}\end{array}$$

We again use our Markovian assumptions to simplify the conditional probabilities, and we rewrite the third probability using our belief state:

$\propto\Pr\left(m\,sg|X_{t},\,done\,e(X,t+1),Y_{t+1}\right)\Pr\left(Y_{t+1}|X_{t},\,done\,e(X,t+1)\right)$  $\cdot\,b_{t}\left(X,\,block\,k\right)$
Finally, we rewrite the first two conditional probabilities using our parameters, µ and π:
xyxy
(2)
Lines 7–8 of Algorithm 1 perform exactly the derived summation of Equation 2.

Normalization of the sum (line 9).  Line 9 normalizes the sum to recapture a wellformed probability distribution. Note that the normalization step must take into account the fact that evidence may be incorporated for plan steps where one is an ancestor of another—in which case the evidence for the ancestor plan is probabilistically redundant.

The more specific evidence (for the descendent plan) will be more useful for visualization, as it is more accurate.

Propagation of Evidence (lines 10–16)  Finally, the recalculated beliefs are set (line 1) and then the changes are recursively propagated down the decomposition hierarchy to the plan's children (line 12), via the call to Algorithm 2. In addition, the recalculated beliefs are propagated up to the plan's ancestors in the decomposition hierarchy (lines 13–16), since evidence of a child plan being active is evidence of its parent being active as well. We assume here that we have no knowledge about the relative likelihood of the child plans, so we treat each as equally likely.  If we had additional knowledge about these likelihoods, we could easily exploit it in our Propagate-Down algorithm.

Algor it hm 2 Propagate-Dow s (plan Y, probability ρ, beliefs b, plans M)