Increasing Coherence in a Distributed Problem-Solving Network

INCREASING COHERENCE IN A DISTRmUTED PROBLEM SOLVING NETWORK

Edmund H. Durfee, Victor R. Lesser, and Daniel D. Corkill

Department of Computer and Information Science University of Massachusetts Amherst, Massachusetts 01003

ABSTRACT

Globally coherent behavior is the holy grail of dis­ tributed problern eolving network research. Obtaining co­ herent network activity without sacrificing node autonomy and network flexibility placea severe demanda on the lo­ cal control component of each node. We introduce new mechanislD8 that allow a node to compute an abstracted, high-level description of its local state which it then usea to formulate multi-step plans. Not only do these mechanislD8 significantly improve local problern eolving performance, but they also enable nodes to make dynamic refinements to their long-term network organizaUon knowledge. The coordination decisions made by nodes are thus increasingly responsive to changes in network activity as problern solv­ ing progresses. We provide experimental results indicating that these new mechanislD8 improve the intemal control de­ cisions of a node, reduce the communicaUon requirements of the network, and improve network coherence. We be­ lieve that these mechanislD8 would also be useful for control in centralized multi-level blackboard-based problern eolving systelD8.

I. INTRODUCTION

Achieving global coherence in cooperative distributed problern solving networks (DPSNs) is a major problern [4,13]. In a DPSN, each node is an intelligent semi­ autonomous problern eolving agent that determines its own behavior based on its perception of network activities. Global coherence means that the activities of the nodes should appear to make sense given overall network goals. Nodes should avoid unnecessarily duplicating the work of others, sitting idle while others are swamped with work, or transmitting information that will not improve overall network performance. Because network coordination must be decentralized to improve reliability and responsiveness, the amount of global coherence in the network is dependent on the degree to which each node makes coherent decisions based on its local view of network problern eolving activities.

This research was sponsored, in pari, by the National Sdenee Foundation under Grant MCS-8300239 and by the Defense Advaneed Research Projeets A,eney (DOD), monitored by the Offtee of Naval Research under Contraet NR049-041.

At any given time, a node will rank its pending tasks based on how it believes each will improve network problern eolving. A decision by the node to execute the top ranked task is therefore more or less coherent depending on how highly ranked the task would have been if the node had a completely global view of network problern solving. Full global coherence requires that each node have a complete and accurate view of the past, present, and intended future activities of all other nodes. H this is done by globally predefining a coordinated multi-agent plan at network creation, the network will be inflexible to changing problern solving situations and network characteristics. Altematively, having nodes broadcast all state changes and future intentions is infeasible due to bandwidth limitations and channel delays. Therefore, we have no practical means to insure full global coherence. The functionally accurate, cooperative approach to distributed problern solving develops a framework in which network goals can be achieved with only partial global coherence [13]. However, since partial coherence wastes resources and degrades performance, we have been developing mechanislD8 which increase coherence without significant additional communication costs.

Our previous work toward this end developed a decentralized approach to network coordination in which each node is guided by a high-level strategic plan for cooperation among the nodes in the network [3]. This strategic plan, represented as a network organizational structure, specifies in a general way the communication and control relaUonships among the nodes. The organ!zational structure increases the likelihood that nodes will be coherent in their behavior by predefining a limited range of options available to a node. Network flexibility is maintained by not limiting these options too tightly. Sophisticated local control plays a key part in this approach because decisions about which of these options to pursue must be based on shorl-term information about the current situation.

In this paper, we describe new mechanislD8 that allow a node to refine its perception of the role it currently plays in the organization. This refined view is achieved by providing each node with the ability to reaeon about its current state of problern solving and to make predictions about its future actions. To accomplish this, these new mechanisms allow a node to compute an abstracted, high­ level description of its local state. The node uses this description to formulate high-level goals and to generate plans to achieve them. Since each plan incorporates a sequence of actions, the pursuit of a specific plan allows the node to make reliable predictions about its actions in the near future. These predictions enable the node to make medium-term, dynamic refinements to how it views its role in the network organization, and it may modify its local processing accordingly. Furthermore, if nodes occasionally exchange meta-level information about these refined views of the organizational roles they will be playing in the near future, each node will have a more global view of the network problern solving activity, and global coherence will increase.

We have implemented and empirically evaluated our ideas using the Distributed Vehicle Monitaring Testbed. The next section outlines the relevant aspects of the testbed, describes how our mechanisms were incorporated, and discusses experimental results indicating improvement in local problern solving ability. We then study how these mechanisms can be used to improve network coherence, and present results indicating their utility. Finally, we relate our work to other research in distributed problern solving and discuss the implications of the preliminary research we have outlined, along with the directions we will be pursuing in the future.

D. INCREASING TBE SOPBISTICATION OP' A PROBLEM SOLVING NODE

The distributed vehicle monitaring testbed (DVMT) is a flexible and fully-instrumented research tool for the evaluation of distributed network designs and coordination policies [14]. The DVMT simulates a network of problern solving nodes attempting to identify, locate and track pattems of vehicles moving through a two­ dimensionalspace using signals detected by acoustic sensors. Each problern solving node is an architecturally-complete Hearsay-II system with knowledge sources and Ievels of abstraction appropriate for this task. The basic Hearsay-II architecture has been extended to include more sophisticated local control [2], knowledge sources (KSs) for communicating hypotheses and goals among nodes, and data structures called in.tere&t area& that specify the organizational role of a node [3] . These interest area specifications are used by the local node control in deciding what problem-solving and communication knowledge sources should be instantiated and how these knowledge source instantiations (KSis) should be rated for possible execution.

In this section, we introduce further modifications to this architecture by providing a node with the capability to generate and reason with a more complete view of its past, present, and future activities. Although nodes generally tend to methodically perform sequences of related actions, they are unable to represent and reason about such sequences. For example, given a highly rated hypothesis, a node typically executes a sequence of KSis that drive up low Ievel data to extend the hypothesis. However, the entire sequence of KSis is never on the queue at once. We have therefore developed a structure, called a plan, to explicitly represent a KSI sequence.

A. Blackboarch, PlllllS, and Node Actlvities

Each plan represents a desire to achieve a high-level goal by performing a sequence of activities. To identify plans, the node needs to recognize these high-level goals. Inferring high-level goals based on pending KSis is an inappropriate strategy; it is like attempting to guess a chess opponents strategy after seeing a single move. Furlhermore, the hypothesis and goal blackboards provide information at too detailed a Ievel to infer these high-level goals. What is required is a structure similar to the blackboards that groups related hypotheses and goals into a single structure. We have developed a preliminary version of this structure which we call the ab&tracted blackboard, a multi­ level structure reminiscent of the focus-of-control database first used in the Hearsay-ll speech understanding system [7]. Our implementation of the abstracted blackboard is incomplete because it does not adequately incorporate the information from the goal blackboard. However, for the type of processing done in the DVMT, hypothesis abstraction is usually effective.

Hypotheses with similar Ievel, time, and region characteristics are grouped together on the abstracted blackboard. This grouping acts as a smoothing operator, obscuring details about individual hypothesis interactions so that broader, long-term interactions between areas of the solution space can be discemed. By transforming the data blackboard into the abstracted blackboard, we explicitly generate a state representation that is uniquely appropriate for planning at a higher Ievel of abstraction. We believe that the significant success of our modified architecture can largely be attributed to having such a representation, and expect that the control components in other multi-Ievel blackboard-based problern solving systems migbt similarly find such representations useful [9].

In our preliminary implementation, the abstracted blackboard takes the form of a two-dimensional array, with Ievel and time indices. Each hypothesis has associated with it a sequence of time-locations which indicates where the hypothesized vehicle was at various times. When a hypothesis is created, it is incorporated into the abstracted blackboard by stepping through this sequence of time­ locations and modifying the appropriate level-time entries in the abstracted blackboard. Each level-time entry contains some number of regions, and if the location associated with the specific time can be included in one of these regions (perhaps by enlarging the region within certain bounds), the hypothesis is associated with that region. Otherwise, a new region is formed for the hypothesis.

Each Ievel-time-region of the abstracted blackboard is summarized into a set of values that are derived from the associated hypotheses. These values include the maximum belief of the hypotheses in the Ievel-time-region, the number of highly believed hypothesea, the number of K.Sia stimulated by theee hypothesea that have yet to be invoked, the total number of hypotheeee in the Ievel­ time-region and how many uninvoked K.Sia are aesociated with them, and an indication ae to the other Ievel-time­ regions that share at least one of the hypothesea. This information allows the aituatior& recogr&iur to develop a higher level view of the problem solving. For example, low ma.ximum belief indicatee the problem solving approach in that area should be re-evaluated, a large number of equally rated hypothesea could imply that there is uncerlainty that should be resolved, and a large number of pending K.Sia indicatee the need for making an informed and judicious choice ae to which action to take next. Basedon this higher­ level view, we can begin to form high er level goals. A goal might be to merge hypothesea in adjacent time-regione, to improve the belief of an established hypotheeis, or to extend a highly believed hypothesis into a new region.

The detedion of theee goals, . and the subsequent generation and ranking of their respedive plane, is in itself a complex problem solving task. Our current implementation is a first step toward this end, in which we only coneider very simple but imporlant plane. Given the abstracted blackboard, our planner scane down it, looking for regione of high belief. Having found such a atimulua regior&, the planner determines whether there is any indication that the data in this region can be improved (this is done by determining whether any corresponding lower level regione have higherbelief than the upper level regions), and if so indicated, a plan is formed to achieve this improvement. Otherwise, a plan is generated to extend this highly rated region, either by merging a hypothesis in this region with a hypothesisinan adjacent region on the same level (if any), or by driving lower level data in an adjacent area up to a level at which it can be incorporated. If none of theee plane can be formed, then a plan to syntheeize the hypotheses in this highly rated region up to a higher level of abstraction may be formed.

Plane in our current implementation are not yet fully developed, because a plan should not only involve the specification of an eventual goal, but also of a sequence of actione needed to achieve this goal. Only the next potential step(s) for achieving the plan are currently represented ae a priority rated queue of K.Sia. In turn, the node maintaine a queue of plane, ordered based on their reepective ratings. A plan rating is based on a number of factors, including the belief of its stimulus region, the level of its stimulus region, the interest in that region (specified by the intereet areas), the ratings of its K.Sia, and whether the stimulus region repreeents hypothesea generated locally or it repreeents received hypothesea (to reason more fully about potentially distracting information received from outside). Therefore, in choosing its next activity, a node will invoke the highest rated K.SI in the higheet rated plan.

We have therefore made imporlant modificatione to the control strudure of a node (Figure 1). As the figure indicatee, the creation and ranking of plane requiree the planner to integrate the influencee of the long-term strategy of the organizational strudure (the interest areas), the medium-term higher-level view of the current situation (the abstracted blackboard), and the shorl-term KSI input indicating actions that can be achieved immediately ( the KSI queue). Hence, decisione in a plan-based node are more informed than those in a K.SI-based node (a node without plane). Moreover, a plan-based node is no le811 opporlunistic, because plane, unlike KSis, are interruptable. If an area outside the current plan looks more promising, a plan to work there may temporarily supplant the current plan at the top of the queue. In addition, when plane are introduced, one can begin reasoning about the time invested in a parlicular area, and whether it is really in the node's best interests to leave this area for another.

Pigure 1: The Problem Solving Architecture or a Node.

B. Experiment· with Plan-baaed Nodea

We now briefly illustrate how problem solving is improved in a plan-based node (we shall consider multi­ node networks in the next section). Consider the sensor configuration and input data shown in Figure 2. The vehicle track hae two strongly seneed areas divided by a weakly seneed area, while the ghost track is moderately seneed throughout. In the centralized case, a single node receivee data from all four sensors. If the node makee only correct decisione, it can generate the solution in 40 time units. However, the presence of moderate ghost data serves to distract the node. This distraction is severe if the node is K.SI-based-the solution is found in 213 time units.

The four sensors have a small amount of overlap. There are eight data points on both the ghost track (upper) and the vehide t~ac.k (lower). The size of the data point indicates how strongly 1t IS sensed.

Figure 2: Four Sensor Conflguration.

Although a plan-based node is also distracted, ib high­ level view helps it quickly recognize that the distracting data will not satisfy the high-level goal which drives the plan. For example, the high-level goal may be to create a hypothesis which extends a hypothesis with three time­ locations to four time-locations. Distracting data which initially Iooks like it might satisfy this goal is developed until the planner, using the high-level view, recognizes that the high-level goal will not be achieved. At this point, a plan to develop other data which could satisfy the high-level goal becomes the highest rated plan. Due to the high-level view and the sophistication of the planner, the time spent deviating from the correct solution path is reduced, and the plan-based node can generate the solution in 58 time units.

Plan-based nodes have been used in a number of other environments with similar results. In both the centralized case and the multi-node case where nodes do not exchange meta-level information (see next section), the increased self­ awareness afforded by the new mechanisms significantly improves problem solving performance. The experiments thus serve to emphasize the imporlance of sophisticated local control which recognizes and reacts appropriately to various problem solving situations. We anticipate expanding the repetoire of situations which can be dealt with so that plans can be developed in more complex environments.

m. INCREASING TBE COBERENCE OF TBE PROBLEM SOLVING NETWORX

Wehaveseen how the performance of a centralized node can be improved by allowing it to reason more fully as to the appropriate activities to perform. We now examine the multi-node case, where each node has a limited local view of network problem solving. In the previoua sedion, we established that the problem solving behavior of a plan­ based node is more effective than that of a KSI-based node. Therefore, we can expect that a nehrork of such nodes might have improved performance, not because they displayheUer ·teamwork· (their global knowledge does not increase), but rather because each is a better ~layer-.

These expectations were empirically verified on a number of environments. Environment El uses the configuration of Figure 2, but assigns a separate node to each sensor, each node being allowed to communicate with its neighbors. A second environment, E2, is a four-node environment identical to El except that the positions of the vehicle and ghost tra.Cks are reversed. Note that, in this case, the weakly sensed vehicle data is received by all four nodes, and is the only data received by one of them. A larger sensor and data configuration consisting of ten sensors and eighteen sensed times was developed, pattemed alter the four sensor configuration (5]. A third environment, E3, consisting of ten nodes was bunt upon this configuration.

The experimental results are given in Table 1. Note that, in all cases, the multi-node network composed of plan-based nodes is significantly heUer. Environment E2 approaches optimal results because one node receives only the weakly sensed vehicle data, and so, will drive this data up earlier. In the other environments, however, work on this weakly sensed data is not as timely because the nodes prefer to work redundantly on the more highly sensed vehicle and ghost data in their overlapping sensed areas. This redundancy wastes computation time that could be used to develop the weak vehicle data instead-the network is not behaving coherently.

By transmiUing the abstracted blackboards (or porlions thereof), nodes can reason about the pa~t activities of their neighbors. Furlhermore, if a node knows the current plan of its neighbor, it can reason about the p~&~nt actions of its neighbor. Rea.sOning about the futu~ actions of a node, however, is a complex problem. This reasoning involves considering not only the current plans in the node's queue and making estimations about their durations and effects, but also what funher information the node may receive (from another node or from its sensor) that could affect its activities. A plan may have associated with it some estimations as to duration and probability of completion, or even more specific information about how its execution could be affected by received information.

Our current implementation assumes that a node can make completely accurate shorl-term predictions about future activity based solely on the plan queue. We simulate this best-case scenario by allowing a node access

Legend:

Tlme Earllest time at which a solution was found

MLC Meta-level Commnnication

Comparison of performanee in multi-node environmenb. Plan­ based nodes work eonsistently heUer than KSI-based nodes, resultinr; in improved performanee. Meta-level eommunieation can funher improve performanee by increasinr; eoherence.

Table 1: Performllllce of Multl-node Networke.

to the abstracted blackboard and plan queue of another node. Discussion of more realistic seenarios where nodes must transmit thie meta-level information as they transmit hypotheses, and must therefore reason about relevance, timeliness, and completeness, can be found elsewhere [6].

A node may use meta-level information to avoid redundancy. In developing a plan, a node can determine if the plan represents a redundant derivation of information that another node has either generated (present in the abstracted blackboard) or ie in the process of generating (the top plan). By avoiding redundant activity, signifi.cant improvements in solution generation rate can result because less highly rated but potentially useful activities will be invoked earlier ( rather than redundant invocation of highly rated activities ). Hence, the experimental results in Table 1 indicate that network performance can be funher improved by the exchange of meta-level information which allows individual nodes to make more coherent local decisions.

A. Coherent Comm.mücatlon

An imp0rlant aspect of coherent network activity ie that limited communication resources should be used intelligenUy to improve the globalstate of network problem solving. Flooding the bandwidth with partial results can cause both undesirable delays to imporlant messages and unreasonable amounts of local processing as nodes incorporate the received information. On the other hand, if a node withholds cerlain partial results, network performance can degrade. n ie therefore imporlant that a node have a satiefactory view of both local and network problem solving in order to make coherent communication decisions.

We have developed a nurober of communication strategies that use the high-level view of node and network activity to guide a node in making these decisions [6]. These strategies extend the ideas fi.rst developed by Lesser and Erman [12]. When deciding about sending a partial result, the node might consider whether it will be improving upon that result in the future, and if so, whether by waiting and sending only the heUer version (conserving bandwidth) it can still fulfill its obligation to provide partial results in a timely manner. Furlhermore, the exchange of meta-level information can allow a node to make inferences about how a particular transmission might affect network problem solving, and to decide when to repeat a message if the effects are not seen. In experimental studies, we have found that simple communication strategies that flood the bandwidth can signifi.cantly slow down the network, and that these problems become much more pronounced as we experiment with }arger networks. For example, in the ten-node environment above (E3), a simple communication strategy results in 279 hypothesis transmissions between nodes. A more intelligent strategy reduces this nurober to 166 without adversely affecting the solution time. Therefore, indications are that coherence in communication decisions is an imporlant area of study, and will become increasingly so as our environments continue to increase in size.

IV. SUMMARY AND IMPLICATIONS POR DPSN RESEARCH

We have discussed our experiences in increasing the coherent behavior of the Dietributed Vehicle Monitoring Testbed. We modifi.ed the blackboard problem solving architecture of the individual nodes to enhance their ability to make predictions about their future activities. Network coherence is increased by allowing a node to refi.ne its organizational role based on these predictions. Exchanging the predictions permits a node to refi.ne its view of the organizational roles of the other nodes.

Coherence is an integral part of distributed problem solving research. In contrast with others [11], we assume that we have only a limited nurober of highly sophisticated problem solving agents, and so, should coordinate them to make the most effective team possible. Because we assume that communication between agents is potentially slow and unreliable, we regard coordination that requires mutual agreement on contracts before action [1,4] to be insufficiently responsive to changing problem circumstances (indeed, mutual agreement might not even be possible [8]). To insure reliability, we cannot accept centralized coordination [1]. The unpredictable nature of the problem solving environment makes simple game theoretic models of agents unrealizable [15], while more complete models of agent beliefa [10] might require nodes to essentially duplicate each others reasoning.

Our view of distributed problem solving therefore stressea the imporlance of sophisticated local control which integrates objed-level knowledge about the problem do­ main with meta-level knowledge about network coordina­ tion. Such control allows nodes to make rapid, intelligent local decisions based on changing problem charaderistics without the overhead of conferring with each other. Coor­ dination decisions are based on a high-level organizational view of individual node activity, so nodes need not have detailed models of the object-level problem solving activ­ ity of their compatriots. Dynamic improvements to this organizational view may be achieved with the exchange of meta-Ievel messages which briefly convey high-level coordi­ nation information. In shorl, the nodes initiate their own activities and will take advantage of any local and network knowledge available to formthebest -team· possible within the constraints of their environment.

We believe that implementation and experimentation are essential for learning about and understanding distributed problem solving. Our future plans include improving the representation of the state of a node, enhancing the mechanisms to recognize problem solving situations, and extending the plan strudures to incorporate more information. Our preliminary experiments indicate that these developments should significanUy improve the performance of distributed problem solving networks, and may also be useful in blackboard-based problem solving systems in general.