Analyzing a quantitative coordination relationship

Coordination is a crucial behavior in cooperative distributed problem solving (CDPS). Analyzing coordination requires an understanding of the interplay between the agents, their problem, and their environment. The core behaviors ofdistributed coordination in CDPS systems are the coherent specification and scheduling of tasks over the set of distributed agents working on sets of interrelated problems. The complexity of, and uncertainty about, the problem interrelationships make distributed task coordination difficult. This article describes a causal model of this process that links the interrelationships, calledcoordination relationships, to the local scheduling constraints of distributed agents. Besides coordination relationships, environmental uncertainty and the lack of infinite computational resources also make distributed coordination difficult.It is not only the presence or absence of a coordination relationship that is important, but its quantitative properties: how likely is it to appear, how significant is its effect, and so on. These aspects determine the usefulness of a particular coordination relationship in the context defined by an environment, a problem to be solved, and an agent architecture. This article discusses the analysis of coordination relationships, using as an example our abstract model for thefacilitates relationship. We detail the derivation and assumptions of this model and apply it to the design of a generalized coordination module that is separate from, and interfaces cleanly with, the local scheduler of a CDPS agent. A set of simulation experiments is described that test our assumptions and design process in the coordination of a group of real-time problem-solving agents.