
## 3.3  Belief Update With No Observation

In overhearing tasks, there is a great deal of uncertainty about when agents complete the execution of their plan steps, since agents do not necessarily send messages upon every termination or initiation of a plan. Therefore, if no messages are observed at time t, then the system's beliefs for time t +1 must be calculated based on the possibility that the agents may have initiated or terminated plans without sending any messages. To support the necessary belief update, we need a model of plan execution that provides us with a probability of plan termination over time (i.e., Pr( done (X, t))). In principle, this probability distribution can be arbitrarily complex, and its structure may vary enormously from domain to domain, and en from plan to plan within the same domain. In some domains, obtaining an accurate model of this distribution requires complex knowledge acquisition from domain experts or else a complex learning process on the part of the agent. In addition, an accurate model may be too complex to support efficient online inference.

OVERSEER instead uses a temporal model that supports both efficient inference and simple parameter estimation procedures. OVERSEER models the duration of a (leaf) plan, X, as an exponential random variable.  In other words, the probability of the plan completing execution within τ time units increases as 1 − e − τλx The single parameter, λχ, corresponds to 1 /(mean duration of X ), which we can easily acquire from domain experts or previous runs. As for inference, the exponential random variable has a Markovian property, in that the probability of the plan's completion between times t and t + 1 is

## Pr(Done(X, T + 1)|X T ) ≡ 1 − E-^Z,

independent of how long the agent has been executing X before time t. This strong assumption may not fully hold in some real-world domains, but it is often a good approximation. Also, the error associated with this approximation may be acceptable, given the enormous gain in inferential efficiency (as we show in the remainder of this section).

These efficiency gains manifest themselves when OVERSEER rolls the model forward in time to compute its belief state for the next time slice.  Given the exponential random variable as a model of plan duration, the probability of completion of a leaf plan is a constant, 1 - e-> ε , for each plan X . For plans with children, the probability of completion is exactly the probability of completion of its last child (according to the temporal ordering of the children).

Having computed the probability of plan termination, OVERSEER then evaluates which plan the agent may execute next. It examines the possible successors and, for each, computes the probability of taking the corresponding transition, conditioned on the fact that no message was observed (1 = µ xy ), and on the prior probability of taking this message ( π xy ).

Again, as mentioned in Section 3.2, OVERSEER makes a Markovian assumption that the plan history before time t does not affect the likelihood of the various transitions.  Given this assumption, it can combine the two parameters, π and μ , to get the desired conditional