represented using a single recognizer instead of an array of recognizers, offering considerable scalability in team monitoring. However, since the algorithm can no longer represent certain hypotheses, this scalability comes at the expense of expressivity. We discuss the scalable representation and the trade-off it offers below.

## 5.1  Efficient  Reasoning  With Team  Coherence

Coherence is a very strong constraint, since for a team of agents there are only a linear number ( O ( M ) where M is the size of the plan-hierarchy) of coherent hypotheses, but an exponential number of incoherent hypotheses ( O ( M N ) where N is the number of agents; the proof is in Appendix A). We can exploit this property by designing monitoring algorithms that reason only about the linear number of coherent hypotheses, and therefore offer better scalability as the number of agents increases. Such algorithms may not be able to reason about incoherent hypotheses, and are therefore less expressive. However, Section 6 demonstrates that the level of accuracy even with such limited expressiveness is sufficient for our purposes. Furthermore, algorithms that reason only about coherent hypotheses may still be able to detect incoherent hypotheses, representing a failure state in which two or more team-members are in disagreement with each other.

We begin by presenting the YOYO* algorithm, an efficient technique for reasoning about coherent hypotheses (Algorithm 5). YOYO* replaces the array-based algorithm described earlier (Algorithm 4). Similarly to it, YOYO* is called every time tick. If no message is observed, the state of the entire team is propagated forward in time.  Otherwise, all observed messages are collected together and used as evidence for the (different) plans implied by these messages.

YOYO*'s key novelty is that it relies on a single plan-hierarchy that is used to represent all team-members together (regardless of their number), instead of an array of such structures. In other words, each variable X t represents O V E S E R ' s belief that all agents in the teams associated with X (as described in the team-oriented program) are executing the plan X at time t. Thus YOYO* makes extensive use of the information associating plans and transitions in M with teams and subteams in H , the team-hierarchy. The team hierarchy plays a critical bookeeping role in this respect, since it maintains the knowledge critical for correctly applying coherence in the single recognizer.

This key distinction between YOYO* and the array-based approach causes a subtle, but critical, difference in the way probabilities are propagated along transitions. In a planhierarchy M of an individual agent, part of an array of such models, ea outgoing transition represented a hierarchical decomposition or temporal step that the agent is allowed to take.

Alternative outgoing transitions therefore represent alternative paths of execution available to the agent.  On the other hand, in a plan-hierarchy M used by YOYO*, alternative outgoing transitions tagged by different subteams (that are not ancestors of one another)
represent not a decision point for the agent, but alternative paths of execution as decided by the agents' roles and team-memberships.

This creates a critical difference in how the values of πχγ and μχγ are to be interpreted.

Where previously (in Section 3) the value of π xy referred to the probability that a specific agent will take a transition X → Y (given that it has terminated execution of X ), in YOYO* it refers to the probability that an entire team will take the transition together.