The downward propagation (line 25) implements a subtle but critical step: It re-aligns any beliefs YOYO* maintains about subteams other than those implied by the message so that these beliefs are made coherent with existing evidence. The SCALE procedure, which re-distributes the new state probability of a parent among its children, such that each child gets scaled based on its relative weight in the parent.  The end result is that the state probabilities of the children are made to sum up to the state probability of the parent. The process is recursive, but never re-visits a subtree, since it is only carried out for hierarchicaldecomposition transitions that were not previously updated.

Once this downward propagation is done, YOYO* updates the current team to be its parent in the team-hierarchy, in line 26. Note that the call to parentteam reflects a lookup in the team-hierarchy H , rather than the plan-hierarchy M . Finally, regardless of whether downward propagation took place, the temporary variable P is updated to climb up the hierarchical decomposition in M (line 27).

Ea iteration through the loop begun on line 17 is O ( M + H ) since in the worst case both the plan-hierarchy and team-hierarchy are traversed. However, this loop many repeat
(in the worst case) for each of the plans in the plan-hierarchy, and thus overall, the run-time complexity of this process is O ( M + H )) = O ( M 2 + M H ).

An example run of YOYO*.  The following example illustrates YOYO*'s inference upon an observation of a message. Suppose a single member of the TRANSPORT subteam communicates that it is initiating the Transport-Ops plan. Upon observing this message, YOYO* looks up the sender, to determine what transitions can be taken by it (line 8).  It then proceeds to determine the new beliefs in team T's execution of the Transport-Ops plan (lines 9–10, then 16), and incorporates these new beliefs to reflect a much increased belief that the TRANSPORT subteam is executing Transport-Ops and its children (lines 18–19). Since this plan's parent, Landing-Zone-Maneuvers, is not null, YOYO* enters the loop in lines 2–27. First, it increases the belief in the execution of the parent (line 23). Then, it checks the condition on line 24: Indeed, the team that is to execute Landing-Zone-Maneuvers is TEAM-FLY-OUT, the parent of the TRANSPORT subteam (i.e., Landing-Zone-Maneuvers is to be executed jointly by the TRANSPORT and ESCORT subteams). YOYO* therefore calls the SCALE procedure (line 25) to re-adjust Landing-Zone-Maneuvers' other children subtrees. Landing-Zone-Maneuvers has two hierarchical-decomposition children:
Transport-Ops (which YOYO* has already updated) which is to be executed by the TRANSPORT subteam, and Escort-Ops, which is to be executed by the ESCORT subteam.

SCALE climbs down from Landing-Zone-Maneuvers to Escort-Ops , increasing YOYO*'s beliefs that the ESCORT team is executing the Escort-Ops plan. This process re-aligns any prior beliefs YOYO* had about the likelihood that Escort-Ops was being executed with current evidence, in effect updating beliefs about the plans executed by the ESCORT subteam, based on a single observation made of a member of the TRANSPORT team. The process now repeats this loop until the entire set of beliefs is updated and aligned with respect to the observed message.

## 5.2 Scalability In The Number Of Agents

YO * offers significant computational advantages when compared to the individual representation (array) approach. YOYO* requires only a single, fully-expanded plan-hierarchy