Evolution of the GPGP/TÆMS domain-independent coordination framework

ABSTRACT

Generalized Partial Global Planning (GPGP) and its associated TÆMS hierarchical task network representation were developed as a domain-independent framework for coordinating the real-time activities of small teams of cooperative agents working to achieve a set of high-level goals. GPGP's development was influenced by two factors: one was to generalize and make domain-independent the coordination techniques developed in the Partial Global Planning (PGP) framework (this also involved our understanding that coordination activities could be separated from local agent control if an appropriate bi-directional interface could be established between them); the other was based on viewing agent coordination in terms of coordinating a distributed search of a dynamically evolving goal tree. Underlying these two influences was a desire to construct a model that could be used to explain and motivate the reasons for coordination among agents based on a quantitative view of task/subproblem dependency. Coordination of behaviors among agents requires three things: specification (creating shared goals), planning (subdividing goals into subgoals/tasks, i.e., creating the substructure of the evolving goal tree) and scheduling (assigning tasks to individual agents or groups of agents, creating shared plans and schedules and allocating resources). GPGP is primarily concerned with scheduling activities rather than the dynamic specification and planning of evolving activities (e.g., such as decomposing a high-level goal into a set of subgoals that if successfully achieved will solve the high-level goals).

REFERENCES

• 1: [1] K. Decker and V. Lesser, "Generalizing The Partial Global Planning Algorithm," International Journal on Intelligent Cooperative Information Systems, 1(2):319- 346, 1992.
• 2: [2] K. Decker and V. Lesser, "Quantitative Modeling of Complex Environments," International Journal of Intelligent Systems in Accounting, Finance, and Management, 2(4):215-234, Special issue on Mathematical and Computational Models of Organizations: Models and Characteristics of Agent Behavior, 1993.
• 3: [3] K. Decker and V. Lesser, "Designing a Family of Coordination Algorithms," Proceedings of the First International Conference on Multi-Agent Systems, San Francisco: AAAI Press, pp. 73-80, 1995.
• 4: Keith Decker , Jinjiang Li, Coordinating Mutually Exclusive Resources using GPGP, Autonomous Agents and Multi-Agent Systems, v.3 n.2, p.133-157, June 2000 [doi>10.1023/A:1010074611407]
• 5: [5] E. H. Durfee and V. R. Lesser, "Partial Global Planning: A Coordination Framework for Distributed Hypothesis Formation," IEEE Transactions on Systems, Man, and Cybernetics, 21(5):1167-1183, 1991.
• 6: Barbara J. Grosz , Sarit Kraus, Collaborative plans for complex group action, Artificial Intelligence, v.86 n.2, p.269-357, Oct. 1996 [doi>10.1016/0004-3702(95)00103-4]
• 7: [7] Bryan Horling, et al. "The TÆMS White Paper," Technical Notes of Multi-Agent Systems Lab, Department of Computer Science, University of Massachusetts, 1999.
• 8: N. R. Jennings, Controlling cooperative problem solving in industrial multi-agent systems using joint intentions, Artificial Intelligence, v.75 n.2, p.195-240, June 1995 [doi>10.1016/0004-3702(94)00020-2]
• 9: [9] V. Lesser, K. Decker, T. Wagner, N. Carver, A. Garvey, B. Horling, D. Neiman, R. Podorozhny, M. Nagendra Prasad, A. Raja, R. Vincent, P. Xuan, and XQ. Zhang, "Evolution of the GPGP/TÆMS Domain-Independent Coordination Framework," University of Massachusetts/Amherst Computer Science Technical Report #02-03, 2002. ftp://mas.cs.umass.edu/pub/EvolGPGP_TR0203.ps.gz
• 10: M. V. Nagendra Prasad , Victor R. Lesser, Learning Situation-Specific Coordination in Cooperative Multi-agent Systems, Autonomous Agents and Multi-Agent Systems, v.2 n.2, p.173-207, June 1999 [doi>10.1023/A:1010059125034]
• 11: [11] M. V. NagendraPrasad, K. S. Decker, A. Garvey, V. R. Lesser, "Exploring Organizational Designs with TÆMS: A case study of distributed data processing," in Proceedings of the Second International Conference on Multi-Agent Systems, 1997.
• 12: [12] M. Tambe, "Towards Flexible Teamwork," Journal of Artificial Intelligence Research, Volume 7, pp. 83-124, 1997.
• 13: [13] T. Wagner, A. Garvey, V. R. Lesser, "Criteria Directed Task Scheduling," International Journal of Approximate Processing, Special Issue on Scheduling, 19:91-118, 1998.
• 14: Thomas Wagner , Brett Benyo , Victor R. Lesser , Ping Xuan, Investigating Interactions between Agent Conversations and Agent Control Components, Issues in Agent Communication, p.314-330, January 2000
• 15: Ping Xuan , Victor R. Lesser, Incorporating Uncertainty in Agent Commitments, 6th International Workshop on Intelligent Agents VI, Agent Theories, Architectures, and Languages (ATAL),, p.57-70, July 15-17, 1999
• 16: [16] X. Q. Zhang, R. Podorozhny, and V. R. Lesser, "Cooperative, MultiStep Negotiation Over a Multi-Dimensional Utility Function," in Proceedings of the IASTED International Conference, Artificial Intelligence and Soft Computing (ASC 2000), IASTED/ACTA Press, pp. 136-142, 2000.
• 17: XiaoQin Zhang , Anita Raja , Barbara Staudt Lerner , Victor R. Lesser , Leon J. Osterweil , Thomas Wagner, Integrating High-Level and Detailed Agent Coordination into a Layered Architecture, Revised Papers from the International Workshop on Infrastructure for Multi-Agent Systems: Infrastructure for Agents, Multi-Agent Systems, and Scalable Multi-Agent Systems, p.72-79, June 03-07, 2000
• 18: Anita Raja , Victor Lesser , Thomas Wagner, Toward robust agent control in open environments, Proceedings of the fourth international conference on Autonomous agents, p.84-91, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337054]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents; Multiagent systems

General Terms:
Algorithms