The main cause for this low accuracy is the scarcity of observations, one of the identifying characteristics of monitoring by overhearing. As previously discussed, agents often switch their state unobservably (i.e., without sending a message).  Therefore, the monitoring system critically needs to estimate correctly the times at which agents switch state.  Since some agents rarely communicate (i.e., there are very few observations about them), variance in their temporal behavior (with respect to the system's predictions) tends to cause large errors in monitoring.

To address this issue, we bring back for discussion the agent independence assumption which we have made in the previous section. After all, team-members do not communicate independently of each other. Communication in a team is an action that is intended to change the state of a listener (Cohen & Levesque, 1990). Agents that only rarely send a message may still change their state upon receiving a message. In other words, although observed messages are used in the previous section to update the belief in the state of the sender, they could also be used to update the state of any listeners. To do this, the monitoring system must know about the relationships between the team-members.

Knowledge of the social structures enables additional sophisticated forms of monitoring.

For instance, in order to maintain their social structures, team-members communicate with each other predictably, during particular points in the execution of a task. Such predictions of future observable behavior—communications—can be used to further reduce the uncertainty. However, it is often the case that while it can be difficult to correctly predict that a specific agent will communicate at a specific point in task execution, it is easy to predict that some team-member will. Knowledge of the procedures employed by a team to maintain its social structures can be very useful allows a monitoring system to make such predictions.

To reason about the effects of communications on receivers, and about future observable behavior of team-members, a monitoring system must utilize knowledge of the social structures and social procedures used by team-members to maintain these structures.

Such exploitation of social knowledge for monitoring is called Socially-Attentive Monitoring
(Kaminka & Tambe, 2000). This section discusses these concepts in detail.

## 4.1 Exploiting Social Structures

While computationally cheap, the approach described earlier proved insufficient in the evacuation domain. In monitoring by overhearing tasks, the monitoring system must address scarce observations, as agents rarely communicate all at the same time. Indeed, in the evacution application, only a single message was observed (on average) for every 20 combined individual state changes.

Under such challenging conditions, a system for monitoring by overhearing must come to rely extensively on its ability to estimate when agents change their internal state without sending a message. The representation presented earlier used a simple, but efficient, temporal model to do this, based on the estimated average duration of plans. However, we have found high variance in the actual duration of plan execution, compared to the duration predicted by the average-duration model:
G Plan execution times vary depending on the external environment. For instance, when all the agents in the team are running on a local network, their response times to queries