Next: CBR-TEAM: A multi-agent Up: Negotiated Retrieval Previous: Overview

Negotiated Retrieval Algorithm

Below, we briefly present a summary of the Negotiated Retrieval Algorithm. Interested reader is referred to [Nagendra Prasad, Lesser, &Lander1996][Nagendra Prasad, Lesser, &Lander1995] for a more formal treatment and empirical studies.

Negotiated Retrieval is viewed as a distributed constraint optimization problem where each agent has a set of subcase consistency constraints in addition to the local case base. These constraints arise in a number of ways:

A case can be viewed as a set of feature-value pairs. The set of constraints that an agent has may be defined on both "local" and "non-local" features. Local features of an agent are those features that the agent uses to represent its local subcases. Non-local features are those features that some other agent uses to represent its local cases. Thus, a constraint can be viewed as a relationship between subcases of one or more case bases and is enforced through interrelationships between features of these subcases.

A case has a number of associated attributes that involve measures of certain characteristics of a case and are functions of the feature values of a case. Examples of attributes include reliability, quality, uncertainty and cost. In addition to being acceptable to all agents, it is desirable that a case be optimized along the attribute set. These requirements lead to organization of an agent's constraints as soft constraints and hard constraints where the former set represents solution preferences and the later set represents those constraints that are relaxed only as a result of explicit recognition by the agents that the set is too constrained to lead to a mutually acceptable solution. Relaxing a soft constraint may only involve penalties in terms of loss of optimality in the desirable attributes. For example, relaxing a soft constraint may lead to less robust solutions. Softness of a constraint represents its degree of flexibility. On the other hand, hard constraints are generally not relaxed except with an explicit understanding that the resulting responses satisfy the query specifications only partially or are consistent with only a subset of the agents.

A partial case is a partially evolved response to a query. A partial case is obtained by composing the subcases from one or more agents but it is not yet acceptable to all agents (perhaps because it needs more subcases or because other agents have not checked it against their consistency constraints). Projection of a partial case on to a set of features is the set of feature-values pairs in the partial case for that set of features.

The agents execute the Negotiated Retrieval Algorithm (NRA) as follows:

Phase I: Local Retrieval

If an agent received feedback from other agents about previous violations, it first assimilates it (details of the assimilation process are provided later). Some of the agents, using the relevant portions of the user query and the presently available information on the problem-solving state (including previously tried solutions, conflicts they caused and feedback in the form of advice on violated constraints from other agents), retrieve the seed subcases around which the rest of the case evolves. Other agents have too poor a local view to perform retrieval without additional help and hence wait to extend partially assembled cases. If a seed agent fails to retrieve a case, it can relax some local constraints until it finds a case or gives up at certain point. In general, a locally retrieved subcase is re-instantiated in the present problem context during this phase. Re-instantiation could also involve adaptation of the retrieved subcase to the new context.

Phase II: Sub-case Integration, Partial Case Extension and Conflict Detection

Agents try to "merge" the local subcases to form larger partial cases. It involves checking for consistency and interactions among the sub-cases retrieved by different agents. In the situation where the agents are trying to physically represent the overall episode at a single central repository, the agents can easily obtain the relevant information for consistency checking by looking at the other agents' sub-cases in the central repository. However, integration need not necessarily lead to a combination of the sub-cases at a single physical location. In this situation, the agents have to exchange projections of partial cases. For example, agent wanting a consistency check on one of its partial cases by has to send to , a projection of that partial case with respect to the relevant features of the constraints at agent . Projection information alone is sufficient for Agent to check for the consistency of that partial case with respect to its constraints (more details can be found in [Nagendra Prasad, Lesser, &Lander1996]). If constraints are not violated then the subcases are considered "merged" due to their mutual consistency. Those agents who could not retrieve subcases due to insufficient information in Phase I, try to extend these partial cases by adding their subcases. An agent intending to extend a partial case obtains an appropriate projection of that partial case to serve as an anchor for the local subcase retrieval.

If any violations are detected during a merge or an extend operation due to poor or infeasible values on local or non-local features, go to Phase III; else exit.

Phase III: Conflict Resolution through Negotiation

Each agent categorizes its violated local constraints into pre-enumerated classes of violations and uses a set of conflict resolution strategies associated with each of these categories to generate a set of advice as feedback to itself and the other agents involved in the partial case that led to the conflicts. The set of advice could range from domain independent strategies to highly domain specific ones[Nagendra Prasad, Lesser, &Lander1996]:

    Some of the agents may do their local retrieval using similarity measures based on "closeness" of the retrieval requirements to the cases in the archive. Such agents can be advised to broaden their search by obtaining cases with poorer similarity values or different similarity measures.

    Some of agents may retrieve a case and massage it using an adaptation strategy to fit the new situation. An agent could advise another agent to modify the retrieved case in a different way - use a different adaptation strategy.

    In systems where it is possible for agents to be associated with some knowledge of the importance of a particular feature's values and constraints for the overall case, this knowledge can serve as basis for generating advice to relax a soft constraint involving certain parameters. Alternately, the advice can be in the form of changes to the values or ranges of certain features in order to obtain better local solutions.

    An agent detecting lack of progress either locally or at other agents (based on the projections it receives from those agents) could advise some of them to relax their hard constraints. This is expected to take the retrieval process to qualitatively different regions of the case base. Just as with soft constraints, the choice of which constraint to relax is based on system-wide knowledge or generic strategies associated with some or all of the agents about the importance of various types of constraints for the overall case.

    Some of the agents may have capabilities to analyze particular features of the solution space that lead them to recognize opportunities for more efficient customized search strategies. They can together decide to play out specific roles in this kind of customized search. Lander[Lander1994] presents a good example of a customized search called linear compromise where agents, upon recognizing the linear nature of their solution space, decide to exchange end points and extrapolate between them to find the intersection point as a mutual compromise solution.

Upon generating feedback, goto Phase I.

Assimilation of feedback advice from other agents enhances an agent's view of the non-local requirements. An agent assimilating feedback can indulge in a process as complex as the generation of feedback. It may involve relaxing a constraint or adding a new constraint to the local set of constraints. Assimilation may be context-sensitive, leading to constraints that are applicable only in specific contexts or to specific types of partial cases at the local agent. In addition, the assimilation process may also involve transformations where an agent uses the feedback from other agents to generate its own local constraints rather than directly incorporate the feedback.

The Negotiated Retrieval Algorithm is an asynchronous parallel distributed constraint optimization search to obtain a good overall episode assembled from case pieces. The asynchronous nature of the search arises from the fact that an agent could be in any phase of the NRA for a given case evolution at a given time. More than one partial case could be evolving simultaneously and an agent could be in different phases of Negotiated Retrieval for different partial cases at any given time. The NRA algorithm is very general and a system may go through only some or all of these phases to achieve coherent retrieval of good overall cases.

Another feature of Negotiated Retrieval Algorithm is its ability to work with heterogeneous agents. While we cast NRA as constraint optimization search, it is not essential that the agents represent these constraints in any particular form - they could be procedural or declarative and in multiple forms. Internally, the agents could be using disparate knowledge organizations or problem solving control organizations. Agent detects constraint violations based on projections that basically represent information about the features that this agent as well as some other agents know about. The only requirement is the ability of an agent to translate a projection or feedback into its local language or from its local language to the language of another agent. These types of translation mechanisms are commonly called "wrappers"[Genesereth, , &Ketchpel1994] and are used to enable a set of heterogeneous or stand alone systems to function as a multi-agent system.

Next: CBR-TEAM: A multi-agent Up: Negotiated Retrieval Previous: Overview
Mon Sep 16 17:23:45 EDT 1996