Publication - Designing a Family of Coordination Algorithms

Authors: Decker, K. and Lesser, V.
Title: Designing a Family of Coordination Algorithms
Abstract: Many researchers have shown that there is no single best organization or coordination mechanism for all environments. This paper discusses the design and implementation of an extendable family of coordination mechanisms, called Generalized Partial Global Planning (GPGP). The set of coordination mechanisms described here assists in scheduling activities for teams of cooperative computational agents. The GPGP approach has several unique features. First, it is not tied to a single domain. Each mechanism is defined as a response to certain features in the current task environment. We show that different combinations of mechanisms are appropriate for different task environments. Secondly, the approach works in conjunction with an agent’s existing local planner/scheduler. Finally, the initial set of five mechanisms presented here generalizes and extends the Partial Global Planning (PGP) algorithm. In comparison to PGP, GPGP schedules tasks with deadlines, it allows agent heterogeneity, it exchanges less global information, and it communicates at multiple levels of abstraction. We analyze the performance of several GPGP algorithmfamily members and one centralized upper bound reference algorithm, using data from simulations of multiple agent teams working in abstract task environments. We show how to decide if adding a new mechanism is useful, and suggest a way to prune the search for an appropriate combination of mechanisms in an environment.
Keywords: Coordination, GPGP, Multi-Agent Systems
Publication: Proceedings of the First International Conference on Multi-Agent Systems (ICMAS-95), pp. 73 - 80
Publisher: AAAI Press
Date: January 1995
Sources: PS: ftp://ftp.cs.umass.edu/pub/lesser/decker-94-14.ps
PDF: /Documents/lesser/decker-94-14.pdf
Reference: 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. January 1995.
bibtex: 
@article{Decker-30,
  author    = "K. Decker and V. Lesser",
  title     = "{Designing a Family of Coordination Algorithms}",
  journal   = "Proceedings of the First International Conference
               on Multi-Agent Systems (ICMAS-95)",
  publisher = "AAAI Press",
  pages     = "73-80",
  month     = "January",
  year      = "1995",
  url       = "http://mas.cs.umass.edu/paper/30",
}