the communication procedures used by the team (Section 4.2). Here, the communications predictions were used to restrict the set of coherent hypotheses considered, with ties broken randomly. The remaining bar ( Coherence, Temporal, Comm ) presents the monitoring accuracy in each run using the combination of all techniques.

The results presented in Figure 5 demonstrate the effectiveness of the socially-attentive monitoring techniques we presented. First, the results show that the coherence heuristic brings the accuracy up by 15–30% without using any probabilistic reasoning. This boost in performance is a particularly interesting result, because of the relation between the coherence technique and previous techniques explored in the literature (Tambe, 1996; Intille & Bobick, 199). Previous work has successfully used the relationships between agents to increase the accuracy of monitoring. The boost in OVERSEER's accuracy based on the use of role and teamwork relationships confirms the results from previous investigations.  However, the results also demonstrate that the technique is not sufficient in this domain.

OVERSEER adds a number of novel techniques not addressed in previous work. The first such technique combines coherence with a temporal model of plan-duration ( Coherent ,
Temporal ), and it results in significant increases to the accuracy, because the probabilistic temporal information now allows OVERSEER to better handle the lack of observations. A possible alternative, which we explore in this evaluation, is to rely instead on the communications predictions to rule out hypotheses about future states that may or may not have ben reached ( Coherent, Comm ). It is therefore interesting to compare the performance of these two techniques by comparing the ( Coherent, Temporal ) and ( Coherent, Comm ) bars.

In almost all runs the average accuracy when using coherence and communications predictions is significantly higher than when using coherence and the temporal model. This is despite the fact that the more effective coherence technique uses arbitrary (random) selection among the available hypotheses: The reason for this is that in many cases the communication predictions are powerful enough to rule out all hypotheses but one or two, significantly decreasing the uncertainty of the agents' plan-horizons.  Thus even arandom selection stands a better chance than a more informed (by a temporal model) selection among many more
(10–20) hypotheses.

However, runs J and B show a reversal of this trend compared to the other runs. Figures 6a-b show the accumulative number of errors as task execution progresses during run I
(Figure 6-a) and during run J (Figure 6-b). An error is defined as a failure to choose the correct hypothesis as the most likely one (i.e., the most likely hypothesis does not reflect the true state of the agent/team). Each message exchange corresponds to one to a dozen messages communicated by the agents, establishing or terminating a plan. In the two figures, a lower slope means better performance (less errors). The line marked Coherent shows the accumulative number of errors if only coherence is used to select the correct hypothesismost su oices turn out to be erroneous since a random oice is made among the competing hypotheses. The line marked Coherent, Temporal shows the results using both coherence and the temporal model to choose the most likely hypothesis. Similarly, the line marked Coherent, Comm shows the results using both coherence and the communications predictions. Finally, the remaining line displays the results of using the combined technique, using coherence, the temporal model, and the communications predictions.

In Figure 6-a, we see that the two techniques ( Coherent, Temporal and Coherent, Comm )
have almost equal slopes and result in almost equal number of errors at the end of run I,