belief state to incorporate new evidence about any variables, X t , and they can also compute the next time-tick's belief state, bt+1. We can extract the desired probability over planstate variables by examining the posterior probabilities stored in b . Given the dependency structure of our plan model, the space and time complexity of performing inference using this DBN (either incorporating a single observation, or computing b t +1 ) is O (2 M 2 ) for a single agent.

This DBN method is not sufficiently efficient to support on-line monitoring in real-world domains, since on each and every time step, the recognizer must perform an inferential step of exponential computational complexity. There exist single-agent plan-recognition techniques that avoid the exponential complexity of DBNs by using a representation and inference algorithms aimed at the particular properties of the plan-recognition task (e.g.,
Pynadath & Wellman, 2000). Such specialized representations avoid the full generality of DBNs, while still capturing a broad class of interesting planning agent models.  Given a specialized representation, the single-agent plan-recognition algorithms can exploit the particular structure of the plan models to achieve efficient online inference.

Drawing our inspiration from the success of this work in single-agent domains, we adopt a similar methodology in our multi-agent domain. In other words, we have developed a novel plan-recognition representation more suited to capturing team-oriented programs.  The structural assumptions we make in this representation support efficient inference with our specialized algorithms, as well as more naturally supporting an extension to represent interagent dependencies (as discussed in Section 4).

We represent the team-oriented plan as a directed graph, whose vertices are plans, and whose edges signify temporal and hierarchical decomposition transitions between plans: Children edges denote hierarchical decomposition of a plan into sub-plans.  Sibling edges denote temporal orderings between plans. Following the structure of the plan hierarchy, the variables {X t } form a directed connected graph, such that each node X t has at most one hierarchical-decomposition incoming transition from a parent node (representing its parent plan), and any number of temporal incoming transitions from plans that precede it in order of execution. The graph may contain multiple nodes for a single plan, if the plan is the potential child of multiple parent plans. The node may have any number of temporal outgoing transitions to immediate successor sibling nodes (representing plans that may follow it in order of execution), and any number of hierarchical-decomposition outgoing transitions to the node's first children (i.e., those that will be executed first by a decomposition of the plan X t . The graph forms a tree along hierarchical decomposition transitions, so that no plan can have itself as a descendent. On the other hand, there may be cycles along temporal transitions (to siblings). In other words, a plan may have an outgoing temporal transition to itself (meaning that it can be selected for execution again upon termination), or to a node that has a temporal path leading back to the plan (meaning that it is the first node in a temporal sequence of plans that may be executed repeatedly). It may also have two alternative temporal paths leading indirectly from one node to another.

To perform inference with this representation, we borrow the standard DBN inference algorithms' notion of a belief state, b t . As in the DBN case, the belief state represents the posterior probability distribution over the variables in time slice, t, conditioned on all of the observations made so far. In addition, for each plan, we distinguish between a state of actual execution and a blocked state, indicating that execution has terminated, but execution of