to represent the entire team. This hierarchy is a union of all the individual agent planhierarchies, containing all transitions and plans, tagged by the subteams that are allowed to execute them. In addition YOYO* uses a single copy of the team hierarchy. Suppose M is the size of the plan-hierarchy, H is the size of the team-hierarchy, and N the number of agents in the team. When agents are added to the monitored team, the team hierary grows by one new node that represents the new agent, and is connected to the appropriate sub-team in the team hierarchy. YOYO*'s space complexity is therefore O ( M + H ). Since H grows with N , we could write it O ( M + N ) (compare to the array approach: O ( M N ), Algorithm 4).

To analyze YOYO*'s run-time complexity, we have to consider the behavior of Algorithm 5 separately in cases where no communications are observed, and in cases where at least one message is observed. If no messages are observed, then an update takes the form of a single call to T EAM -P ROPAGATE -F ORWARD (Algorithm 7), an O ( M ) process. This is clearly a best-case scenario for YOYO*. If one agent communicates, then YOYO* would have to go through M and H in its upward-downward propagation process only once, thus O(M + H) = O(M + N).

The worst case scenario for YOYO* occurs if all agents send messages, and each one of these N messages refers to a different plan (messages about the same plans would be merged in lines 5–7). In this case, there would be up to M different plans for which evidence exists, and each one of them would require a separate update through lines 17–27. Thus YOYO*'s run-time complexity in this case is

## O(N + M + M + M (M + H)) = O(N + M² + Mh) = O(N + M² + Mn)

Clearly, this worst-case cannot be continuously sustained by a monitored team, since agents cannot continuously communicate about their state. We thus believe that the average case in real-world domains with many agents would be mu closer to the O ( M + N ) case presented earlier (see Section 6.4 for empiric evaluation). In any case, YOYO*'s complexity compares favorably with a procedure reasoning about coherent hypotheses using an array of recognizers, an O ( M N 2 ) process (at least), even if only one agent communicates (Section 4.1).

## 5.3 Discussion

YOYO* explicitly represents a team as a single coherent entity. Its space and run-time requirements are preferable to the array based approach when the number of agents grow, and it considerably simplifies reasoning about coherence and communications predictions. On the other hand, YOYO* sacrifices the capability to represent failing team activities (incoherent hypotheses), where one team-member is executing one team-plan while its teammate is executing another. This does not at all mean that individual actions taken by agents are somehow locked together in synchronous execution, or that individual agents must all execute the same individual action at the same time. For instance, two team-members A, B
that are each executing a completely different path of execution at the same time (i.e., plan steps A 1 , ..., A k and B 1 , ..., B l ) can be easily represented by a plan hierarchy that includes an overall joint plan J , having two first hierarchical decomposition children, A 1 and B 1 , to