Publication - Environment Centered Analysis and Design of Coordination Mechanisms

Authors: Decker, K.
Title: Environment Centered Analysis and Design of Coordination Mechanisms
Abstract: Coordination, as the act of managing interdependencies between activities, is one of the central research issues in Distributed Artificial Intelligence. Many researchers have shown that there is no single best organization or coordination mechanism for all environments. Problems in coordinating the activities of distributed intelligent agents appear in many domains: the control of distributed sensor networks; multi-agent scheduling of people and/or machines; distributed diagnosis of errors in local-area or telephone networks; concurrent engineering; ‘software agents’ for information gathering. The design of coordination mechanisms for groups of computational agents depends in many ways on the agent’s task environment. Two such dependencies are on the structure of the tasks and on the uncertainty in the task structures. The task structure includes the scope of the problems facing the agents, the complexity of the choices facing the agents, and the the particular kinds and patterns of interrelationships that occur between tasks. A few examples of environmental uncertainty include uncertainty in the a priori structure of any particular problem-solving episode, in the actions of other agents, and in the outcomes of an agent’s own actions. These dependencies hold regardless of whether the system comprises just people, computational agents, or a mixture of the two. Designing coordination mechanisms also depends on properties of the agents themselves. Our thesis is that the design of coordination mechanisms cannot rely on the principled construction of agents alone, but must also rely on the structure and other characteristics of the agents’ task environment. For example, the presence of both uncertainty and high variance in a task structure can lead to better performance in coordination algorithms that adapt to each problem-solving episode. Furthermore, the structure and characteristics of an environment can and should be used as the central guide to the design of coordination mechanisms, and thus must be a part of our eventual goal, a comprehensive theory of coordination, partially developed here. Our approach is to first develop a framework, TÆMS, to directly represent the salient features of a computational task environment. The unique features of TÆMS include that it quantitatively represents complex task interrelationships, and that it divides a task environment model into generative, objective, and subjective levels. We then extend a standard methodology to use the framework and apply it to the first published analysis, explanation, and prediction of agent performance in a distributed sensor network problem. We predict the effect of adding more agents, changing the relative cost of communication and computation, and changing how the agents are organized. Finally, we show how coordination mechanisms can be designed to respond to particular features of the task environment structure by developing the Generalized Partial Global Planning (GPGP) family of algorithms. GPGP is a cooperative (team-oriented) coordination component that is unique because it is built of modular mechanisms that work in conjunction with, but do not replace, a fully functional agent with a local scheduler. GPGP differs from other previous approaches in that it is not tied to a single domain, it allows agent heterogeneity, it exchanges less global information, it communicates at multiple levels of abstraction, and it allows the use of a separate local scheduling component. We prove that GPGP can be adapted to different domains, and learn what its performance is through simulation in conjunction with a heuristic real-time local scheduler and randomly generated abstract task environments.
Keywords: GPGP, TAEMS
Publication: Ph.D. Thesis, Department of Computer Science, University of Massachusetts, Amherst
Date: May 1995
Sources: PS: ftp://ftp.cs.umass.edu/pub/lesser/decker-thesis.ps.gz
PDF: /Documents/lesser/decker-thesis.pdf
Reference: Decker, K.. Environment Centered Analysis and Design of Coordination Mechanisms. Ph.D. Thesis, Department of Computer Science, University of Massachusetts, Amherst. May 1995.
bibtex: 
@article{Decker-27,
  author    = "K. Decker",
  title     = "{Environment Centered Analysis and Design of
               Coordination Mechanisms}",
  journal   = "Ph.D. Thesis, Department of Computer Science,
               University of Massachusetts, Amherst",
  month     = "May",
  year      = "1995",
  url       = "http://mas.cs.umass.edu/paper/27",
}