ENVIRONMENT CENTERED ANALYSIS AND DESIGNOF COORDINATION MECHANISMS

MAY 1995

KEITH S. DECKER

B.S., CARNEGIE MELLON UNIVERSITY

M.S., RENSSELAER POLYTECHNIC INSTITUTE

Ph.D., UNIVERSITY OF MASSACHUSETTS AMHERST

Directed by: Professor Victor R. Lesser

Committee: Professors Paul Cohen, Jack Stankovic, Douglas Anderton

Coordination, as the act of managing interdependencies between activities, is one of the central research issues in Distributed Artificial Intelligence. 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, TAEMS, to directly represent the salient features of a computational task environment. The unique features of TAEMS 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.