probability of the transition, given that we observed no message:

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

$$\left({3\atop{3}}\right)$$

The normalizing denominator, ηχ, is the sum of the numerator over all possible successors, Y , which we can pre-compute off-line. We can use the value of η x to determine the likelihood that the agent will send a message upon terminating plan X at time t . In the special case when η x = 0, Equation 3 is not well-defined, as all possible transitions from X require a message. In this case, the agent cannot have begun execution of any successor, en though it has completed execution of X . η χ is therefore the probability mass signifying our belief that the agent is no longer executing X at time t + 1, and is not waiting for a message (i.e., it is in a blocked state). In other words, it is our increased belief that the agent is executing one of X's immediate successors at time t + 1, given that we have seen no message Algorithm 3 presents the pseudo-code for the process of propagating the probabilities forward in time when a message is not observed. First, it initializes all the values to 0 (lines 1–5). The process continues by going over all plans X ∈ M , in post-order —we explore children plans (i.e., plans reachable by hierarchical decomposition transitions) before their parents, and sibling plans in order of execution. For ea plan, the algorithm executes four stages: (1) It determines the plan's outgoing probabilities (lines 7–10); (2) it determines η x ,
the outgoing probability mass that is propagated along the outgoing temporal transitions without being blocked by waiting for a message (lines 11–12); (3) it propagates η x along the non-blocked temporal outgoing transitions (lines 13–20); and finally (4) it computes our belief that the agent will execute the plan at the next time-tick b t +1 ( X , ¬ Wock ) or will be blocking (lines 21–22). The remainder of this section explains these four stages in detail.

Calculating the outgoing probability outx (lines 7–10).   In Algorithm 3, the variable out x represents the total temporal outgoing probability from plan, X , given our belief that the agent was executing X at time t. If a plan X is a leaf, then we derive its temporal outgoing probability, outx , from the temporal model discussed previously, given our belief that the agent is currently executing X (lines 7–8). If X is a parent, lines 9–10 are, in fact, redundant: They serve only to remind the reader that for a parent, Y, outy follows from Y's children when they execute line 20. This depends critically on the post-order traversal of the plan-hierarchy: the outgoing probability of a parent Y is derived from the outgoing probabilities of its last hierarchical-decomposition ildren, and thus all ildren's outgoing probabilities must be calculated before their parents'.