Also Known As

Brokered Resources, Implicit Invocation

Intent

The Sponsor-Selector pattern can be used to provide a mechanism for selecting the best resource for a task from a set of resources that changes dynamically. It allows a software system to integrate new resources, and new knowledge about resources, at run-time in a way that is transparent to users of the resources. This pattern is based on the idea of separating three kinds of responsibilities: knowing when a resource is useful, selecting among resources, and using a resource.

Example

Consider a software system engaged in the task of medical diagnosis. The system has at its disposal a set of sub-systems capable of performing particular diagnostic sub-tasks. The task/sub-task structure may look something like this:

At each point during a diagnostic session, the system faces the question: Which sub-task should be performed next? This is the question of problem-solving control. Early systems of this kind performed their sub-tasks sequentially, or in some other prescribed order, but such "hard coded" control produced unsatis-factory results. Often, the data provided by previous actions indicated the need to break out of the prescribed sequence -- say, to gather more specific data while doing causal reasoning about a hypothesis -- in order to arrive at the best diagnosis in a timely manner.

Ideally, one would think of the diagnostic system as having an agent responsible for performing each task in this hierarchy. At run-time, the system would like to select the most appropriate sub-task agent to invoke, based on the context information available at that point. This involves determining which of the sub-systems is likely to make the most progress toward the goal of arriving at a useful diagnosis.

Situations like this arise in many domains: An operating system may want to select the best process scheduling algorithm based on the current state of the system. A central web server may want to balance access load across a family of web servers based on their current performance capabilities. A communication network may want to select the best route for a message based on the current state of the network and its components. In all of these examples, a system needs the ability to select a resource dynamically from a set of resources whose attri-butes may be changing at run-time.

Context

You are building a system in which the set of resources used to perform some task, or the system's knowledge about those resources, can change, either statically or dynamically.

Problem

Sometimes, a class has a number of other classes (resources) with which it can collaborate, but it cannot know until run-time which of these resources it will need in a specific situation. Furthermore, the set of potential collaborators may change over time, either statically by programmer modification or dynamically during system execution. At run time, the class would like to select the "best" collaborator based on the context information available at that point.

However, designing such a control mechanism introduces new problems. One solution to this problem is to encode a resource selection mechanism directly into the system. Such a solution leads to two kinds of difficulties: If the programmer adds a new resource to the system, the system's control knowledge must be modified to make it accessible. And if a new resource is added to the system dynamically at run-time -- say, through some form of machine learning -- the system is unable to use the resource, because its control knowledge makes no reference to the new resource.

A second solution is to separate the selection mechanism into a separate class that specializes in control decision-making, using the Blackboard pattern. This solution makes the system immune to modification in the face of new resources. But this still confounds knowledge about resource applicability with knowledge about resource preference, making the new "selection" class prone to the same difficulties when new resources are added to the system.

Any solution to this problem should bring the following forces into equilibrium:

• The system should be able to access resources whenever appropriate.
• It should be possible to add, change, or remove resources, either statically or dynamically, without making extensive modifications to the system.
• The utility of some resources cannot or should not be determined until run-time.

Solution

Introduce sponsor and selector components to achieve a higher degree of decoupling between the system and the resources it uses. Each resource has a sponsor whose responsibility is to recommend when it can be used. The selector takes these recommendations as input and decides which resource should be used.

In the course of execution, whenever the system needs a resource to proceed, it sends a request to the selector in charge of the corresponding resource set. The selector then broadcasts the request to all of the sponsors in the set. Each sponsor evaluates the applicability of its resource and sends a rating back as its answer. The selector then uses these ratings, along with other preference knowledge and context information, to select the "best" resource for the client in the current context.

A new resource can be added to the system either statically or dynamically by building a sponsor for it and registering the new sponsor with the appropriate selector. In many situations, the creator of the resource will also need to register specific preferences that relate to the new resource with the selector as well.

The key to the Sponsor-Selector pattern is the separation of three fundamentally different responsibilities: recommending a resource, selecting among resources, and using a resource.

Structure

The Sponsor-Selector pattern comprises three kinds of components: a selector, a set of sponsors, and a set of resources. Together, these components provide a set of services to some client.

A resource is any one of a set of objects that has specific functionality in some larger context.

Each sponsor contains knowledge of when its resource is appropriate for use. This knowledge makes reference only to local features of the environments in which the resource is useful. If possible, a sponsor should make no reference to any resource other than its own.

The selector embodies knowledge of which resource to prefer in particular kinds of situation. This knowledge can express preferences among groups of resources and can make reference to global features of the context, such as issues of run-time efficiency and correctness. The selector sends requests to the set of sponsors and receives a set of ratings in return. It then uses these ratings to select a resource for use in the current context.

The client is a system that uses the resources to perform some part of its task. It sends requests to the selector when it needs a resource and invokes the resource that is returned by the selector.

In our example, the client is the diagnostic system. The resources are the sub-systems that perform parts of the diagnostic system's task, for example, the hypothesis builder and the causal reasoner. Each sub-system has an associated sponsor that indicates whether or not the diagnostic system should invoke the sub-system in a given situation. The task selector uses its knowledge to select the sub-system to invoke next, based on the ratings returned by the sponsors and information about the diagnostic system's current context.

Dynamics

A Sponsor-Selector system operates in the following manner.

The client reaches a point in its activity at which it needs a resource in order to proceed, so it asks the selector for a resource. The selector broadcasts a request to all sponsors, each of which rates its resource and returns a rating for the resource. The selector uses these ratings to select the most appropriate resource and then asks the corresponding sponsor for its resource. The selector then returns this resource to the client. The client uses the selected resource in the desired way.

In our example, the diagnostic system completes some activity and must begin working on a new sub-task. It asks the task selector to select the next sub-task to work on. The task selector broadcasts a request to all sub-task sponsors, which rate their sub-tasks for applicability in the current context. The task selector then uses these ratings to select the next sub-task and asks the corresponding sponsor for its resource. The selector returns this sub-task to the diagnostic system, which begins working on the selected sub-task

Implementation

Several common patterns can be used to implement the components of the Sponsor-Selector pattern. Sponsors may be implemented using the Proxy pattern, since they stand in the place of resources during the selection process. The selector may be implemented using the Broker pattern, which coordinates communication between the client and its decoupled resources. Finally, if the resources themselves are methods to be invoked, they can be implemented using the Strategy pattern.

Regardless of how the components of the pattern are built, three main implementation decisions must be made:

1. How does each sponsor rate the appropriateness of its resource? Each sponsor should be coded with only local considerations in mind: Is my resource appropriate in the current context? It should not make reference to any other resources or any other global questions (such as client-specific timing issues), if at all possible. Otherwise, modifiability of the structure is impaired. The Memento pattern can be used to transport relevant state information from the client to the sponsors.

2. What constitutes a rating? In some domains, sponsors may be able to rate their resources quantitatively on a continuous scale, such as a real number between 0 and 1, which the selector then combines using a continuous function. However, experience in many domains has shown that often qualitative ratings of applicability are more appropriate. One common approach of this type is to have sponsors rate their resources on a scale from "highly applicable" through "neutral" to "highly inapplicable". Using qualitative ratings of this sort makes it easier to build selectors that more nearly correspond to the judgments made by human experts in the domain.

3. How does the selector combine the ratings to select a particular resource? The selector ordinarily uses the ratings returned by its sponsors as its primary criterion for selection. A selector may just select the highest-rated resource, breaking ties using either a default preference on resources or a random choice from among the resources with the highest ratings. But it may also need to apply more global knowledge that goes beyond the scope of any single sponsor (e.g., comparisons among specific resources). In such cases, it may have to use state information from the client that is outside the scope of the individual sponsor's decision.

Two other implementation issues should be considered:

1. Does the selector directly invoke the selected resource or return the resource to the client? Direct invocation by the selector makes more sense when the resources are methods to be invoked, since the client may be willing to pass control to the selected method. One advantage of direct invocation is that resources no longer need to share a common interface; only the resource's sponsor needs to know the resource's interface. In this case, the sponsors serve as Adapters between the client and the resources. Returning the resource to the client is more appropriate when the resource plays both a static role (as data store) and a dynamic role (as behavior) for the client, since the client may then need more prolonged interaction -- and thus a common interface -- with the resource.

2. Can the sponsor objects be assimilated directly into the resources? If sponsorship decisions are trivial, the structure of Sponsor-Selector can be simplified by adding a rating behavior to the resource objects. This can be useful when the rating behavior can be implemented in a superclass and inherited by all of the resource classes. Such an implementation resembles that of the Blackboard pattern, where the selector plays the role of the control object and the resource plays the role of the knowledge source.

3. How costly is the rating process? As the cost of rating resources becomes higher, the client will pay a run-time penalty for its flexibility. The implementor of a Sponsor-Selector pattern must be sensitive to potential performance issues. One way to use Sponsor-Selector in the face of high rating costs is to use the "parallel resource selection" variant described below.

4. Must resources be able to share knowledge? One of the costs that can be associated with a high degree of modularity is a difficulty in sharing domain knowledge among the resources, which can lead to replicated implementations. One way to address this problem is to use Singletons and Flyweights to encode knowledge that must be shared.

Example Resolved

The use of the Sponsor-Selector pattern resolves the forces at play in our diagnostic system example. By creating sponsors for each sub-task and encoding the selection mechanism in the task selector, changes to the task structure of the system are localized.

Suppose that we wished add a new sub-task, say hypothesis identification, to the system. This sub-task might involve selecting a new hypothesis to consider while building the system's diagnosis. A programmer could make this addition to the system by:

• encoding the sub-task as a new resource,
• encoding local knowledge of when to identify a new hypothesis or not in a sponsor for the resource, and
• registering the new sponsor with the task selector.

No other changes to the selector or to the client would be necessary.

However, since all change is localized around the new sub-task, the addition could also be done both by the system itself at run-time. During execution, the system could use some form of machine learning to discover and encode new diagnostic knowledge. When a new sub-task is discovered, all information that is needed to add the resource to the system (what it is and when it is useful) is created as a part of the learning process. The final step of registering the new sponsor with the selector involves little or no change to the structure of the selector itself.

Variants

A number of interesting variations of Sponsor-Selector are possible:

1. Parallel resource selection. Each sponsor is an independent agent charged with the rating of an individual resource's applicability and utility. As such, they can be executed in parallel on separate processors, or in the background on the same processor, while other processes are active. The selector can then be implemented as an "anytime algorithm," processing sponsor ratings as they become available and providing a resource selection to the client on demand.

2. Hierarchies of Sponsor-Selector modules. Suppose that one resource that is available to the client is itself essentially a set of resources. For example, the data validation sub-task in our diagnostic system may have several different methods by which it can perform its task. In such a situation, multiple Sponsor-Selector patterns can be composed to form a hierarchy.

   

   Figure 5: A Hierarchy of Sponsor-Selector Modules

   A hierarchy of Sponsor-Selector patterns provides a means for organizing complex resource sets, such as the many tasks, sub-tasks, and methods of a large system, in a way that promotes system modifiability in the face of change.

Known Uses

The first documented use of Sponsor-Selector was in DSPL (Brown and Chandrasekaran, 1986), which used the pattern in a mechanism for selecting design plans in a system that designed air cylinders for aircraft. The mechanism was incorporated into a shell for building knowledge-based systems that do "routine design," in which much or all of the design task is accomplished through the use of pre-enumerated design and redesign plans.

TIPS (Punch and Chandrasekaran, 1993) generalizes Sponsor-Selector into a mechanism for making dynamic control decisions about sub-tasks. Punch has applied TIPS in the construction of a medical diagnostic expert system.

FAULTY-II (Benjamins 1993) goes further by using a Sponsor-Selector pattern as the basis of an application framework for dynamically selecting a method for performing each sub-task in explicitly represented task structures.

IPCA (Decker et al., 1994) uses Sponsor-Selector as the basis for control plan selection and execution in a system that controls microwave composite material processing in a soft real-time environment.

Goel and his colleagues (1994) have used Sponsor-Selector for dynamic method selection in navigational planning for mobile robots. Experiments in this domain confirm that Sponsor-Selector is a good design solution in situations where the client application is learning new control knowledge. As the planner acquires domain knowledge, Sponsor-Selector enables the agent to incorporate the new knowledge dynamically into its problem solving and to select the method that is indicated by that knowledge. The planner has been embodied in a physical robot that demonstrates the effectiveness of its plans.

Landauer and Bellman (1995) have proposed a new technique for developing, integrating, and managing complex software systems based on an idea very similar to that of the Sponsor-Selector pattern. Their technique uses two types of component, wrappings and managers. Wrappings are qualitative information about a system component: how to use the component, when and why to use it, and in what combinations they can be used. Managers are algorithms that select and combine components based on the information in their wrappings. This technique extends Sponsor-Selector to apply to all components of a system at all times.

Consequences

Many of the consequences that follow from using Strategy also follow from using Sponsor-Selector. Sponsor-Selector offers the following benefits:

• High degree of modularity. Resources can be added, modified, or reimplemented with no effect on other resources or on client code. Only the resource's sponsor must be modified. In the case of a new resource, the selector is modified only in that the new sponsor must be registered with it.

• Decision control is made explicit and independent from other components of the system. Sponsor-Selector further improves on the Strategy pattern's separation of method and client by further decoupling selection of the ConcreteStrategy from the Context. Strategy leaves the client with the job of selecting the appropriate ConcreteStrategy to instantiate in the client. This can clutter the client with extra data examination code, knowledge that is not part of the client's primary task (thus blurring the explicitness of its representation), and unwieldy control statements.

Sponsor-Selector also imposes some drawbacks:

• Potentially tight coupling between the Client and the Selector. Pulling all of the selection knowledge out of the client may be unwise. Selection knowledge may be so context-specific as to be (1) not reusable as a separate object and/or (2) easier to express directly in the client, since large amounts of information may need to be passed from client to selector.

• Potentially tight coupling between the Selector and the Sponsors. The Sponsor-Selector pattern may be inappropriate if sponsors need to take into account knowledge about the relative quality of their methods' solutions in a particular context or global constraints to be placed on the resource. For instance, if a there are global bounds placed on the time of computation of the resource, it may be difficult to build a local sponsor capable of taking such knowledge into account.

  One way to address these potential couplings is to use the Observer pattern as a mechanism for allowing selectors and sponsors to view external context information without encoding context into these components.

• Cost of indirection in hard real-time environments. Decker (1994) has argued that deadlines associated with hard real-time processing can pose problems for a Sponsor-Selector architecture. In cases where the costs of indirection and rating exceed the resources available to a system, Sponsor-Selector may be an inappropriate pattern.

See Also

As described above, Sponsor-Selector may incorporate many of the features of the Broker, Proxy, and Strategy patterns. Mementos, Observers, Singletons, and Flyweights may be used to address some of the issues that arise when implementing Sponsor-Selector.

Sponsor-Selector is similar to the Blackboard pattern in its decoupling of control from the resources that comprise a system. But Sponsor-Selector also adds an extra degree of flexibility by further decoupling knowledge of when a knowledge source is useful (the sponsor) from the knowledge source itself (resource). This flexibility can be realized by adding an extra layer to the system's architecture.

Client-Dispatcher-Server also resembles Sponsor-Selector in its decoupling of the client from the resources that serve it. But Sponsor-Selector further prescribes that knowledge of when a knowledge source is useful be decoupled from the knowledge of which resource to use at any point in time. The Client-Dispatcher-Server pattern makes no commitment in this respect. Both Sponsor-Selector and Client-Dispatcher-Server can be viewed as architectural forms of implicit invocation (Notkin et al., 1993), an idea that can be applied even at the level of general-purpose programming languages.

When taken to the level of wrappings (Landauer and Bellman, 1995), Sponsor-Selector can be viewed as a mechanism for implementing the Reflection pattern. Sponsor-Selector provides a means by which a system can reflect about its own sub-tasks and methods and select resources when they are most useful for achieving the system's goals. Furthermore, Sponsor-Selector allows the system to fully integrate new resources at run-time while retaining its ability to reflect about them.

Acknowledgements

An earlier version of this pattern appeared at PloP'96. Shepherd Chris Landauer first suggested the relationship between Sponsor-Selector and the ideas of wrapping and implicit invocation. I thank the members of PloP'96 Working Group 4 for their valuable criticisms and suggestions for improvement. Frank Buschmann, Eric Hughes, and Peter Sommerlad were especially helpful, providing thorough written comments on my paper. Finally, I thank Bobby Woolf, whose thoughtful comments helped me to think about how readers outside the domain of knowledge-based systems might interpret my pattern.

References

1. Benjamins, Richard. Problem Solving Methods for Diagnosis. Ph.D. Thesis, University of Amsterdam, 1993.

2. Brown, David, and B. Chandrasekaran. Knowledge and Control for a Mechanical Design Expert System. IEEE Computer, 19:92-101, July 1986.

3. Buschmann, Frank, Regine Meunier, Hans Rohnert, Peter Sommerlad, and Michael Stal. Pattern-Oriented Software Architecture. John Wiley and Sons, New York, 1996.

4. Decker, David, Bill Punch, Jim McDowell, and Jon Sticklen. An Intelligent Control Architecture for the Microwave Fabrication of Composite Materials Based on the Generic Task Approach to Knowledge Based Systems. In Proceedings of the AAAI Fall Symposium on Intelligent Systems, New Orleans, November 1994.

5. Gamma, Erich, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns. Addison-Wesley, New York, 1995.

6. Goel, Ashok, Khaled Ali, Michael Donnellan, Andres Gomez, and Todd Callantine. Multistrategy Adaptive Navigational Path Planning. IEEE Expert, 9(6):57-65, December 1994.

7. Landauer, Christopher, and Kirstie Bellman. Knowledge-Based Integration Infrastructure for Complex Systems. TAC Technical Report, 1995.

8. Notkin, David, David Garlan, William G. Griswold, and Kevin Sullivan. Adding Implicit Invocation to Languages: Three Approaches. In Proceedings of the Object Technologies for Advanced Software Conference, Springer-Verlag, Berlin, 1993.

9. Punch, Bill, and B. Chandrasekaran. An Investigation of the Roles of Problem-Solving Methods in Diagnosis. In Second Generation Expert Systems, ed. by J.M. David, J.P. Krivine, and R. Simmons. Springer Verlag, Berlin, pages 673-688, 1993.

10. Punch, Bill, Ashok Goel, and David C. Brown. A Knowledge-Based Selection Mechanism for Strategic Control with Application in Design, Assembly, and Planning. International Journal of Artificial Intelligence Tools, 4(3):323-348.