
| Individually    | Collectively   | Collectively         | Non-          |             |
|-----------------|----------------|----------------------|---------------|-------------|
| Observable      | Observable     | Partially Observable | Observable    |             |
| No Comm.        | P-complete     | NEXP-complete        | NEXP-complete | NP-Complete |
| General Comm    | P-complete     | NEXP-complete        | NEXP-complete | NP-Complete |
| PSPACE-complete |                |                      |               |             |
| Free Comm.      | P-complete     | P-complete           | NP-Complete   |             |

- On the other hand, when the world is individually observable or non-observable, communication makes no difference in performance.

- It should be noted that even under those conditions where the problem is P-complete, the complexity of optimal teamwork is polynomial in the number of states of the world, which may still be impractically high.

- The above complexity results pertain to finding policies that are optimal subject to the domain properties. We will find different expected rewards of the optimal policies under different observability and communication properties. For instance, cutting off all of the agents' sensors makes the domain non-observable and reduces the complexity of generating an optimal policy from NEXP to NP, but we would expect an associated drop in the expected reward achieved by the team.

## 4. Evaluating Team Coordination

Table 2 shows that providing optimal domain-level and communication policies for teams is a difficult challenge. Many systems alleviate this difficulty by having domain experts provide the domain-level plans (Tambe, 1997; Tidhar, 1993). Then, the problem for the agents reduces to generating the appropriate team coordination, παχ, to ensure that they properly execute the domain-level plans, παΑ . In this section, we demonstrate the COM-MTDP
framework's ability to analyze existing teamwork approaches in the literature.  Our methodology for such analysis begins by encoding such a teamwork method as a communicationlevel policy. In other words, we translate the method into an algorithm that maps agent beliefs (e.g., observation sequences) into communication decisions. To evaluate the performance of this policy, we then instantiate a COM-MTDP that represents the states, transition probabilities, and reward function of a domain of interest.  Our methodology provides an evaluation of the policy in terms of the expected reward earned by the team when following the policy in the specified domain.

We demonstrate this methodology by using our COM-MTDP framework to analyze joint intentions theory (Cohen & Levesque, 1991b, 1991a; Levesque et al., 1990), which provides a common basis for many existing approaches to team coordination. Section 4.1 models two key instantiations of joint intentions taken from the literature (Jennings, 1995; Tambe, 1997) as COM-MTDP communication policies. Section 4.2 analyzes the conditions under which these policies generate optimal behavior and provides a third candidate policy that makes communication decisions that are locally optimal within the context of joint intentions. In