setup, new experimental results, and additional discussion and explanations of key points. This research was supported by DARPA award No. F30602-98-2-0108, under the Control of Agent Based Systems program, and managed by AFRL/Rome Research Site. We would like to thank Daniel Bernstein, Ashish Goel, Daniel Marcu, Stacy Marsella, Ranjit Nair, and Paul Rosenbloom for valuable discussion and feedback. We also thank the anonymous reviewers for their helpful comments and suggestions.

## References

Bernstein, D. S., Zilberstein, S., & Immerman, N. (2000). The complexity of decentralized control of Markov decision processes. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp. 32-37.

Boutilier, C. (1996). Planning, learning and coordination in multiagent decision processes.

In Proceedings of the Conference on Theoretical Aspects of Rationality and Knowledge, pp. 195-210.

Boutilier, C., Dean, T., & Hanks, S. (1999). Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11, 1-93.

Cohen, P. R., & Levesque, H. J. (1991a). Confirmation and joint action. In Proceedings of the International Joint Conference on Artificial Intelligence.

Cohen, P. R., & Levesque, H. J. (1991b). Teamwork. Nous, 25 (4), 487–512. Decker, K., & Lesser, V. (1995). Designing a family of coordination algorithms. In Proceedings of the International Conference on Multi-Agent Systems.

Dunin-K eplicz, B., & Verbrugge, R. (1996). Collective commitments. In International Conference on Multi-Agent Systems, pp. 56-63.

Durfee, E., & Lesser, V. (1991). Partial global planning: a coordination framework for distributed planning. IEEE transactions on Systems, Man and Cybernetics, 21 (5).

Goldberg, D., & Mataric, M. J. (1997). Interference as a tool for designing and evaluating multi-robot controllers. In Proceedings of the National Conference on Artificial Intelligence, pp. 637-642.

Grosz, B. (1996).  Collaborating systems.  Artificial Intelligence  Magazine, 17 (2), 67–85.

Grosz, B., & Kraus, S. (1996). Collaborative plans for complex group actions. Artificial Intelligence, 86, 269-358.

Grosz, B. J., & Sidner, C. L. (1990).  Plans for discourse.  In Cohen, P. R., Morgan, J., & Pollack, M. E. (Eds.), Intentions in Communication, pp. 417-444. MIT Press, Cambridge, MA.

Ho, Y.-C. (1980).  Team decision theory and information structures.  Proceedings of the IEEE, 68(6), 644-654.

Jennings, N. (1995).  Controlling cooperative problem solving in industrial multi-agent systems using joint intentions. Artificial Intelligence, 75, 195–240.