An Approach to Analyzing the Need for Meta-Level Communication

1 Introduction

Organizational theorists have long held that the organization of a set of agents cannot be analyzed separately from the agents' task environment, that there is no single best organization for all environments, and that different organizations are not equally ef­ fective in a given environment [Galbraith, 1977]. Most of these theorists view the uncertainties present in the environment as a key characteristic, though they differ in the mechanisms that link environmental uncertainty to effective organization. In particular, the transaction cost uonomics approach [Moe, 1984] focuses on the r~lativ~ 4Jicimci~s of various organizations given an uncertain environment, while the modern contingency ih~ory approach [Stinchcombe, 1990] focuses on the need for an orga­ nization to expand toward the earliest available information that r~solv~s unc"tainti~s in the current environment.

·This work was supported by DARPA contract NOOO 14-92-j-1698, Office of Naval Research contract N00014-92-J-1450, and NSF con­ tract CDA 8922572. The content of the information does no't nec­ essarily reflect the position or the policy of the Government and no official endorsement should be inferred.

2 Task Environment Model

Our task environment model of naturally distributed problems assumes that several independent groups of computational tasks arrive at multiple locations over a period of time called an ~isode. For example, in a distributed sensor network (DSN) episode the movements of several independent vehicles will be detected over a period of time by one or more distinct sensors, where each sensor is associated with an agent. The performance of agents in such an environment will be based on how long it takes them to process all the task groups necessary to interpret their sensed data, which will include the cost of communicating data, task results, and meta-level communication, if any. The orga­ nizational structure of the agents will imply which subsets of which task groups are available to which agents and at what cost. For example, if DSN agents have overlapping sensors, either agent can potentially work on data in the overlapping area (from its own sensor) without any extra communication costs. We make several simplifying assumptions: that the agents are homogeneous (have the same capabilities with respect to receiving data, communicating, and processing tasks), that the agents arc cooperative (interested in maximizing the system per­ formance over maximizing their individual performance), that the data for each episode is available simultaneously to all agents as specified by their initial organization, and that there are only structural <rrccedence) constraints within the subtasks of each task group.

Any single episode can be specified by listing the task groups, and what part of each task group was available to which agents, given the organizational structure. Our analysis will be based on the statistical properties of episodes in an environment, not any single instance of an episode. The properties of the episodes in a DSN environment are summarized by the tuple 'D =< A, 111 r, o, T > where A specifies the number of agents, 11 the expected number of task groups, r and o specify the structural portion of the organization by the rangt of each agent and the ovtrlap between agents, and T specifies the homogeneous task group structure (Section 2.5 and Figure 4 describes how task group structures are specified).

Our analysis initially focuses on what a priori knowledge agents have about the distribution of task groups in an episode. First we will look at the distribution of the lowest-level sensor subtasks of a single task group among multiple agents (deriv­ ing the maximum expected number of subtasks), and then we will look at the distribution of task groups themselves. These results will then be used in subsequent sections to derive the total amount of work, and therefore expected termination per­ formance, under various organizational structures and control schemes.

2.1 Task environment simulation

In the next sections and for the rest of the paper, we will test the model we are developing against simulated DSN problems. Each simulated DSN episode will take place on a grid where the concepts of length and size correspond directly to physi­ cal distances. For example, Figure 1 illustrates several simple organizations imposed on such a grid in our simulation.

In the simulation we assume that each vehicle is sensed at discrete integer locations (as in the DVMT), randomly entering on one edge and leaving on any other edge. In between the ve­ hicle travels along a track moving either horizontally, vertically, or diagonally each time unit using a simple DDA line-drawing algorithm (see Figure 5). In an 18 X 18 grid, the (empirical) average length of a track is 14 units-the actual length of any one track will range from 2 to 19 units and is not distributed normally. Given the organization (r, o, ,and A, and the geom­ etry), we can calculate what locations arc seen by the sensors of each agent. This information can then be used along with the locations traveled by each vehicle to determine what part of each task group is initially available to each agent. Section 2.5 will detail what the structure of each task group is for the DSN simulation.

1 ln general there are usually more complex interrelationships be­ tween subtasks that affect scheduling decisions, such as facilitation [Decker and Lesser, 1993b].

2.2 Expected number of sensor subtasks

In order to analyze the performance of a particular organization, we will want to know what proportion of each task group each agent is likely to process. There will be some upper limit on this proportion (related to the agent's range r), and sometimes the agent will process less than this upper limit. Especially in static organizational structures where tasks are not exchanged, the termination of the system as a whole can be tied to the com­ pletion of all tasks at the most heavily loaded agent. Normally, we would use the avtragt part of a task group to be seen, but since the focus of our analysis is the termination of problem solving, we need to examine the txptcttd maximum portion of a task group to be seen. This section will develop an equation for the expected maximum workload at an agent by counting the expected number of low-level sensor subtasks (each individually associated with a sensed vehicle location) that the maximally loaded agent will have.

The amount of a single task group seen by an agent (which is the same as the number of sensor subtasks in the DSN example) can be viewed as a random variable S with a probability density function and corresponding cumulative distribution function. In the DSN environment, S is discrete, and its probability function (determined empirically) is heavily weighted toward r (the maximum). To simplify the analysis, instead of letting S correspond to the number of subtasks in a single task group seen by an agent, we have it equal 1 if the agent sees the maximum amount, and 0 otherwise. Now S has a Bernoulli (coin-tossing) distribution with parameter p corresponding to the chance of an agent seeing the maximum amount r of a task group. Let's assume we know that N ~ n is the number of task groups at the maximally loaded agent, and that on average a ~ A agents see a single task group. The number of times an agent sees the maximum out of N task groups (N coin Aips) then has a binomial distribution (bN,p(s)). We need to know, given that a agents each Aip N coins, what the distribution is of the maximum number of 'heads' any agent sees-this is called the binomial max order statistic, 9a,N,p(B):

In the DSN example we have p = 0.5 (empirical) and the amount of a task group seen when an agent does not see the max­ imum amount averages r /2 (empirical). The expected heaviest load seen by any agent when a agents see N task groups with a probability p of seeing r and probability 1 - p of seeing r /2 is:

Figure 2 demonstrates the correc~ess ofEq. 1 by showing the heaviest load actually observed in th~imulation plotted against the expected value from Eq. 1, for I 000 runs with n tracks and all square DSN organizations [2 ~ r ~ 10,0 ~ o ~ r, 1 ~ VA~ 10, 1 ~ N ~ 10] (R 2 > .99).

2.3 Expected Number of Task Groups

Given the maximum number of task groups seen by an agent (N), we can calculate the expected heaviest agent load using Eqn. I. But this begs the question of what is the maximum number of task groups an individual agent will see, given the actual (n) or expected number (71) that the entire system will see. The solution is similar-each agent either sees or does not see each of the n task groups, another binomial process. Let Ni be the number of task groups sensed by agent i, with a binomial distribution of parameters n and q. If a is again the number of agents that see a single task group and A the total number of agents, then q = aj A, the probability that each agent will see a particular track. By the same derivation as in the last section, the max order statistic Nn has the probability function 9A,n,a/A { 8 ), and expected value:

Figure 3 shows the actual mean value of the maximum number of tracks seen by an agent over I 000 runs of the DSN simula­ tion, versus the predicted value, for n tracks and square DSN organizations [2 ~ r ~ 10, 1 ~ VA~ 10, 1 ~ n ~ 10] without any overlap (R 2 > .99)

2.4 Expected Number of Agents

The only remaining term we need to analyze before deriving an expression for system performance is a, the expected number of agents that will see a single task group. In general, a will depend on the total number of agents A and the organization (r and o). When there is only one agent, it will see every task group (a= I). When the agents overlap completely, every agent sees every task group ([o = r] - [a = A]). When the agents in a square environment do not overlap, a = v'A. The relationship follows the ratio of the area solely covered by an agent plus the area of the overlapping section, to the total area covered alone:

Figure 3 shows a regression of the actual average value of a over I 000 runs verses the predicted value for all 630 DSN organiza­ tions [2 ~ r ~ 10,0 ~ o ~ r,1 ~VA~ 10] (R 2 > .99).

2.5 Work Involved in a Task Structure

Finally we turn to modeling the performance of the system as a whole, which is based on the structure of the tasks involved. We have developed a characterization of task environments that formally captures the range of features, processes, and especially interrelationships that occur during computationally intensive coordination and scheduling [Decker and Lesser, I993bl. The model of environmental and task characteristics we propose has three levels: objtctivt, subjtctivt, and gtntrativt; the subjective level is not discussed here.

The objtctivt level describes the essential structure of a partic­ ular problem-solving situation or instance over time. It focuses on how task interrelationships dynamically affect the quality and duration of each task. In this paper we will concentrate only on duration as a performance metric. The basic model is that task groups T occur in the environment at some frequency, and in­ duce tasks to be executed by the agents under study. Task groups are independent of one another, but tasks within a single task group have interrelationships. An individual task that has no subtasks is called a mtthod M and is the smallest schedulable chunk of work. The quality and duration of an agent's per­ formance on an individual task is a function of the timing and choice of agent actions ('local effects'), and possibly previous task executions ('non-local effects'). The basic purpose of the objective model is to formally specify how the execution and timing of tasks affect quality and duration.

At the lowest level, each method (leaf task) M at time t can produce, if executed, some maximum quality q{M, t) in some amount of time d{M, t) (each method has an initial maximum quality Qo{M) and duration do{M)). Any task execution that starts before the execution of M completes may potentially affect M's execution through non-local qficts. The effect is dependent on the relative timing of the two task executions, the quality of the task cawing the effect, and whether information was transmitted between the two tasks.

This work considers a single non-local effect, prtcuknct. If task A precedes task B, then the maximum quality q(B, t) = 0 until A is completed and the result is available, when the maximum quality will change to the initial maximum quality q{B, t) = qo{B).

2.5.1 Execution Model

For this paper we we an extremely simple model of execution. Agents can perform three actions: method execution, commu­ nication, and information gathering. The control component of an agent determines the next action an agent will perform based on the agent's current set of beliefs [Cohen and Levesque, 1990; Shoham, 1991]. A method execution action, of method M, that is begun at timet will conclude at timet+ d(M, t). An in­ formation gathering action has duration do{!) and updates the agent's set of beliefs with any new information in the environ­ ment, for example, the arrival of data at the start of an episode, or communications from other agents. A communication action has duration do(C) and, after a communication delay, makes information (such method execution results) available to other agents .. The agent on the receiving side must perform an infor­ mation gathering action before the communication can affect its local beliefs.

2.5.2 Simple Objective DSN Model

Recall that the summary of a DSN environment was the tuple 'D =< A, 7] 1 r, o, T >; this will become our generative model, especially the parameter 7J (expected number of task groups). A particular episode in this environment can be described by the tuple D =< A, r, o, 1j 1 ··· , Tn > where n is a random variable drawn from an unknown distribution with location parameter (central tendency) of7]. Note that we make almost no assumptions about this distribution; its characteristics will differ for different environments. For example, in the description of our DSN simulation early in Section 2 we noted the physical process by which vehicle tracks were generated and that the length of the tracks was not normally distributed.

Each task group '1i is associated with a track of length l; and has the same basic objective structure, based on the DVMT:

• l; Vehicle Location Methods (VLM's) that represent pro­ cessing raw signal data at a single location to a single vehicle location hypothesis.
• l; - 1 Vehicle Tracking Methods (VTM's) that represent short tracks connecting the results of the VLM at time t with the results of the VLM at time t + 1.
• 1 Vehicle Track Completion Method (VCM) that repre­ sents merging all the VTM's together into a complete ve­ hicle track hypothesis.

Non-local precedence effects exist between each method at one level and the appropriate method at the next level as shown in Figure 4-two VLMs precede each VTM, and all VTM'S precede the lone VCM.

If we assume that each VLM has initial duration do{VLM) and each VTM has the initial duration do{VTM), then we can see from the task structure that for each task group the total execution time taken by a single processor agent will be:

This task structure is a simplification of the real DVMT task structure. For example, there is no sensor noise (which will cause facilitation relationships between tasks, and there is no confusion caused by 'ghost tracks'. Adding these features to the task strucn~;re will cause some interesting phenomena that we will discuss briefly in the conclusions (see also [Decker and Lesser, 1993b] for a representation of these extensions).

3 Static vs. Dynamic Organizational Structures

Now we have the necessary background to analyze static and dynamic organizational structures. The key to static structures is to divide up the overlap area a priori (rather than to penalize agents for doing redundant work in the overlap area [Durfee tt aL, 1987]). The key to dynamic organizational structures is to transfer tasks so that all the agents' resources are used efficiently. We will repeat the assumptions we discussed at the start of Section 2 on page 2: the agents are homogeneous, cooperative, the data for each episode arrives in a single burst, and the only non-local effect is precedence.

3.1 Analyzing Static Organizations

In a static organization, agents divide the overlapping areas of their ranges as evenly as possible. The result is a new area of responsibility r' = r - ! for each agent with no overlap (see Figure 5). 2 Given the task structure as described in Section 2.5 and shown in Figure 4, and any raw data or communicated task results provided by information gathering actions, the agent can at any time build a list of currently executable methods (under the set of precedence constraints). Also, at any time an agent can build a list of methods that need to be executed, but cannot . be executed because their precedence constraints have not yet been met. The communication action in this algorithm is a broadcast of the highest level results of all the task groups an agent has worked on. Each agent follows the same control algorithm (remember, all the raw data is available at the start) and terminates when all task groups arc completed (either locally or by reception of the result from another agent):

2 The reason for overlap will be apparent in dynamic structures­ multiple agents can work in an overlapping area without paying any cost for communicating raw data between them. Overlap can also provide redundancy in case of agent failure.

(Repeat

Do Information-Gathering-Action (Repeat Let E · [grt s~t of currmtly o«cutabk m~thodsJ (For method In E Do Method-Execution-Action(method)) Until (null E))

Do Communication-Action(broadcast highest-level results) Let W · [gtt stt of mtthods waiting on prt!ctdmct constraints] Until (null W))

In the environment 'D =< A, 1]1 r, o, T >. if we let S' represent the largest amount of initial low-level data in one task group seen by any agent, and a the total number of agents that see the task group (from Eqn. 3), then the amount of time it will take that agent to construct a complete solution is equal to the amount of time it will take for the initial information gathering action (do (I)) plus the amount of time to do all the local work (S'do(VLM) + (S'- 1)do(VfM)), communicate that work ( do(C)), get the other agents' results (do(!)), plus the amount of time to combine results from the other a - 1 agents ((a- 1)do(VfM)), plus time to produce the final complete task group result ( d 0(VCM)), plus communicate that result to everyone (do(C)). For simplicity we will assume that do(I) and do( C) arc constant and do not depend on the amount of data. Note that the maximally loaded agent will be the last to finish any local work.

If the system sees n total task groups, then the expected size of the initial low-level data set at the maximally loaded agent can be derived from the marginal expected value for S given the joint distribution of SN (Eqn. 1) and Nn (Eqn. 2):

Similar to the single task group case, the total time until ter­ mination for an agent receiving an initial data set of size S is the time to do local work, combine results from other agents, and build the completed results, plus two communication and information gathcrtng actions: .

We can use Eq. 6 as a predictor by combining it with the proba­ bilities for the values of Sand N given in Eq. 5 (i.e., substitute Eq. 6 for (rs + I(N- s)) in Eq. 5).

We tested these predictions of Eqn. 6 versus the mean termi­ nation time of our DSN simulation over 10.rcpetitions in each of 43 randomly chosen environments from the design space [2 S r S 10,0 S o S r, 1 S VA S 5, 1 S N S 10). The du­ rations of all tasks were set at 1 time unit, as were the duration of information gathering and communication actions. We used the simulation validation statistic suggested by Klcijncn [Klcij­ nen, 1987] (where y = the predicted output by the analytical model andy = the output of the simulation):

where Var(y) is the predicted variance. 3 The result z can then be tested for significance against the standard normal tables. In each case, we were unable to reject the null hypothesis that the actual mean termination equals the predicted mean termination at the o = 0.05 level. 4 Figure 6 shows the mean of 10 rep­ etitions in each environment versus the expected value and its confidence intervals. Regression of the measured and predicted values results in R 2 = 0.96 . .

3.2 Control Costs

The control algorithm presented above is simple and not neces­ sarily optimal. By communicating only when there is no local work to be done, the heaviest-loaded agent gives up the chance for other agents to do the high-level composition in a task group by incrementally transmitting partial results, a maximum potential savings of(N- 1)(a- 1)do(VfM) + (N- 1)do(VCM). However, this needs to be balanced with the cost of multiple communication actions, which is (N- 1)do(C). Thus 'when to communicate' rests directly on the cost of communication relative to (a- 1)do(VfM) + do(VCM) (which depends on both the basic method durations and the agents' organizational structure). This simple control algorithm can be analyzed easily, unlike many other systems where control costs arc ignored. If we view the cost of control as the time spent by an agent when not performing an action (executing a method, information gath­ ering, communication), then our algorithm runs in constant time between actions except for the two tests fgtt stt of cu"tntiy e«cutabk methods] and fgtt stt of methods sti/J waitiniJ. Each of these in the worst case requires a constant-time test of each clement of the full task structure, which is of size O(qr). Thus we sec how the control costs, too, arc related to organizational structure.

3 The predicted variance of qn. 6 can be easily derived from the statistical identityVar(z) = E[zl)- (E[zJ)l.

4 For non-statisticians: this is a good thing. The null hypothesis is that our prediction is the same as the actual value, we did not wish to reject it, and we did not.

3.3 Analyzing Dynamic Organizations

In the dynamic organizational case, agents are not limited to the original organization and initial distribution of data. Agents can reorganize by changing the initial static boundaries (changing responsibilities in the overlapping areas), or by shipping raw data to other agents for processing (load balancing).

In the case of reorganized overlapping areas, agents may shift the initial static boundaries by sending a (very short) message to overlapping agents, telling the other agents to do all the work in the overlapping areas. The effect at the local agent is to change its effective range parameter from its static value of r' = r- o/2 to some valuer" where r- o/2 2:: r" 2:: r- o, changing the first two terms of Eqn. 6, and adding a communication action to indicate the shift and an extra information gathering action to receive the results. Another paper [Decker and Lesser, 1993a] discusses a particular implementation of this idea that chooses the partition of the overlapping area that best reduces expected differences between agent's loads and averages competing desired partitions from multiple agents.

In the second case, an agent communicates some proportion p of its initial data to a second agent, who does the associated work and communicates the results back. Instead of altering the effective range and overlap, this method directly reduces the first two terms ofEqn. 6 by the proportion p. The proportion p can be chosen dynamically in a way similar to that of choosing where to partition the overlap between agents (see [Decker and Lesser, 1993a]).

Whether or not a dynamic reorganization is ·useful is a func­ tion of both the agent's local utility and also the load at the other agent. We will again be concentrating on the agent with the heaviest load. Looking first at the local utility, to do local work under the initial static organization with n task groups, the heaviest loaded agent will take time:

When the static boundary is shifted before any processing is done, the agent will take time:

to do the same work, where Cshon is a very short communication action which is potentially much cheaper than the result com­ munications mentioned previously, and S" is calculated using r". When balancing the load directly, local actions will take time:

where do(C~a 01 ) is potentially much more expensive than the communication actions mentioned earlier (since it involves send­ ing a large amount of raw data). If the other agent had no work to do, a simple comparison between these three equations would be a sufficient design rule for deciding between static and either dynamic organization.

4 Using Meta-Level Communication

For some environments 'D =< A, "11 r, o, T > one of the three organizational choices may be dearly better in the long run, but for most environments the choice is not so dear given the variance in system performance. The choice that optimizes per­ formance over the long run is often not optimal in any particular episode. Taking the equations for local work in Section 3.3 along with Eqn. 5, we can compute confidence intervals on the pre­ dicted performance of an organization under each of the three coordination regimes by combining the local confidence interval on the expected load of the heaviest loaded agent, and the con­ fidence interval on the average agent load. These results, for the 50o/o confidence interval, are shown in Figures 7 and 8. Again we have assumed that all execution, communication, and infor­ mation gathering action durations have the same value (making communication relatively expensive). The first figure, Figure 7, highlights how the relationship between performance under a static organization and a dynamically load balanced organiza­ tion changes as the number of agents increases. As expected, load balancing becomes more desirable as the number of agents increases (in relation to the average number of tracks): when there are many agents, the average agent load becomes very low, which offsets the cost of transferring tasks. In this figure the per­ formance difference between static and overlap reorganization remains nearly constant relative to the number of agents.

The second, Figure 8, points out how dynamically reorga­ nizing the overlap area increases the performance over static organization as the amount of overlap increases. For this graph we assumed that the agents would shrink their entire area of responsibility (as opposed to minimizing the difference in max­ imum versus average work as described in [Decker and Lesser, 1993a]). This graph shows the need for dynamically calcu­ lating the shrinkage parameter (p) especially at high levels of overlap (note how the dynamically reorganized organization is predicted to do worse at high levels of overlap in the n = 20 portion). The expected performance difference between the static organization and load balancing remains relatively con­ stant across changing values of o. In both figures we have let do(C) = do(Cmon) = do(C1 001 ); changing these values will move the corresponding curves directly up or down.

These figures bring us to the final point of this paper: often system performance can be improved significantly by dynamic reorganization, but it will rarely always be improved. There­ fore, meta-level communication between agents about their lo­ cal loads can, with a small communication cost, pinpoint the true costs and benefits of the various organizational structures, allowing an informed organizational decision to be made. In­ stead of an agent making a decision about restructuring or load balancing by assuming the avn-agt load, the agent will have the actual load for the neighboring agents. As we said in the in­ troduction, the proper organization is often one that exploits information that rtsolvts uncn-taintits about the current environ­ ment as it becomes available to the agents, allowing the agents to then create the most efficient organization for the situation.

5 Conclusions

The results of this paper can be looked at from three points of view. From the practitioner's viewpoint, the analysis presented here resulted in a set of design equations that can be used directly to optimize the performance of a simple DSN, or explore the design space given some model of how expensive agents are and what bounds {mean, median, 90o/o quantile) on their perfor­ mance are required. Several of the simplifying assumptions we used, such as constant communication and information gather­ ing costs, can be easily replaced with submodels chosen by the designer. From the viewpoint of the distributed AI community, we have returned to look at the some of the problems first stud­ ied by Durfee, Lesser, and Corkill [Durfee tt a/., 1987]. They concluded that "Our intent is to show that overly specialized organizational structures allow effective network performance in particular problem-solving situations, but that no such orga­ nization is appropriate in all situations." In this paper we reach the same abstract conclusion, but also show precisely what the effect is of a particular organizational structure (characterized by both its structural components and its coordination algo­ rithm) in an environment (characterized by the structure and frequency of its tasks) in a clear way that not only allows us to predict performance but to explain it. The technique of using binomial approximations should also prove useful in different domains. From the viewpoint of the general research commu­ nity this paper presents a methodology for answering questions about the design of a system by analysis and simulation. In such a methodology, the observation of particular phenomena in a complex system {the DVMT) leads to the building and verifica­ tion of general models that predict and explain such phenomena.

In the short term, this work leads to the explanation of other interesting distributed problem solving phenomena displayed in [Durfee tt al, 1987]. The addition of noise at DSN sensors leads to the necessity of more complex coordination with the introduction of more complex task interrelationships (such as facilitation [Decker and Lesser, 1993b]). The addition of corre­ lated noise in the environment can then cause these new, more complex coordination mechanisms to break down, producing the phenomenon recognized as distraction. In the long term, we are working towards a complete characterization of generalized partial global planning [Decker and Lesser, 1992] as a first step towards a theory of coordination in distributed problem solving.

A longer technical report version of this paper is available from the authors.