Focus of Control Through Goal Relationships

1 Introduction

Making appropriate control decisions in a complex, multi-dimensional search space is a difficult task . This difficulty arises because relationships among partial re­ sults and potential activities are not readily observable. For example, in a blackboard architecture the same partial results can be used in many contexts. There­ fore, producing a specific result may affect many al­ ternative solutions . In addition, the problem space is represented at multiple abstraction levels on the black­ board. and multiple solution paths for the same result mav be available. This provides the problem solver with flexibility in choosing problem-solving activities but also allows results to be rederived using alterna­ tive paths without recognizing the redundancy until the last step. Furthermore, the asynchronous, opportunis­ tic stvle of problem solving leads to situations where it is unclear whether a solution is missing due to a lack of data, in which case the solution will never be generated, or due to a lack of processing, in which case additional work will eventually produce the solu­ tion. Thus, employing complex problem-solving capa­ bilities while at the same time making intelligent con­ trol decisions is a formidable task [Hayes-Roth, 1985, Haves-Roth and Lesser, 1977, Lesser and Erman, 1977, Nii, 1986b, Nii, 1986a].

'This research was sponsored, in part, by th(' National Sci('nce Foundation under CER Grant DCR-8500332, and by th(' Office of Naval Research under University Research Jni­ tiative Grant Contract N00014-86-K-0764, and under Con­ tract N00014-79-C-0439.

Several years ago, the co9perating knowledf?e source architecture of Hearsav-II [Erman et al., 1980j was ex­ tended to unifv data-directed and goal-directed control [Corkill et al., 1982]. 1 This was a first step toward devel­ oping the needed interrelationships among actions and results necessary for making intelligent control decisions . In the interim, we have gained considerable experience with this control architecture. In particular, we have identified the need for new types of goals and for addi­ t.ional relationships among goals. These extensions allow us to more accuratelv relate the predicted results of fu­ ture activities to existing results in order to make more informed control decisions.

In the next section we briefly review the unified data­ directed and goal-directed control architecture . Section 3 describes the new goal relationships from a general perspective and presents specific examples from two do­ mains. Section 4 out.lines how these new mechanisms work in a blackboard based problem solver. Section 5 is a brief presentation and discussion of our experimental results.

2 A Review of Goal-based Control

Figure l presents a high-level schematic for the inte­ grated data-directed and goal-directed control architec­ ture as implemente<i in t.he DVMT [Lesser et al ., 1987, Lesser and Corkill , 1983]. The basic H earsav-ll archi­ tecture is modified to include a goal blackboard and a goal processor. The goal blackboard, which mirrors the data blackboard in dimensionality, contains goals representing intentions to create particular results on the data blackboard. Goals provide an abstraction over the potential actions for achieving a particular type of result and allow the system to reason about its inten­ tions independently of the particular knowledge source (KS) actions at its disposal.

1 Through a slightly different. approach, Johnson and Hav('s-Roth [Johnson and Hayes-Roth, 1987) have also ('X­ t('n.d ed the data-direct('d proc('SS of the classic black board problem solver to includ(' goal-directed control.

The two general classes of goals are data-directed and goal-dir~cted . The blackboard monitor uses do­ main knowledge to create data-directed goals in response to the addition or modification of partial results on the data blackboard. Each data-directed goal specifies the range of potential solutions resulting from the use of the triggering data.

Since the creation of a goal does not guarantee suf­ ficient information on the data blackboard to execute a KS to satisfy the goal, the goal processor runs a precon­ dition procedure for the applicable KSs to make a de­ tailed examination. When results indicate that a KS has sufficient information to satisfy the goal, the goal trig­ gers a KS instantiation (KSI) . The scheduler assigns the KSI a priority rating and places it on the scheduling queue. The scheduler assigns priority by first deter­ mining the set of goals that may be satisfied by a KSI's predicted output. It then computes the KSI's rating as a function of the ratings of the potentially satisfied goals and the credibility of the predicted results. If suffi­ cient information is not available to run a KSI , the goal processor can create goal-directed goals (subgoals) to generate the needed data. 2 The decision to create sub­ goals is dependent on the importance of achieving the goals potentially satisfied by the KSI and on the cost of creating the subgoals. Subgoal ratings are based on the rating of the goal that triggered the KSI. If the parent goal has a high rating, its subgoals might increase the rating of KSis that generate data needed to satisfy the preconditions of the KSI triggered by the parent goal.

2 Goal-directed goals are also generated by the goal pro­ cessor for other purposes.

Goal-based control does not require that control de­ cisions be made in a top-down, goal-directed man­ ner. Goals are used to make both data-directed and goal-directed control decisions, and the classic data­ directed/goal-directed dichotomy is represented in our approach by the relative ratings among goals. By ad­ justing its KSI rating computations, the scheduler can bias the system towards goal-directed or data-directed control. Goal-based control attempts to incorporate do­ main data to build an appropriate control abstraction that will predict the type of results that can possibly be generated. This permits the system to develop non­ local focus-of-control strategies that take into account the interactions of work on data in different parts of the problem-solving space.

3 Goal Relationships

In addition to the goal/subgoal relationship, other rela­ tionships among goals can be exploited to improve the effectiveness of goal-based control. These new goal rela­ tionships resulting from the initial data and subsequent processing can be used to dynamically construct a partial topology of the solution space based on what appear to be feasible solutions. This structure can be used to make control decisions that significantly reduce the amount of search required to solve a problem in a complex domain. Specifically, three important questions necessary for ef­ fective control can be answered by relating goals to each other:

• Can the same results be obtained by working on different goals?
• Will working on two distinct goals generate equiva­ lent partial solutions?
• Will work on a goal differentiate between mutually exclusive solutions?

In order to formally define the goal relationships nec­ essary to answer these questions, we first define the fol­ lowing concepts: the potential solution set of a goal and the component set of a potential solution.

• potential solution set for a goal g: S(g) = { x I x is a potential solution of g}, where x is a potential solution of g if its characteristics lie within a range specified by g. S(g) defines the space of all possible solutions of g. A specific x E S(g) is only a potential solution since it may not be supported by low-level data or it may not be consistent with the solution to some other goal that interacts with g.
• component set of a potential solution x: the set of partial results consistent with some subset of the characteristics of x, c.(x) = {y I Vg, y E S(g) =} x E S(g) 1\ x =F y}. y E C,(x) implies that the characteristics of yare a subset of the characteristics of x and, therefore, that y could possibly be used to derive x.

The goal relationships can now be defined as follows:

• (a) Sample Grammar: S-+ NP aux VP NP -+ noun I det noun VP -+ verb I verb PP I verb NP PP -+ preposition NP
• (c) Competition:

91 : form a PP using {"by", w;, ... , w;} 92 : form a PP using {"to", w;, ... , w;} 91 and 92 are competing since there is no goal with a solution :z: where :z: includes solutions to 91 and 92 as components.

• (e) Sub.mmption:

91: form a PP using {w;, ... ,w;} 92 :form a VP using { wh, .·. , w;} 92 subsumes 91 since any PP satisfying 91 will be included in some VP satisfying 92.

• (g) Independence :
• 91: form an S using {w;, ... ,w;} 92 : form an S using { Wm, ... , wn} 91 and 92 are not competing and their individual solutions cannot be combined to satisfy another goal.

Figure 3: Goal Relationship Diagrams, Example 2

• (b) Sample Component Set: C,("The boy ran up the hill.")= {NPThe boy, detThe, nounboy, aUXnil, VPran "P the hill, verbran, PP,.p the hill, prep,.p, NPthe hill,detthe, nounhw}
• (d) A !!i!tance:

91 : form an NP using { w;, ... , w;} 92: form a PP using {"to",w;, ... ,w;} Every PP contains an NP, so satisfaction of 92 implies satisfaction 91· But an NP does not have to be used in a PP, so 91 is not subsumed by 92.

• (f) Cooperation:

91 :form an AUX using {w;, ... , w;} 92 :form a VP using { WA:, ··· , w!} Goal, "91 :form an S", has solution X where solutions to 91 and 92 are components of X, so 91 and 92 are cooperating.

• subsurnption: Goal gl subsumes a second goal, g2, if the specifications of g2 are completely encompassed by the specifications of gl. Formally, 91 subsumes 92 ifVy,y E S(92) ~ :Jw s.t . y E C,(w) l\w E S(91).
• assistance: One goal, gl, is said to assist another goal, g2, if satisfaction of gl implies satisfaction of g2. The assistance relationship identifies those goals that represent alternative approaches to generat­ ing a particular solution. 91 assists 92 if Vw, w E S(91) ~ :Jy s.t. y E C.(w) 1\ y E S(92).
• competition: Two goals, gl and g2, are competing if there is no possible partial solution that will satisfy both goals. By checking if two goals are competing, the system can determine if the knowledge sources they have triggered will generate distinct results. If two goals are not competing, the system cannot make this determination because the possibility ex­ ists that a solution to one goal is also a solution to the other goal. As a consequence, working on both goals could produce redundant results. Goals 91 and 92 are competing if VwVy, w E S(91 ) 1\ y E S(92) ~ ....,(:J91:JW:JY s.t . {W, Y} C S(9J ), Wand Y can be simultaneously acceptable solutions and wE C,(W) 1\ y E C,(Y)).
• cooperation: Two goals are cooperating if it is possible for the goals to produce information that may be incorporated into a single result at some point in the future. Goals g1 and g2 are completely cooperating if VwVy, w E S(g1) 1\ y E S(g2) ~ :lgf:Jx s.t. x E S(gJ) 1\ {w,y} C C.(x).
• independence: Two goals are independent if they are not competing and if it is not possible for them to be incorporated into a single solution at some point in the future . Goals g1 and g2 are independent if they are not competing and if VwVy, w E S(g1) 1\ y E S(g2) ~ -, (:Jgf:Jx, s.t. X E S(gJ)I\{w,y} c c.(x)).
• subsurnption-inhibition: A new type of goal , called an inhibiting-goal, has been added to identify redun­ dant work that can be eliminated. Goal gl inhibits a second goal, g2, if gl is an inhibiting goal and gl subsumes g2.
• assistance-inhibition: Goal gl partially inhibits goal g2 if gl is an inhibiting-goal and gl assists g2. The assistance-inhibition relation limits work to those areas of g2 not encompassed by gl.

A sample grammar and example goal relationships for a natural language parsing system that works asyn­ chronously and opportunistically from any point in the input are shown in Figure 2. Preprocessed signal data input is represented as {w1, w2, ... ,wn}·

Figure 3 shows similar goal relationships for a dis­ tributed vehicle monitoring system that functions in a spatial domain where a goal can be represented as a two dimensional parallelogram, [((xu, Yu), (xnz, Ynz)) ((xzr , Yzr), (x,r, y.,.r))]. A potential solution of a goal is a sequence of lines connecting consecutive points (( xa,Yo ) ... (x(«+k)>Yk) ... (xc,Y( xc-xa ))) where at least one point lies within the parallelogram, a line intersects at FOR each newly created hypothesis, h IF (h.level ~ *inhibiting-goal-creation-level*) AND ( h.rating ~ *inhibiting-goal-creation-threshold*)

THEN

Create inhibiting goal G,. and associated inhibiting subgoals, SGc ..

For each triggering goal subsumed by G,. or SGc .. Terminate efforts to satisfy the triggering goal

For each triggering goal assisting G,. or SGc,.. Restrict processing in areas encompassed by G,. or SGc ..

Figure 4: Inhibiting Goal Creation Algorithm

least one side of the parallelogram, and no line intersects either the top or bottom of the parallelogram.

4 Experiments

The following two examples demonstrate the usefulness of goal relationships. The first helps prevent redundant processing through the use of inhibiting goals, and the second enables a knowledge! source to be rated more ac­ curately based on its local context.

4.1 Inhibiting Goals

A new goal type, an inhibiting goal, has been added to control redundant processing. Without inhibiting goals , the only way to minimize redundant activity was to de­ crease the ratings of the goal and subgoals that led to a strongly believed result. This method prevents addi­ tional work only on the original solution path used to derive the high-level result. It does not limit activity on any of the alternative paths that might lead to the same result. In order to effectively control redundant processing, a separate mechanism is needed to eliminate derivation of any intermediate result that would eventu­ ally produce the high-level result. Thus, when a satisfac­ tory, high-level result is produced, this new mechanism insures that the system only works on data it determines to be independent, competing, or cooperating in relation to the high-level result.

An inhibiting goal and its associated inhibiting sub­ goals are generated when the system determines that sufficient work has been done on refining a high-level result. All KSs are then inhibited from producing re­ sults that are subsumed by the inhibiting goal or inhibit­ ing subgoals. The specification of the inhibiting goal is taken from the characteristics of the high-level result. By specifying a tolerance around the inhibiting goal , its characteristics can be generalized to extend the range of inhibition. This can eliminate solutions that are simi­ lar, though not identical. This is appropriate in envi­ ronments where answers that have characteristics close to the correct answer are acceptable. The algorithm is given in Figure 4.

In general, inhibiting goals do not preclude the for­ mation of competing solutions that overlap inhibited re­ gions. These solutions will still be formed by extending data outside the inhibited area. Figure 5 illustrates such a situation in the previously described distributed ve­ hicle monitoring system. In this scenario, four potential solutions can be formed by merging the segments labeled a, b, c and d into the potential solutions ad, ac, be and bd. If the system were to form ad first and create an inhibit­ ing goal to restrict further processing on ad, ac could still be formed by extending c to ac since the goal to extend cis neither subsumed nor assisted by the inhibit­ ing goal corresponding to ad. It might still be possible for some competing solutions to be precluded in anoma­ lous situations where multiple inhibited regions interact. However, this depends almost entirely on how the inter­ mediate potential solutions are formed.

4.2 Local Context

Along with inhibiting activity based on high-level re­ sults, there is also a need to inhibit activity based on a more local context. For example, if any goal that trig­ gered a KS is satisfied before the KS runs, and if the KS can not improve on the results that satisfied the goal, the KS should have its rating decreased. Consequently, which KS satisfies a goal is an important issue . If the scheduler gave priority to the KSI with the most com­ prehensive triggering goal , its results might satisfy other goals and eliminate the need to execute their triggered KSis . The following situation demonstrates this point.

Consider the pending activities KSI1 and KSI2 , gen­ erated from work on two different derivation paths. If executed, K SI1 would produce result R1 that would sub­ sume R2 , the result of executing KS[z. Executing KSI1 first would make KSI2 's results redundant, so the scheduler should give K SI1 priority. However, from a local, data-directed perspective, K S]z might be given higher priority, even though K SI1 is the more promising of the two. This can occur if the scheduler incorporates an av­ erage of input data credibility in its KSI rating function and if K Sh uses lower rated data in addition to highly rated data used by K SI2 . For example, K Sh may gen­ erate R1 by extending highly credible data into areas of weak data, and K 512 may use only the highly credible data to produce the highest rated component of R1.

Our ear~ : er approach to rating KSis tried to balance the quality of the predicted result with its scope. How­ ever, we found that the appropriate balance was situa­ tion dependent. Assigning too much priority to scope had the undesirable consequence of making the search too depth-first, while assigning too much priority to quality led to redundant activity as illustrated in the above example. Instead, to choose among the pending KSis, we need to explicitly take into account the rela­ tionships among their predicted outputs.

Using the goal relationships specified in the previous section, the system can form a local understanding of why a KSI is scheduled to be invoked and may instead invoke a different KSI that produces the same results more efficiently. This procedure, called the Local Con­ text Mechanism, can be added to the system as an addi­ tion to the scheduler. In general, before executing a KSI, the Local Context Mechanism examines the KSI's trig­ gering goals and searches for a more comprehensive KSI that would also satisfy these goals. If this more compre­ hensive KSI produces an actual result that is as good in

result c FOR every goal, g, in a KSI's triggering-goal list For each hypothesis, h, satisfying g IF h subsumes any element of the KSI's predicted outputs AND the predicted output cannot improve h in any way THEN

Remove the subsumed item from the KSI's set of predicted outputs Recalculate the KSI's rating

(* Prior to invoking the highest rated KSI *)

IF the KSI's assisting goal list is non-nil THEN

Invoke the KSI triggered by the most comprehensive assisting-goal

ELSE

Invoke the original KSI

Figure 6: Local Context Mechanism

the subsuming area as that expected from the less com­ prehensive KSI , the subsumed results are removed from the output set of the less comprehensive KSI. The Local Context Mechanism is implemented as a combination of the two algorithms shown in Figure 6.

5 Experimental Results

The goal relationship algorithms were implemented in the Distributed Vehicle Monitoring Testbed (DVMT). The DVMT simulates a network of vehicle monitoring nodes, where each node applies simplified signal process­ ing knowledge to acoustically sensed data in an attempt to identify, locate and track patterns of vehicles moving through a two-dimensional space. A node is responsible for a specific area and attempts to recognize and elimi­ nate errorful sensor data as it integrates the correct data into an answer map. Each node has a blackboard archi­ tecture with knowledge sources and blackboard levels of abstraction appropriate for vehicle monitoring. Knowl­ edge sources perform the basic problem solving tasks of extending and refining hypotheses (partial solutions). As described earlier, data-directed and goal-directed goals are used to control problem solving activities.

Experimental results are summarized in Table 1. Three environments were used for testing; a simple envi­ ronment with a single vehicle track and no sensor noise, an environment with the same vehicle track but with random noise added, and a complex environment with two crossing vehicle tracks and a significant amount of noise. Features used for comparison were the number of knowledge source executions required to produce the solution(s), the number of hypotheses created, and the number of goals created . The system performed more ef­ ficiently with the new goal relationship algorithms. For the environment with a single track, 36% fewer hypothe­ ses and 9% fewer goals were produced and the system required 65% fewer KS executions to compute the an­ swer. In the second environment, 11% fewer hypotheses and 8% more goals were produced and the solution was found with 37% fewer KS executions. Finally, in the

Abbreviations

complex environment, 22% fewer hypotheses and 10% fewer goals were produced and the solutions were found with 46% fewer KS executions.

In each of the environments, the new algorithms were effective in preventing redundant processing in areas where strongly believed, high-level results were found. This enabled the system to allocate resources for work in noisy areas and areas where the sensed signals were weak. Although the new algorithms caused the system to generate additional goals, most noticeably in the sec­ ond environment, the resulting improvement in focus­ ing capabilities resulted in a considerable reduction in the number of knowledge sources executed. Finally, the cost of processing goal relationships was significantly less than the cost of processing KSs. The savings were suf­ ficient to result in dramatic decreases in execution time required when the system used goal relationship mecha­ msms.

6 Conclusion

We have presented a taxonomy of goal relationships that include inhibiting goals. In addition, we have shown that mechanisms for accurately controlling the flexibility pro­ vided by the multi-level, cooperative knowledge source model of problem solving can be built as natural exten­ sions to the integrated data-directed and goal-directed architecture.

Goal relationships provide important information for making intelligent control decisions, and they a re a useful tool for representing the current state of problem sol v­ ing in a complex search space. Their use is applicable to tasks in which combined data-directed and goal-directed control is appropriate. In order to exploit goal relation­ ship mechanisms, it is necessary that the quality and characteristics of a KSI's output be roughly predictable and that data-directed goals be constructed so as to con­ tain all the possible outputs that a KS can produce based on the triggering data. Additionally, the computation of goal relationships, data-directed goals, and KS output set approximations must be inexpensive compared to the cost of executing a KS. Finally, it is also important that a data-directed goal's solution set not include a large num­ ber of potential solutions that can not be generated by a KS working on the triggering data. Otherwise, many goal relationships will be overlooked.

We are incorporating these concepts into mechanisms for real time control and investigating the use of cooper­ ating, independent, and competing goal relationships for use in complex focusing heuristics and in problem solving termination. We are also examining the potential ben­ efits of adding additional goal attributes indicating the expected amount of resources needed to satisfy a goal, the amount of work already invested in satisfying a goal, the expected number of solutions to a goal, and the like­ lihood of satisfying a goal. Finally, we intend to expand the notion of cooperation and attempt to reproduce the high-level planning results of Durfee and Lesser [Durfee and Lesser, 1986] through the use of goal relationships.