Algor it hm 4 Array-Overseer(beliefs b, plan-hierarchy array M [], agents A )
1: for all Agents α ∈ A do 2:
3: 4: 5:

if A message m a from a was observed then I NCORPORATE E VIDENCE ( m a, b, M [ a ])
else {No message was sent by a }
PROPOGATE-FORWARD(b, M[a])
rithm 1). From the plan-hierarchy (Figure 1b) it is known that Process-Orders cannot be a possible current or future plan of the agent, and that the helicopter in question is executing Fly-Flight-Plan, i.e., bi (ProcessOrders, ¬block) = 0, bi (FlyFlightPlan, ¬block) = 1.0.

This probability mass is propagated to Fly-Flight-Plan's first ildren, of whi there is one, and thus the belief in this child is set to 1.0 as well.

After some time passes and no message is observed, there is uncertainty as to whether Fly-Flight-Plan and Landing-Zone-Maneuvers are active, as both are possible future states, and the duration of Fly-Flight-Plan is uncertain. OVERSEER would still assign a probability of 1.0 to the top-level plan Evacuate . However, some probability mass from Fly-Flight-Plan would be propagated every time-tick to Landing-Zone-Maneuvers by PROPAGATE-FORWARD (Algorithm 3). For each such propagation, the incoming temporal probability mass being added to the belief in the execution of Landing-Zone-Maneuvers would be propagated to its first ildren immediately. Assuming that the helicopter agent is free to select either Transport-Operations or Escort-Operations , the incoming probability would be split evenly and added to the prior belief in each of the two first children.

In the same temporal propagation step, any outgoing belief from these first ildren would be propagated via their own outgoing temporal transitions.

The inference procedure described by Algorithms 1–4 exploits the particular structure of our representation in ways that more general existing algorithms cannot. The pseudo-code demonstrates that for a single monitored agent, both types of belief updates have a time complexity linear in the number of plans and transitions in M i.e., O ( M ). Thus for N
agents, the space and time complexity of Algorithm 4 is O ( M N ).

We gain this efficiency (compared to an approach such as DBN) from two sources. First, we make a Markovian assumption that the probability of observing a message depends on only the relevant plan being active, independently of execution history. With this assumption, we can incorporate evidence, based on only our beliefs at time t. Second, we make another Markovian assumption in the temporal model, allowing our propagation algorithm to reason forward to time t + 1 based on only our beliefs at time t, without regard for previous history.

## 4. Monitoring A Team By Overhearing

The previous section has outlined an efficient plan-recognition mechanism that is particularly suitable for monitoring a single agent based on its communications. Monitoring a team was achieved by monitoring each member of the team independently of the others.  Unfortunately, although the time complexity of this approach is acceptable, its monitoring (recognition)
results are poor. The evaluation in Section 6.1 provides more details, but, in short, the average accuracy using this approach over all experiments was less than 4%.