Generic Coordination Strategies for Agents

Note: The GPGP coordination research has progressed a great deal and these pages are out of date. We are working on revising them. In the mean time, please consult the "Reflections" or "Evolution of GPGP" papers below.

Summary: The partial global planning (PGP) approach to distributed coordination improved the coordination of agents in a network by scheduling the timely generation of partial results, avoiding redundant activities, shifting tasks to idle nodes, and indicating compatibility between goals. PGP achieved this by recognizing certain coordination relationships among tasks in the Distributed Vehicle Monitoring Testbed (DVMT) environment and producing the appropriate scheduling constraints. We have focused on generalizing the partial global planning mechanism. This process involved identifying and generalizing the types of coordination relationships that were used by the basic PGP algorithm, developing a conceptual model that clearly specifies the role of a PGP-style coordination algorithm as identifying coordination relationships and producing behaviors (primarily the creation and refinement of local scheduling constraints), and generalizing the partial global planning algorithm itself (GPGP). GPGP is a coordination algorithm described in a modular, domain independent way and and can be tuned for particular intra-task environment behavior. In addition, GPGP extends (as well as generalizes) the PGP algorithm along two lines. The first extension is that the algorithm reacts appropriately to real-time deadlines. The second extension is that GPGP has a more 'partially global' planning character that supports distributed search among schedulers in a more give-and-take manner than the partially 'global planning' PGP.

Many researchers have shown that there is no single best organization or coordination mechanism for all environments. We view GPGP as an extendable family of coordination mechanisms that form a basic set of mechanisms for teams of cooperative computational agents. The important features of this approach include a set of modular coordination mechanisms (any subset or all of which can be used in response to a particular task environment); a general specification of these mechanisms involving the detection and response to certain abstract {\em coordination relationships\/} in the incoming task structure that are not tied to a particular domain; and a separation of the coordination mechanisms from an agent's local scheduler that allows each to better do the job for which it was designed. We have also investigated the interactions between these mechanisms and how to decide when each mechanism should be used, drawing data from simulation experiments of multiple agent teams working in abstract task environments.

Other pages to consult:

• The Design-to-Criteria Scheduler that performs scheduling and analysis of TAEMS task structures and is being used in the GPGP-prime project.

• The BIG Information Gathering Agent that integrates different ai problem solvers using TAEMS as a medimum of exchange; and the related multi-agent information gathering project, CIG, which will employ GPGP technology.

• The Survivable Systems Projet and the related simulator project both of which use TAEMS and GPGP.

• The TAEMS Task Modeling Framework

• The schedule coordination problem

• Some details on GPGP

• Using TAEMS to model DSN environments

Related Publications

Sims, Mark; Mostafa, Hala; Horling, Bryan; Zhang, Haizheng; Lesser, Victor; Corkill, Dan. Lateral and Hierarchical Partial Centralization for Distributed Coordination and Scheduling of Complex Hierarchical Task Networks. AAAI 2006 Spring Symposium on Distributed Plan and Schedule Management. 2006.

Lesser, V.; Decker, K.; Wagner, T.; Carver, N.; Garvey, A.; Horling, B.; Neiman, D.; Podorozhny, R.; NagendraPrasad, M.; Raja, A.; Vincent, R.; Xuan, P.; Zhang, X.Q. Evolution of the GPGP/TAEMS Domain-Independent Coordination Framework. Autonomous Agents and Multi-Agent Systems, Volume 9, Number 1, Kluwer Academic Publishers, pp. 87-143. 2004. This is a revised version of the paper that appeared in Proceedings 1st International Conference on Autonomous Agents and Multi-Agent Systems, 2002.

Lesser, V.; Decker, K.; Wagner, T.; Carver, N.; Garvey, A.; Horling, B.; Neiman, D.; Podorozhny, R.; NagendraPrasad, M.; Raja, A.; Vincent, R.; Xuan, P.; Zhang, X.Q. Evolution of the GPGP/TAEMS Domain-Independent Coordination Framework. Proceedings 1st International Conference on Autonomous Agents and Multi-Agent Systems (Plenary Lecture/Extended Abstract), pp. 1-2. 2002. The full version is available as University of Massachusetts/Amherst Computer Science Technical Report 02-03.

XiaoQin Zhang, Anita Raja, Barbara Lerner. Integrating High-Level and Detailed Agent Coordination into a Layered Architecture. The workshop on Infrastructure for Scalable Multi-Agent Systems, Agents 2000. Also available as UMass Computer Science Technical Report 1999-029.. 2000.

Wagner, Thomas and Lesser, Victor. Toward Generalized Organizationally Contexted Agent Control. Proceedings of the AAAI-99 Workshop on Reasoning in Context, a version also available as UMASS CS Tech Report TR99-18, AAAI Press, pp. 101-105. 1999.

Wagner, Thomas; Shapiro, Jonathan; Xuan, Ping; Lesser, Victor. Multi-Level Conflict in Multi-Agent Systems. Proceedings of the AAAI-99 Workshop on Negotiation in MAS , AAAI Press, pp. 50-55. 1999. Also available as UMASS CS Tech Report 99-17

Lesser, V., Decker, K., Carver, N., Garvey, A., Neiman, D., Nagendra Prasad, M., and Wagner, T.. Evolution of the GPGP Domain-Independent Coordination Framework. University of Massachusetts/Amherst CMPSCI Technical Report 98-05. 1998.

Lesser, Victor. Reflections on the Nature of Multi-Agent Coordination and Its Implications for an Agent Architecture. Autonomous Agents and Multi-Agent Systems, Volume 1, Kluwer Academic Publishers, pp. 89-111. 1998.

Decker, K.. Environment Centered Analysis and Design of Coordination Mechanisms. Ph.D. Thesis, Department of Computer Science, University of Massachusetts, Amherst. 1995.

Decker, K.; Lesser, V.. Coordination Assistance for Mixed Human and Computational Agents. Proceedings of Concurrent Engineering 95, pp. 337-348. 1995. Available as UMASS Computer Science Department Technical Report 95-31

Decker, K. and Lesser, V.. Designing a Family of Coordination Algorithms. Proceedings of the First International Conference on Multi-Agent Systems (ICMAS-95), AAAI Press, pp. 73-80. 1995.

Decker K. and Lesser, V.. Communication in the Service of Coordination. AAAI Workshop on Planning for Interagent Communication. 1994.

Decker, K. and Lesser, V.. Analyzing a Quantitative Coordination Relationship. Group Decision and Negotiation Special Issue on Distributed AI, Volume 2. 1993.

Decker, K. and Lesser, V.. Generalizing the Partial Global Planning Algorithm. International Journal on Intelligent Cooperative Information Systems, Volume 1, Number 2, pp. 319-346. 1992.

Durfee, E.H. and Lesser, V.R.. Partial Global Planning: A Coordination Framework for Distributed Hypothesis Formation. IEEE Transactions on Systems, Man, and Cybernetics, Volume 21, Number 5, pp. 1167-1183. 1991.

Durfee, Edmund, and Lesser, Victor. Using Partial Global Plans to Coordinate Distributed Problem Solvers. Proceedings of the Tenth International Joint Conference on Artificial Intelligence, pp. 875-883. 1987.