approach) was already presented in Section 5.2, and we follow it here with empirical evaluation. Figure 9 reports on the space requirement of YOYO* and the array-based approach in three different domains: the evacuation domain, where YOYO* has been evaluated and deployed, and two additional domains in which we have built multi-agent teams—ModSAF (Tambe et  al., 1995; Calder, Smith, Courtemanche, Mar, & Ceranowicz, 1993) and RoboCup (Tambe, Adibi, Al-Onaizan, Erdem, Kaminka, Marsella, & Muslea, 1999; Marsella, Adibi, Al-Onaizan, Kaminka, Muslea, Tallis, & Tambe, 2001).  YOYO* is currently being evaluated in these domains, and while it has not yet been fully deployed there, we believe the partial existing implementations are sufficient to provide robust projections of the space savings achieved in these domains.  We believe that such projected savings of implementation in these two domains could provide a rough guide as to the savings that designers could expect from deploying YOYO* in additional domains.

For each domain, Figure 9 compares the space requirements of the array-based approach
(left bar) with those of YOYO* (right bar). In addition, the dark-shaded region on top of each bar shows the space required for representing each additional agent in the two approaches, under the assumption that no additional plans are added to the plan-hierarchy as more agents are added. As discussed above, this assumption is favorable to the arraybased representation. The figure shows the significant space savings achieved by YOYO*. First, in representing the teams in their current size, YOYO*'s space requirements are significantly smaller.  Furthermore, YOYO*'s savings really shine when we examine the scalability of the two approaches. While the array-based approach requires at least the amount of space shown in the figure as darkly-shaded area, YOYO*'s requirements grow by one node with each additional agent. Its space requirements for representing additional agents are so small, that they don't show in the figure.

![0_image_0.png](0_image_0.png)

Earlier, in Section 5.2, we have analyzed YOYO*'s worst case run-time complexity, but argued that this worst case behavior is very extreme, and cannot be sustained in practice since it involves continuous communications among all agents, the infeasibility of which