Coherence can be a very powerful heuristic. It assumes non-failing cases, where teammembers successfully maintain their joint execution of particular plans. Under this assumption, evidence about a decision made by one team-member influences (through coherence), our belief of what its team-mates have decided.  And laing su evidence, coherence prefers hypotheses in whi at least the team-members have made joint decisions. For instance, suppose a transition from a team plan is to be taken only by the TRANSPORT team. Under non-failure circumstances, there are only two coherent hypotheses considering this transition: Either all members of TRANSPORT took the transition, or none did. Evidence for one member, supporting one of these hypotheses, can be used to infer the state of the other members.

The significance of this property of coherence is that if the monitoring system can reduce the uncertainty for even one agent, then this reduction will be amplified through the use of the coherence heuristic to apply to the other agents as well. The use of the coherence heuristic can thus lead to a significant boost in monitoring accuracy, since the number of hypotheses underlying any further (probabilistic) disambiguation is cut down dramatically.

Section 6.1 provides an in-depth evaluation of the use of coherence and knowledge of roles to select plan recognition hypotheses in OVERSEER.

The use of coherence significantly increases the time complexity of the computation.

At the very least, it requires setting inter-agent links in the array of plan recognizers used by OVERSEER (Section 3.4), such that these links represent a probabilistic association between plans that are to be executed jointly (in contrast with the temporal and hierarchic decomposition transitions used thus far). For instance, if a specific plan X is to be executed jointly by agents A and B , then such a link would be constructed between the variable X A
(representing agent A's execution of a plan X ) and the variable X β (representing agent B 's execution of the same plan). In general, there would be N ∗ ( N − 1) such inter-agent links between N agents, for each one of the joint plans (of which there are at most M ). Thus given N agents, and the array of recognizers M [], where each individual agent's plan-hierarchy is of size M , the run-time complexity of an exact-inference algorithm would be at least O(MN 2 ) and quite likely much worse (since in general there is an exponential number of cccess the complete of the complete of the complete and the next section (Section 5.1),
we describe a highly scalable (in the number of agents) representation for reasoning about coherent hypotheses.

## 4.2 Exploiting Procedures That Maintain Social Structures

A monitoring system can exploit knowledge of the procedures agents use to maintain their s seen to the control of the vations. For instance, if the monitoring system could accurately predict future observable behavior of monitored agents, then while it has not observed the predicted behavior, the monitoring system may infer that the agents have not reached the state associated with the predicted behavior. Thus such predictions can be used to eliminate monitoring hypotheses, by setting an individual agent's µ XY probabilities to reflect a prediction that a message will be transmitted by the agent as its execution of X terminates and it initiates Y . For instance, in our own application, the ARIADNE information agent is queried for possible threats before each route is followed in the evacuation. It may therefore be possible to predict that before