provided the motivation for exploring a plan-recognition approach.  As further evidence for the average case, consider the evacuation application, where agents communicate on average once every 20 state changes. In this application, agents communicate in parallel in 4 or 5 exchanges (out of dozens), but in all cases but one, such parallel communications all referred to the same plan, thus still requiring only a single update in YOYO* (see discussion in Section 5.2). Only once during task execution would 3 agents (out of 11) be expected to communicate in parallel about different plans, a scenario still different than YOYO*'s worst case scenario.

The average length of task execution in this domain is approximately 900 time-ticks.

The array approach would update the state of each agent, at each time tick, whether a message would appear or not. Thus its average complexity per time-tick is the same as its worst-case, which is at least O( MN 2 ). For YOYO*, the average complexity would be significantly different: 899 out of 900 time-ticks it would result in an O ( M + H ) process, and only one time (out of 900) it would be result in a process three times as expensive (updating the state of 3 different agents). The worst case scenario did not occur at all in any of the different runs.

## 7. Related Work

Aiello et al. ( 2001 ) present several benefits to overhearing agent conversations. They suggest that the overhearer may infer the intent of the agents engaged in conversations, and offer specific suggestions for improving the agents' performance.  For instance, overhearing a conversation between two agents about a keyword search on the web, the overhearer may suggest alternative keywords to conduct the same search. This work is closely related to our research on OVERSEER, and indeed points out several potential additional benefits of overhearing technology. However, in contrast to our work, Aiello et al. do not address the problem of intent- or plan-recognition. They do not present algorithms for inferring plans, nor for disambiguating recognized plans.

OVERSEER differs from most previous work on plan-recognition in being focused on monitoring multiple agents, not a single agent. While previous work in multi-agent plan recognition has either focused on exploiting explicit teamwork reasoning (e.g.,  Tambe, 1996), or explicitly reasoning about uncertainty when recognizing multi-agent plans (e.g.,
Devaney & Ram, 1998; Intille & Bobick, 1999), a key novelty in OVERSEER is that it effectively blends these two threads together. We provide a detailed discussion below.

Like OVERSEER, RESC,eam (Tambe, 1996) reasons explicitly about team intentions for inferring team plans from observations, similarly to OVERSEER's use of the coherence heuristic. RESC team uses coherence to restrict the space requirements of the plan-library used, similarly to YOYO*. However, OVERSEER uses a more advanced teamwork model
(e.g., it can predict failure states and recovery actions), uses knowledge about procedures used by a team (i.e., communication decisions), and also explicitly reasons about uncertainty and time, allowing it to answer queries related to the likelihood of current and future team plans (issues not addressed in RESC team ). Indeed, RESC team does not explicitly represent ordering constraints between plans, and does not address scarce observations: It assumes that observations are available that account for possible changes in the state of each of the observed agents.