The Use of Meta-level Information in Learning Situation-Specific Coordination

1 Introduction

Coordination is the act of managing interdependencies in a multi-agent system[Decker & Lesser, 1995]. Achieving ef­ fective coordination in a multi-agent system (MAS) is a dif­ ficult problem for a number of reasons. An agent's local control decisions about what activity to do next or what in­ formation to communicate and to whom or what information to ask others may be inappropriate or suboptimal due its lim­ ited view of the interactions between its own activities and those of the other agents. In order to make more informed control decisions, the agents have to acquire a view of the task structures of other agents. To the extent that this resolves agents' uncertainty about the non-local problem solving ac­ tivities, they can act coherently. However, an agent has to expend computational resources in acquiring and exploiting such non-local views of other agents' activities. This involves communication delays and the computational cost of provid­ ing this information and assimilating the information from other agents. Given the inherent uncertainty in agents' activ­ ities and the cost of meta-level processing, relying on sophis­ ticated coordination strategies to acquire non-local views of task structures may not be worthwhile for all problem-solving situations[Durfee & Lesser, 1988; Decker & Lesser, 1995; Nagendra Prasad et al., 1996]. For example, when the agents are under severe time pressure and the load of the activities at the agents is high, it is often difficult for them to rearrange their local activities so that they can exploit the results generated by other agents or to generate results that the other agents can exploit. In these situations, sophisticated agent coordination strategies may not pay-off. In this paper, we will be dealing with how agents can learn to dynamically choose the appro­ priate coordination strategy in different coordination problem instances. We empirically demonstrate that even for a narrow class of agent activities, learning to choose an appropriate coordination strategy based on meta-level characterization of the global problem solving state outperforms using any single coordination strategy across all problem instances.

*This material is based upon work supported by the National Science Foundation under Grant Nos. IRI-9523419. The content of this paper does not necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred.

In order to accomplish learning, we break the coordination problem into two phases. In the first phase, the agents ex­ change meta-level information not directly used for coordina­ tion. This information is used by the agents to derive a predic­ tion of the effectiveness of various coordination mechanisms in the present problem solving episode. These mechanisms differ in the amount of non-local information they acquire and use, and in the complexity of analysis of interactions between activities at the agents. Agents choose an appropriate subset of the coordination mechanisms (or a coordination strategy) based on the meta-level information and enter Phase II. In this phase, the coordination strategy decides the types of informa­ tion to be exchanged and the kind of reasoning about local and non-local activities the agents perform to achieve coherent ac­ tivity. We call the meta-level information a situation and the two phase process situation-specific coordination. Learning situation-specific coordination involves associating appropri­ ate views of the global situation with the knowledge learned about the effectiveness of the coordination mechanisms.

The rest of the paper is organized as follows. After placing our work in context, we briefly review the TIEMS task structure representation for coordination problems. We then describe our learning algorithm that learns to choose among three coor­ dination modes of different levels of sophistication. We then present some of our experimental results and conclude.

2 Related Work

Much of the literature in multi-agent learning relies on re­ inforcement learning and classifier systems as learning al­ gorithms. In Sen, Sekaran and Hale[Sen, Sekaran, & Hale, 1994] and Crites and Barto[Crites & Barto, 1996], the agents do not communicate with one another and an agent treats the other agents as a part of the environment. Weiss[Weiss, 1994] uses classifier systems for learning appropriate multi-agent hi­ erarchical organization structuring relationships. In Tan[Tan, 1993], the agents share perception information to overcome perceptual limitations or communicate policy functions. In Sandholm and Crites[Sandholm & Crites, 1995] the agents are self-interested and an agent is not free to ask for any kind of information from the other agents. The MAS that this paper deals with contain complex cooperative agents (each agent is a sophisticated problem solver) and an agent's local problem solving control interacts with that of the other agents' in in­ tricate ways. In our work, rather than treating other agents as a part of the environment and learning in the presence of increased uncertainty, an agent tries to resolve the uncertainty about other agents' activities by communicating meta-level information to resolve the uncertainty to the extent possible (there is still the environmental uncertainty that the agents cannot do much about). In cooperative systems, an agent can "ask" other agents for any information that it deems relevant to appropriately situate its learned local coordination knowl­ edge. Agents sharing perceptual information as in Tan[Tan, 1993] or bidding information as in Weiss[Weiss, 1994] do not make explicit the notion of situating the local control knowledge in a more global abstract situation. The infor­ mation shared is weak and they are studied in domains such as predator-prey[Tan, 1993] or blocks world [Weiss, 1994] where the need for sharing meta-level information and situat­ ing learning in it is not apparent.

Sugawara and Lesser[Sugawara & Lesser, 1993] also rec­ ognize the need for situation specificity in learning coordina­ tion, though they do have the notion of two phase coordination. They are concerned with learning to make the situations more discriminating to avoid using an inappropriate coordination strategy in the domain of distributed network diagnosis. Their learning relies on deep domain knowledge and agent homo­ geneity assumptions to Jearn to progressively refine situations based on failure-driven explanation and comparative analysis of problem solving traces. They test the theory on very lim­ ited number of coordination situations and the evidence was anecdotal. It is not clear how such knowledge-intensive learn­ ing can be generalized to other instances without significant knowledge engineering and the development of more sophis­ ticated explanation-based learning techniques. Despite these limitations, combining their work on learning situation repre­ sentations with the learning presented here on situation-based choice of coordination could have interesting implications for situation-specific learning.

3 Task Analysis, Environment Modeling, and Simulation

3.1 TAEMS

The TJEMS framework (Task Analysis, Environment Model­ ing, and Simulation) [Decker & Lesser, 1993] represents co­ ordination problems in a formal, domain-independent way. A TJEMS model of a task environment specifies what actions are available to agents and how those actions relate to one another and to the performance of the system as a whole. A

coordination problem instance is represented as a task group T. Each task group has an arrival time Ar(T), and a deadline D(T). A task group, consisting of a set of computationally related actions, is represented by a directed acyclic graph. The quality of a task Tat a particular timet (Q(T, t)) is a function of the quality of its subtasks (in this paper this function is either minimum(AND-Iike) or maximum(OR-Iike)). Quality is used as a catch-all term representing acceptability char­ acteristics like certainty, precision completeness, other than temporal characteristics. Leaf tasks are called methods M and they represent domain actions, such as executing a blackboard knowledge source, running an instantiated plan, or executing a piece of code with its data. Executable methods have base level quality and duration. A task may have multiple ways to accomplish it, represented by multiple methods, that trade off the time to produce a result for the quality of the result.

Besides tasks/subtask relationships, there can be other inter­ relationships between tasks in a task group[Decker & Lesser, 1993]. In this paper, we will be dealing with two such inter­ relationships:

• facilitates relationship or soft interrelationship: If the results of execution of Task A are available for Task B before it starts executing, then Task B will have increased quality and/or decreased duration.
• enables relationships or hard interrelationship: Task A must be executed before Task B can be executed.

A design-to-time scheduling[ Garvey & Lesser, 1993] algo­ rithm heuristically enumerates a promising subset of quality and time trade-offs to produce schedules that maximize qual­ ity given the deadlines. In a cooperative multi-agent system, the goal of the agents is to work together to produce the highest possible quality for as many task groups as possible.

3.2 Environment-Specific Coordination Mechanisms

In order to bring to bear different collections of coordination mechanisms for different multi-agent problem-solving envi­ ronments, we use the Generalized Partial Global Planning (GPGP) approach[Decker & Lesser, 1995]. GPGP consists of several coordination mechanisms, each of which notices cer­ tain features in its local partial view of the task structures of other agents and their relationship with its own task structure and responds by taking certain communication or information gathering actions, or by proposing new commitments to other agents. In GPGP, a coordination strategy can be derived by activating a subset of the coordination mechanisms. Specifi­ cally we will be investigating the effect of three coordination strategies:

Balanced (or dynamic-scheduling): Agents coordinate their actions by dynamically forming commitments. Relevant re­ sults are generated by specific times and communicated to the agents to whom corresponding commitments are made. Agents schedule their local tasks trying to maximize the ac­ crual of quality based on the commitments made to it by the other agents, while ensuring that commitments to other agents are satisfied. The agents have the relevant non-local view of the coordination problem, detect coordination relationships, form commitments and communicate the committed results.

Data Flow Strategy: An agent communicates the result of performing a task to all the agents and the other agents can exploit these results if they still can. This represents the other extreme where there are no commitments from any agent to any other agent.

Rough coordination: This is similar to balanced but com­ mitments do not arise out of communication between agents but are known a priori. Each agent has an approximate idea of when the other agents complete their tasks and communicate results based on its past experience. "Rough commitments" are a form of tacit social contract between agents about the completion times of their tasks.

The latter two coordination strategies are the alternatives normally used in the distributed data processing domain[Na­ gendraPrasadetal., 1996]. [Decker&Lesser, 1995]proposed balanced as a sophisticated strategy that exploits a number of mechanisms to achieve coordination.

4 COLLAGE: Learning Coordination

4.1 Learning Coordination

Our learning algorithm, called COLLAGE, uses abstract meta-level information about coordination problem instances to learn to choose, for the given problem instance, the ap­ propriate coordination strategy from the three strategies de­ scribed previously. Learning in COLLAGE (COordination Learner for muLtiple AGEnt systems) falls into the category oflnstance-Based Learning algorithms[Aha, Kibler, & Albert, 1991] originally proposed for supervised classification learn­ ing. We, however, use the IBL-paradigm for unsupervised learning of decision-theoretic choice.

Learning involves running the multi-agent system on a large number of training coordination problem instances and ob­ serving the performance of different coordination strategies on these instances. When a new task group arises in the envi­ ronment, each of the agents has its own partial local view of the task group. Based on its local view, each agent forms a local situation vector. A local situation represents an agent's assessment of the utility of reacting to various characteris­ tics of the environment. Such an assessment can potentially indicate how to activate the various GPGP mechanisms and consequently has a direct bearing on the type of coordination strategy that is best for the given coordination episode. The agents then exchange their local situation vectors and each of the agents composes all the local situation vectors into a global situation vector. All agents agree on a choice of the coordination strategy and the choice depends on the kind of learning mode of the agents:

Mode 1: In this mode, the agents run all the available co­ ordination strategies and note their relative performances for the each of the coordination problem instances. Thus, for example, agents run each of data-flow, rough, and balanced for a coordination episode and store their perfor­ mances for each strategy.

Mode 2: In this mode, the agents choose one of the coordina­ tion strategies for a given coordination episode and observe and store the performance only for that coordination strat­ egy. They choose the coordination that is represented the least number of times in the neighborhood of a small radius around the present global situation. This is done to obtain a. balanced representation for all the coordination strategies across the space of possible global situations.

Mode 2 is quasi-online algorithm. In the initial stages it just explores and in the later stages it just exploits the learned information. A more typical online learning algorithm inter­ leaves exploration and exploitation. Studying COLLAGE in this kind of a setup is high on our agenda of future work.

At end of each run of the coordination episode with a selected coordination strategy, the performance of the system is registered. This is represented as a vector of four performance measures: total quality, number of meth­ ods executed, number of communications, and termina­ tion time. Learning involves simply adding the new in­ stance formed by the performance of the coordination strat­ egy along with the associated problem solving situation to the "instance-base". Thus, the training phase builds a set of {situation, coordination_strategy, performance} triplets for each of the agents. Here the global situation vector is the abstraction of the global problem solving state associ­ ated with the choice of a coordination-strategy. Note that at the beginning of a problem solving episode, all agents commu­ nicate their local problem solving situations to other agents. Thus, each agent aggregates the local problem solving situ­ ations to form a common global situation. All agents form identical instance-bases because they build the same global situation vectors through communication.

Forming a Local Situation Vector

The situation vector is an abstraction of the coordination prob­ lem and the effects of the coordination mechanisms in GPGP. It is composed of six components:

(a) The first component represents an approximation of the ef­ fect of detecting soft coordination relationships on the quality component of the overall performance. An agent creates vir­ tual task structures from the locally available task structures by letting each of the facilitates coordination relation­ ships potentially affecting a local task to actually take effect and calls the scheduler on these task structures. In order to achieve this, the agent detects all the facilitates interre­ lationships that affect its tasks. An agent can be expected to know the interrelationships affecting its tasks though it may not know the exact tasks in other agents that affect it without communicating with them. The agent then produces another set of virtual task structures, but this time with the assumption that the facilitates relationships are not detected and hence the tasks that can potentially be affected by them are not affected in these task structures. The scheduler is again called with this task structure. The first component, repre­ senting the effect of detecting facilitates is obtained as the ratio of the quality produced by the schedule without facilitates relationships and the quality produced by the schedule with fac i 1 ita tes relationships.

(b) The second component represents an approximation of the effect of detecting soft coordination relationships on the duration component of the overall performance. It is formed using the same techniques discussed above for quality but using the duration of the schedules formed with the virtual task structures.

(c) The third and fourth components represent an approxima­ tion of the effect of detecting hard coordination interrelation­ ships on the quality and duration of the local task structures at an agent. They are obtained in a manner similar to that described for facilitates.

(e) The fifth component represents the time pressure on the agent. In a design-to-time scheduler, increased time pressure on an agent will lead to schedules that will still adhere to the deadline requirements as far as possible but with a sac­ rifice in quality. Under time pressure, lower quality, lower duration methods are preferred over higher quality, higher du­ ration methods for achieving a particular task. In order to get an estimate of the time pressure, an agent generates vir­ tual task structures from its local task structures by setting the deadlines of the task groups, tasks and methods to oo (a large number) and scheduling these virtual task structures. The agents schedule again with local task structures set to the actual deadline. Time pressure is obtained as the ratio of the schedule quality with the actual deadlines and the schedule quality with large deadlines.

(f) The sixth component represents the load. It is obtained as the ratio of execution time under actual deadline and the execution time under no time pressure. It is formed using methods similar to that discussed above for time pressure but using the duration of the schedules formed with the virtual task structures.

In the work presented here, the cost of scheduling is ignored and the time for scheduling is considered negligible compared to the execution time of the methods. However, more sophis­ ticated models would need to take into consideration these factors too. We view this a one of our future directions of research.

Forming a Global Situation Vector

Each agent communicates its local situation vector to all other agents. An agent composes all the local situation vectors: its own and those it received from others to form a global situa­ tion vector. We can have a number of composition functions but the one we used in the experiments reported here is sim­ ple: component-wise average of the local situation vectors. Thus the global situation vector has six components where each component is the average of all the corresponding local situation vector components.

For example, one global situation vector looks as fol­ lows: (0.82 0.77 0.66 0.891.0 0.87).Herethe low value of the third component represents large quality gains by detecting and coordinating on hard interrelation­ ships. Thus two of the more sophisticated coordination strategies called balanced and tough[Decker & Lesser, 1995] are found to be better performers in this situation. On the other hand, in a global situation vector such as (0.80 0.90 0.88 0.80 0.61 0.69) thelowvalues of fifth and sixth components indicate high time pressure and load in the present problem solving episode. Even ifthe agents use sophisticated strategies to coordinate, they may not have the time to benefit from it. Hence, relatively simple coordina­ tion strategies likes imple or mu te[Decker & Lesser, 1995] do better in this scenario.

Note, however, that in most situation vectors, these tradeoffs are subtle and not as obvious as the above examples. It is difficult for a human to look at the situations and easily predict which strategy is the best performer. Hence, hand-coding the strategies by a designer is not a practical alternative.

4.2 Choosing a Coordination Strategy

COLLAGE chooses a coordination strategy based on how the set of available strategies performed in similar past cases. We adopt the notation from Gilboa and Schmeidler[Gilboa & Schmeidler, 1995]. Each case cis triplet

where p E P and P is the set of situations representing abstract characterization of coordination problems, a E A and A is the set of coordination choices available, r E R and R is the set of results from running the coordination strategies.

Decisions about coordination strategy choice are made based on similar past cases. Outcomes decide the desirability of the strategies. We define a similarity function and a utility function as follows:

In the experiments presented later, we use the Euclidean metric for similarity.

The desirability of a coordination strategy is determined by a similarity-weighted sum ofthe utility it yielded in the similar past cases in a small neighborhood around the present situa­ tion vector (in our experiments, the neighborhood radius was heuristically set to 0.05). We observed that such an averaging process in a neighborhood around the present situation vector was more robust than taking the nearest neighbor. Let M be the set of past similar cases to problem Pnew E P (greater than a threshold similarity).

For a E A, let Ma. = {m = (p,a,r) E Mia= a}. The utility of a is defined as

5 Experiments

5.1 Experiments in the DDP domain

Our experiments on learning coordination were conducted in the domain of distributed data processing[Nagendra Prasad et al., 1996]. This domain consists of a number of geographi­ cally dispersed data processing centers (agents). Each center is responsible for conducting certain types of analysis tasks on streams of satellite data arriving at its site: "routine anal­ ysis" that needs to be performed on data coming in at regular intervals during the day, "crisis analysis" that needs to be per­ formed on the incoming data but with a certain probability and "low priority analysis", the need for which arises at the beginning of the day with a certain probability. Low priority analysis involves performing specialized analysis on specific archival data. Different types of analysis tasks have different priorities. A center should first attend to the "crisis analysis tasks" and then perform "routine tasks" on the data. Time permitting, it can handle the low-priority tasks. The process­ ing centers have limited resources to conduct their analysis on the incoming data and they have to do this within certain deadlines. Results of processing data at a center may need to be communicated to other centers due the interrelation­ ships between the tasks at these centers. [Nagendra Prasad et at., 1996] developed a graph-grammar-based stochastic task structure description language and generation tool for mod­ eling task structures arising in a domain such as this. They present the results of empirical explorations of the effects of varying deadlines and crisis task group arrival probability. Based on the experiments, they noted the need for different coordination strategies in different situations to achieve good performance. In this section, we intend to demonstrate the power of COLLAGE in choosing the most appropriate coor­ dination strategy in a given situation. We performed two sets of experiments varying the probability of the centers seeing crisis tasks. In the first set of experiments, the crisis task group arrival probability was 0.25 and in the second set it was 1.0. For both sets of experiments, low priority tasks arrived with a probability of 0.5 and the routine tasks were always seen at the time of new arrivals. A day consisted of a time slice of 140 time units and hence the deadline for the task structures was fixed at 140 time units. In the experiments described here, utility is the primary performance measure. Each message an agent communicates to another agent penalizes the overall utility by a factor called comm_cost. However, achieving a better non-local view can potentially lead to higher quality that adds to the system-wide utility. Thus, utility = quality - totaLcommunication x comm_cost . The system consisted of three agents (or data processing centers).

Experiments

For the experiments where crisis task group arrival probability was 0.25, COLLAGE was trained on 4500 instances in Mode I and on I 0000 instances in Mode 2. For the case where crisis task group arrival probability was 1.0, it was trained on 2500 instances in Mode I and on 12500 instances in Mode 2. Figure I shows the average quality over I 00 runs for different coordination strategies at various communication costs. The curves for both Mode I and Mode 2 learning algorithms lie above those for all the other coordination strategies for the most part in both the experiments. We performed a Wilcoxon matched-pair signed ranks analysis to test for significant dif­ ferences (at significance level 0.05) between average perfor­ mances of the strategies across communications costs upto 1.0 (as versus, pairwise tests at each communication cost). This test revealed significant differences between each of the learning algorithms (both Mode I and Mode II) and each of the other three coordination strategies, indicating that we can assert with a high degree of confidence that the performance of the learning algorithms across various communication costs is better than statically using any one of the family of coor­ dination strategies 1 . As the communication costs go up, the mean performance of the coordination strategies go down. For crisis task group arrival probability of 0.25, the balanced coordination strategy performs better than the learning alga~ rithms at very high communication costs because, learning algorithms use additional units of communication to form the global situation vectors. At very high communication costs, even the three additional meta-level messages for local situa­ tion communication (one for each agent) led to large penalties on utility of system. At communication cost of 1.0, Mode I learner and Mode 2 learner average at 77.72 and 79.98 re­ spectively, whereas, choosing balanced always produces an average performance of 80.48. Similar behavior was ex­ hibited at very high communication costs when the crisis task group arrival probability was 1.0. Figure 2 gives an exam­ ple of situation-specific choice of coordination strategies for Mode I learner in 100 test runs when the crisis task group probability was 1.0. The Z-axis shows the number of times a particular coordination strategy was chosen in the I 00 runs at a particular communication cost. X-axis shows the commu­ nication cost and the Y-axis shows the coordination strategy.

1 Testing across communication costs is justified because in real­ ity, the cost may vary during the course of the day.

When not to learn!

In order to test COLLAGE on interesting scenarios with a range of characteristics, we created a number of "synthetic domain theories" using graph grammar formalisms[Nagendra Prasad et at., 1996]. Space limitations do not permit us to discuss all the results but we would like to briefly talk about a very interesting result seen in the synthetic grammar "G3". We trained COLLAGE on the G3 domain in both Mode I and Mode 2 and tested them on 100 runs for different coordination strategies at various communication costs. We found that a coordination strategy called tough 2 coordination performs slightly better than COLLAGE. Upon closer examination of the problem instances, it was noted that tough was the best performer in 81% of the instances and other coordination strategies did better in the rest of the 19%. COLLAGE learns to choose the right coordination strategy in all the 100 in­ stances. However, the agents require additional units of com­ munication of meta-level information to form the global situa­ tion vector and decide that tough is the strategy of choice (in most cases). The lesson we learn from this grammar is that, if there is an overwhelming favorite for best performance in the family of strategies, then it may not pay to use COLLAGE to determine the best performer through additional situation communication. Sticking to the favorite without awareness of the nonlocal situation may yield as good a performance. However, if the few cases that warrant the choice of another strategy give far superior performance, then the gains from choosing a strategy can more than compensate for the addi­ tional communication. This, however, was not the case in environments produced by grammar G3.

5.2 Discussion

COLLAGE chooses an appropriate coordination strategy by projecting decisions from past similar experience into the newly perceived situation. COLLAGE agents performed bet­ ter than using any single coordination strategy across all the

2 Definition of the tough coordination strategy is not important here.

100 instances in all domains we experimented with, except G3. In these domains, the cost incurred by additional com­ munication for detecting global situation is offset by the ben­ efits of choosing a coordination strategy based on globally grounded learned knowledge. Domain G3, however, is dis­ tinguished by the fact that there is little variance in the choice best coordination strategy and the best coordination strategy was almost always tough. This highlights the fact that learn­ ing is especially beneficial in more dynamic environments.

6 Conclusion

Many researchers have shown that no single coordination mechanism is good for all situations. However, there is little in the literature that deals with how to dynamically choose a coordination strategy based on the situation. In this paper, we presented a learning system, called COLLAGE, that uses meta-level information in the form of abstract characteriza­ tion of the coordination problem instance to learn to choose the appropriate coordination strategy from among a class of strategies. Our experiments provide strong empirical evidence of the benefits of learning situation-specific coordination.

However, one important limitation of COLLAGE is its scal­ ability. As the number of coordination alternatives become large in number, the learning phase could become computa­ tionally very intensive and the instance-base size could in­ crease enormously with respect to Mode 2. We are looking at how to integrate methods for progressively refining situation vectors such as those in [Sugawara & Lesser, 1993], ways to organize the instance-base to access and detect regions where there is insufficient learning and also ways to do more di­ rected experimentation during learning rather than randomly sampling the problem space.

In COLLAGE, all the agents form identical instance-bases. We could as well have done with one designated agent form­ ing the instance-base and choosing the coordination strategy. However, our configuration was set up with a more general scheme in mind. Instead of all agents choosing the same coor­ dination algorithm, they can choose pairwise or group-wise. A subset of the agents coordinate to choose the same strategy. This will lead to different case-bases at different agents and an agent may have more than one case-base if it is a part of more than one group. This leads us to another scalability issue: the number of agents. If there are a large number of agents, then common situation vectors may lose "too many" details about the situations. Pairwise or group-wise coordina­ tion may be a better option. However, we have to deal with issues such as inconsistent and conflicting knowledge among the case-bases, formation of appropriate groups, and different amounts of learning for different groups.

Acknowledgments

We would like to thank Keith Decker and Alan Garvey for their help and input during the course of this work. Thanks also go to Daniel Neiman, Mike Chia and the anonymous referees for their comments and feedback on draft versions of this paper.