Understanding the Role of Negotiation in Distributed Search Among Heterogereous Agents

1 Introduction

The current state of knowledge-based technology is such that almost every application system is built from scratch. In order to move beyond the prohibitive cost of constantly reinventing, rerepresenting, and reimplement­ ing the wheel, researchers are beginning to examine the feasibility of building application systems with reusable agents [Neches et al., 1991]. A reusable agent is designed to work without a priori knowledge of the agent set in which it will be embedded, instead using a flexible, reac­ tive approach to cooperation. Although this flexibility can lead to inefficient problem solving, an agent can of­ ten gather information about the agent set as problem solving progresses to improve efficiency.

This research was supported by ARPA under ONR Con­ tract #N00014-92-J-1698. The content of the information does not necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred.

Multi-agent systems do not traditionally acknowledge the role of conflict among agents as a driving force in the control of problem-solving activity. In reusable-agent systems, however, conflict is inevitable since agents are implemented at different times by different people and in different environments. We present a distributed­ search algorithm, negotiated search, that uses conflict as a source of control information for directing search ac­ tivity across a set of heterogeneous agents in their quest for a mutually acceptable solution.

The negotiated-search algorithm has been successfully incorporated into two implemented systems. In [Lan­ der and Lesser, 1992b], we describe distributed search in the context of a seven-agent steam condenser de­ sign system and discuss how different operator/ agent assignments within the ne~otiated-search algorithm af­ fect problem solving. In [Lander and Lesser, 1992a], a two-agent contract negotiation system is presented, and negotiated search is compared to a search strat­ egy that is tailored to characteristics of that environ­ ment. Through analysis of the environment and search algorithms, we show the versatility and effectiveness of negotiated search in reusable-agent systems while also pointing out that customized search strategies are in­ flexible but can improve system performance when they can be applied. In this paper, we describe negotiated search from an application-independent perspective.

The need for a flexible algorithm to support reusability and heterogeneity motivates particular aspects of nego­ tiated search:

• Conflict, negotiation, and democratic determination of acceptability are integral parts of the algorithm.
• Agent coordination is accomplished through clearly defined individual roles in the evolution of a shared solution. These roles are realized as operators that accomplish state transitions on shared solutions.
• Operators represent standard and widely available search and information-assimilation capabilities. A particular agent may instantiate all defined opera­ tors or some subset of defined operators.
• Whenever possible, feedback is used to refine the perceived search spaces of individual agents to more closely reflect the true composite search space.

TEAM agents are not hostile and will not intentionally mislead or otherwise try to sabotage another agent's rea­ soning. They are cooperative in the sense that an agent is willing to contribute both knowledge and solutions to other agents as appropriate and to accept solutions that are not locally optimal in order to find a mutually­ acceptable solution. Each agent is a stand-alone system with specific capabilities that allow it to be included in an integrated multi-agent system. We assume that agents can be heterogeneous in architecture, inference engines, evaluation criteria and priorities for solutions, and in long-term knowledge. Each agent does its own in­ ternal scheduling and has private data, knowledge, and history mechanisms.

In negotiated search, agents interleave the tasks of 1) local search for a solution to some subproblem; 2) inte­ gration of local subproblem solutions into a shared solu­ tion (the composite solution); 1 3) negotiation to define and refine the shared search space of the agents; and 4) assessment and reassessment of emerging solutions.

In the remainder of the paper, we first motivate the development of our negotiated-search model by present­ ing an intuitive description of negotiation and, from this foundation, constructing an algorithmic model of the ne­ gotiation process. The next section details negotiated search from a state-based perspective similar to that used by von Martial to describe negotiation protocols in distributed planning [von Martial, 1992]. We then present seven· basic negotiated-search operators. The fi­ nal section briefly describes the status of the implemen­ tation and extensions to this model that are not covered in this paper.

2 An Initial Perspective on Negotiation

In this section, we begin with an intuitive description of negotiation:

One agent generates a proposal and other agents review it. If some other agent doesn't like the proposal, it rejects it and provides some feedback about what it doesn't like. Some agent may generate a counter-proposal. If so, the other agents (including the agent that generated the first proposal) then review the counter-proposal and the process repeats. As information is exchanged, conflicts become ap­ parent among the agents. Agents may respond to the conflicts by incrementally relaxing indi­ vidual preferences until some mutually accept­ able ground is reached.

This example captures the primary characteristics that one would expect to see:

• proposals are generated by one or more agents
• agents evaluate proposals based on their individual criteria for solution acceptability
• agents provide feedback about what they like or don't like about particular proposals, resulting in a progressively better understanding of the shared requirements for solutions over time

1 Sathi similarly uses the term composition as the name of a specific search operator that combines local informa­ tion [Sathi and Fox, 1989]

• agents can play different roles in the negotiation process, e.g., an agent can be a reviewer for an­ other agent's proposal and then be a generator for a counter-proposal
• conflicts exist among the agents' requirements for acceptable solutions
• agents incrementally relax their solution require­ ments to reach agreement
• the decision to accept or not accept a proposal is a joint, democratic process

Some extensions to the definition are required. For example, it assumes that a proposal becomes a solution when it is accepted by all agents. However, this assump­ tion rules out situations in which high-level problems are decomposed and each agent works on some subprob­ lem. In this case, the proposal an agent makes does not represent a complete solution but rather some compo­ nent of a solution that interacts with other components through shared attributes. Evaluation is then indirect since an agent cannot evaluate proposals for interact­ ing components that are outside of its domain of exper­ tise. In negotiated search, an agent evaluates an external interacting-component proposal by creating and evalu­ ating a compatible local proposal (i.e., one that has the same values for shared attributes), thereby focusing on how the external proposal affects local quality.

Although a proposal includes the information required to implement a solution, it provides only a surface-level view of the reasoning that went into creating it. It is sometimes possible to make guesses about other agents' requirements that could be used in generating counter­ proposals. However, in the general case of reusable agents, external local evaluation criteria for solutions cannot be predicted, nor can they be inferred from the "snapshot" provided by a proposal. For proposals and counter-proposals to be related, there must be a deeper understanding of the shared search space of the agents. This understanding is achieved through a feedback sys­ tem that can be separate from the proposals.

3 Negotiated Search

Artificial intelligence researchers have previously used the term negotiation with respect to conflict resolu­ tion and avoidance [Adler et al., 1989; Klein, 1991; Lander and Lesser, 1992a; Sycara, 1985; Werkman, 1992], task allocation [Cammarata et al., 1983; Durfee and Montgomery, 1990; Davis and Smith, 1983], andre­ source allocation [Adler et al., 1989; Conry et al., 1992; Sathi and Fox, 1989; Sycara et al., 1991]. Negotiation is sometimes treated as an independent process that is used to select one of a set of existing alternative solu­ tions [Zlotkin and Rosenschein, 1990] rather than as an inherent part of a solution-generation process. It can be difficult under conditions where agents are hostile and unwilling to share private information [Sycara, 1985]. Negotiation can occur among peers [Cammarata et al., 1983; Lander and Lesser, 1992b], through a mediator or arbitrator [Sycara, 1985; Werkman, 1992], or hier­ archically through an organization [Durfee and Mont­ gomery, 1990; Davis and Smith, 1983]. It can occur at either the domain or control level of problem-solving. Laasri et. al. describe the recursive negotiation model, a general model of multi-agent problem solving that details various situations that can potentially benefit from nego­ tiation [Laasri et al., 1992]. In examining this model, it becomes clear that negotiation is a pervasive process that remains relatively untapped by current computational systems. In developing the negotiated-search model, we have tried to capture the key requirements for negotia­ tion without restricting the domain, task decomposition, or organizational model of the agent set.

Several researchers have developed algorithms and heuristics for constraint-directed distributed search in situations involving multiple homogeneous agents [Sathi and Fox, 1989; Sycara et al., 1991; Yokoo et al., 1992]. 2 We extend this work to handle situations where heterogeneous agents may have different or multiple local problem-solving paradigms, instantiate different search operators, and where agents may not be able to pro­ vide specific information to other agents or understand information received from other agents. The negotiated­ search algorithm is particularly suitable to this style of problem solving because 1) the required search opera­ tors represent standard search capabilities; 2) the search operators can be flexibly assigned across the agent set according to the search capabilities of each agent; and 3) agents use incremental relaxation of solution require­ ments to reach mutual acceptability as an inherent part of problem solving.

3.1 The Search Process

Search is initiated by a problem specification that de­ tails the form of a solution and values, preferences, or constraints on some attributes of that solution. This specification is placed in a centralized shared memory as are emerging composite solutions. 3 Some agent(s) uses constraining information from the specification and its local solution requirements to propose an initial partial solution called a base proposal. The base proposal is then extended and evaluated by other agents during future processing cycles. When a particular solution cannot be extended by some agent due to conflicts with existing so­ lution attributes, there are two possible outcomes: 1) if the conflict is caused by the violation of some hard (non­ relaxable) requirement, the solution path is pruned (e.g., arc 5 in Figure 1); or 2) if the conflict is caused by the vi­ olation of some soft (relaxable) solution requirement, the solution is saved and viewed as a potential compromise (e.g, arc 9 in Figure 1). In the first case, no more work will be done on that solution, and, to the extent that the violated requirement can be communicated to and assim­ ilated by other agents, future counter-proposals will not violate that same requirement. In the second case, the violated requirement may eventually be relaxed and, if that happens, the potential compromise will become a viable solution again. Future counter-proposals will take the violated requirement into account but are not guar­ anteed to avoid the same conflict, since other alternatives may be worse.

2 Agents may control different resources and have different constraints on solutions, but they share a single underlying problem-solving paradigm and knowledge representation.

3 Each agent also has a local short-term memory where it stores intermediate results and/or component proposals that are linked to composite solutions in shared memory.

In both of the above cases, conflict is used as the trig­ ger for the communication of feedback information. In multi-agent systems, it is always problematic to decide what information should be exchanged and when that exchange should take place. In general, agents want to minimize the amount of information they share since it is expensive both to communicate information and to assimilate information. On the other hand, sharing in­ formation that will specifically help another agent avoid future conflicts is generally cost effective since it elim­ inates the expense of generating unproductive solution paths [Lander, 1993]. In negotiated search, an agent that receives conflict information from another agent can choose whether or not to prune its own search to respect that information (see Section 4.5).

Multiple solution paths can be concurrently investi­ gated in negotiated search. Agents are free to initiate solutions at any time either because there aren't any promising solutions in the current solution set or because they have no other work to do. Advantages to main­ taining multiple paths include exploiting the potential for concurrent activity and having the ability to directly compare different potential compromises. There are dis­ advantages to concurrently exploring multiple solution paths however: there will be multiple partial solutions that have to be stored at all times, requiring additional memory resources. There is also overhead involved in focusing on a promising solution path at a particular point in problem solving, both from the local and global perspectives, and in managing the links between solu­ tion components along each path. The number of open solution paths is highly dependent on the domain, the number of agents, and the control policies of individual agents. This number can be controlled through param­ eter settings in TEAM and through the specification of which negotiated-search operators will be active for each agent in the agent set.

3.2 A State-Based View of Negotiated Search

Figure 1 provides a state-based view of the transition of a composite (shared) solution from its initial state (a problem specification) to a termination state (an infea­ sible solution, an unacceptable solution, or a complete acceptable solution). In this figure, states are defined in terms of three attributes of composite solutions: ac­ ceptability, completeness, and search-state. The possi­ ble values for acceptability are acceptable, unacceptable, and infeasible. Possible values for completeness are com­ plete and incomplete. Note that complete means that all agents have had the opportunity to extend or critique the solution. A solution with all required components can still be waiting for critiques from other agents and is not considered complete in that case. Search-state can take the values initial or closed.

A negotiated-search operator is a search function ap­ plied by an agent. Each operator has a generic form that is expressed in an agent language defined by TEAM, specifying its inputs, outputs, and functionality. The deci­ sion to apply a particular operator to a problem-solving situation is made by an agent within its local view of the problem-solving situation. The arcs in Figure 1 are negotiated-search operators that can be applied by some agent to a solution.

Each agent instantiates one or more of the negotiated­ search operators: initiate-solution, extend-solution, critique-solution, and relax-solution-requirement. In ad­ dition, TEAM instantiates the terminate-search operator. These operators will be described in detail below, but we provide an overview here to provide a sense of their functionality. Initiate-solution is applied by an agent to generate a base proposal that will be used as the basis for a new composite solution. Extend-solution is applied by an agent to: 1) add a component proposal to a com­ posite solution; 2) evaluate the composite solution from a local perspective; and 3) provide feedback information if conflicts are detected. Critique-solution is applied to: 1) evaluate a composite solution (without generating a component proposal); and 2) provide feedback informa­ tion if conflicts are detected. Relax-solution-requirement is applied to: 1) select a local requirement to relax; 2) update the local database to effect the relaxation; and 3) reevaluate existing solutions in light of the relaxation. Terminate-search is applied by TEAM to change the state of the problem solving from initial to closed, thereby changing the termination status of solutions.

The negotiated-search algorithm is applied by a set of agents, .A. Let .A = {A1, A2, A3} and assume that A1 initiates a solution, A2 extends the solution, and A3 cri­ tiques some aspect of that solution. We examine a typi­ cal search in which a conflict occurs. A1 first applies the operator initiate-solution to a problem specification and produces a partial acceptable solution (arc 1 ). Then A2 applies extend-solution without detecting a conflict. Although the solution now has all components specified, it is not complete until all critiques have also been received. Therefore the solution is now partial and acceptable (arc 3) . A3 next applies critique-solution, detects a conflict, and evaluates the solution as unacceptable (arc 8). This solution remains as it is for some amount of time while the agents are working on other solution paths. When further search fails to produce an acceptable solution, A3 decides to relax the requirement that made this solu­ tion unacceptable. The solution is now acceptable to A3 and, since it was already complete, it reaches the termi­ nation state of complete acceptable solution ( arc15). In this way, various paths through the state diagram can be achieved by the agent set.

Although the above example describes a sequential or­ dering of operator applications, TEAM permits concur­ rency except where there are domain-dependent opera­ tor preconditions that force sequential execution. Con­ currency requires that TEAM have mechanisms for han­ dling conflicts that occur due to the simultaneous de­ velopment of extending proposals and criticisms. These mechanisms are discussed in [Lander, 1993].

4 Negotiated Search Operators

In this section, we present a detailed description of the negotiated-search operators. Notice that the operators depicted in Figure 1 work at the surface level of problem solving: they move a particular solution through various states to a termination state. They do not address the issue of feedback and its effect on problem solving. Later in this section, we will present two operators that an agent applies to assimilate conflict information into its knowledge base, thereby refining its view of the search space.

4.1 Initiate-Solution

Initiate-solution is the basic operator for initiating solu­ tions. It is applied within the agent's view of solution requirements: local requirements, those imposed by the problem specification, and any known external require­ ments learned from other agents. Given these require­ ments, it creates the base proposal. Initiate-solution is executed by one or more agents at system start-up time, and may be repeatedly executed as earlier proposed so­ lutions are rejected by other agents or if alternative solu­ tions are desired. If earlier solutions have been proposed and rejected, the initiating agent may have received con­ flict information that will influence the generation of new base proposals.

At least one agent must instantiate initiate-solution; however, instantiating it at multiple agents is likely to result in a more diverse set of solution paths and more thorough coverage of the composite solution space. De­ pending on characteristics of the agents and agent set, it may also have a distracting effect. Trade-oft's between coverage and distraction are a ubiquitous problem in dis­ tributed systems and are discussed generally in [Lesser and Erman, 1980] and specifically with resrect to nego­ tiated search in [Lander and Lesser, 1992b .

When no base proposal can be found under the exist­ ing set of requirements, an agent can relax requirements to expand the search space. If there are requirements on solutions that come from information communicated by another agent (external requirements), the initiating agent can ignore one or more of these requirements in its own search. Notice that the other agent does not ac­ tually relax the requirements. In this way, each agent chooses the set of requirements, both internal and ex­ ternal, it will attempt to satisfy. When known exter­ nal requirements are violated, the proposal is suggested as a possible compromise rather than a fully acceptable solution. The external agent that has its requirements violated in the compromise proposal cannot be forced to accept it. Because the selection of a mutually ac­ ceptable solution is democratic, each agent votes on the acceptability of a solution. The external agent that has the violated requirement{s) can initially vote that the solution is unacceptable but, if it does not find a bet­ ter alternative, it may eventually agree to accept this compromise.

If there are no relaxable external solution requirements or if the external requirements are inflexible, an agent can relax some local requirement. If no base proposal can be found at any level of external or internal requirement relaxation, the agent returns a failure along with any conflict information it can generate that describes why it failed. TEAM returns a failure if no agent can generate a new base proposal and all previously created solutions have been found to be infeasible.

4.2 Critique-Solution and Extend-Solution

The critique-solution operator is applied by an agent to evaluate a partially or fully specified composite solution. The extend-solution operator is applied by an agent to extend and evaluate a partially specified composite so­ lution. These two operators will be described jointly be­ cause of their similarity. The input for these operators is a composite solution that was initiated by another agent. The output for critique-solution is an evaluation, and when a conflict is detected, conflict information. The output for extend-solution is a proposal, an evaluation, and, when a conflict exists, conflict information.

The extend-solution operator is required in domains where solutions comprise interacting components and each component is developed by an expert agent. The component that an agent develops with extend-solution must be compatible with the solution being extended (it must have the same values for solution variables that overlap) . The agent executing the operator searches for a compatible proposal under its known solution require­ ments and the requirements imposed by the assigned pa­ rameter values of the solution to be extended.

Although we will not discuss critique-solution fur­ ther, the following discussion of extend-solution gen­ erally applies to both operators, except that critique­ solution evaluates the existing composite solution rather than creating and evaluating a compatible proposal. In extend-solution, if a compatible proposal is found that does not violate any local solution requirements, it is re­ turned as an acceptable proposal. If the best compatible proposal found violates some relaxable (soft) local solu­ tion requirements (where the best proposal is one that maximizes local evaluation), it is returned as unaccept­ able along with information that describes the conflict. Although currently unacceptable, future requirement re­ laxations may change its status and, therefore, the so­ lution is saved as a potential compromise. In the final case, no compatible proposal can be found without vio­ lating nonrelaxable (hard) requirements of the executing agent. In this case, the agent fails and the solution path is marked as infeasible. Conflict information is returned whenever possible that describes why the path is infea­ sible, i.e., what hard requirements were violated.

4.3 Relax-Solution-Requirement

Relaxation of solution requirements is a necessary part of negotiated search. In order to terminate problem solv­ ing, agents must reach mutual acceptability on one or more solutions. Acceptability is defined as an attribute of a composite solution as shown in Figure 1. If any agent locally evaluates a solution as unacceptable, the solution is considered globally unacceptable. However, as can be seen in that figure, a solution that is unac­ ceptable at some point in time can later become accept­ able when the agent or agents that reject it relax their solution requirements.

There are three primary forms of relaxation, unilat­ eral relaxation, feedback-based relaxation, and problem­ state relaxation. Unilateral relaxation occurs when an agent decides to relax a requirement due to its inability to find a solution under the problem specification, i.e. , the agent finds that, given the problem specification and its initial solution requirements, it cannot produce a lo­ cally acceptable proposal. This situation occurs in the application of the initiate-solution operator as described in Section 4.1.

Feedback-based relaxation occurs when an agent re­ laxes a solution requirement because of some explicit information about the requirements of some other agent{s), i.e, a conflict is found between relaxable local solution requirements and less flexible external solution requirements. This occurs when external information has been received by an agent and is being assimilated as described in Section 4.5.

Problem-state relaxation is a reaction to the lack of overall problem-solving progress. In the current TEAM framework, problem-state relaxation occurs at specific processing-cycle intervals: for example, all agents may relax a solution requirement after 10 processing cycles. Alternatively, the user can specify the relaxation param­ eter separately for each agent, so that one agent may relax after 10 processing cycles while another will relax after 20 processing cycles. Problem-state relaxation oc­ curs because the problem may be overconstrained by the full agent set. The ability to formulate, communicate, and assimilate constraining information is not guaran­ teed to be complete and precise across the agent set and the reality is that agents can't always determine whether the composite search space is overconstrained. There­ fore, they must have some heuristic method (as well as the deterministic methods above) for deciding when it is appropriate to relax requirements. 4 Because of problem­ state ~elaxation, we can guarantee that if any initial pro­ posal 18 generated that can result in a feasible solution either that solution will eventually become acceptable t~ all agents, or some other solution will become acceptable to all agents and deadlock will not occur.

4.4 Terminate-Search

The operator terminate-search is applied by TEAM, rather than by an agent, to change the search phase of the algo­ rithm from initial to closed when some (user-specified) number of acceptable proposals been found. 5 As seen in Figure 1, when this change occurs, partial and com­ plete unacceptable solutions move from intermediate to termination states. Any partial acceptable solutions are completed however to ensure that good partial solutions are not abandoned.

4.5 Assimilating Information

There are two operators associated with assimilating in­ formation at an agent: store-received-information and retrieve-information. Store-received-information takes conflict information from other agents, syntactically checks to see if the information already exists in the lo­ cal knowledge base and, if not, stores it so that it can be retrieved. A received requirement may be indexed by various attributes including the name of the sending agent, the flexibility of the requirement, the names and acceptable values of constrained solution attributes and in the case of ordered solution attributes, whether tbe r~ quirement defines a minimum or maximum boundary on potential values, e.g., x > 5.

Retrieve-information is an operator that extends or replaces an agent's default capability to retrieve rele­ vant constraining information from its knowledge base. Because an agent's internal knowledge is expected to be locally consistent, the default retrieval mechanism gen­ erally does not handle cases where conflicts may exist in the retrieved requirements. Requirement retrieval occurs during solution initiation, extension and criti-. ' c1sm. The goal of the retrieval process is to find the most restrictive, but non-conflicting, set of solution re­ quirements that constrain a solution for the current local s~arch problem. Different types of requirements require different treatment, but to provide a concrete example of retrieval, we present the algorithm used for selecting boundary constraints on numerical solution attributes in our application systems. Potentially relevant constraints are retrieved and sorted into maximum and minimum boundary groups. The most restrictive maximum con­ straint {MAX) and the most restrictive minimum con­ straint {MIN) from each group are selected (where most restrictive means the highest value from the MIN group and the lowest value from the MAX group). Then the algorithm loops through the following sequence until a set of minimum and maximum values is found or until it is determined that no non-conflicting set exists.

4 Using the number of processing cycles as a heuristic is a simplistic approach. More sophisticated mechanisms for applying problem-state relaxation based on characteristics of problem-solving situation, rather than on time are discussed in [Lander, 1993). '

5 This is a simplified version of the TEAM termination policy that integrates agent acceptability and, optionally, a domain­ dependent global evaluation of solutions.

LOOP: If the value of MAX is greater than or equal to the value of MIN, return MAX and MIN since a non­ conflicting set has been found. Otherwise, if the flexibil­ ity of MAX is greater than the flexibility of MIN select the next most restrictive maximum constraint {MAX) and go to LOOP. Otherwise, if the flexibility of MAX is less than the flexibility of MIN, select the next most restrictive minimum constraint (MIN) and go to LOOP. Otherwise, the flexibility of MAX is equal to the flexi­ bility of MIN. Then: if MAX is locally owned, select the next most restrictive minimum constraint {MIN) and go to LOOP. If MAX is not locally owned and MIN is lo­ cally owned, select the next most restrictive maximum constraint {MAX) and go to LOOP. If neither MAX nor MIN is locally owned, select the next most restrictive minimum constraint (MIN) and go to LOOP.

In reusable agent sets, operator diversity is expected­ not every agent will instantiate every operator including the store-received-information and retrieve-information operators. Because of this, when an agent formulates ~d sends conflict information to another agent, there 1s no guarantee that the receiving agent will use that information appropriately. Therefore, although conflict information is shared willingly and cooperatively in ne­ gotiated search, agents do not depend on other agents to react in a fixed way to that information.

4.6 Agent-Level Control of Operator Application

Figure 1 describes domain-independent state precondi­ tions that must be satisfied before an agent can apply one of its operators to a particular solution. However, because there are multiple solution paths, and because some operators are not directly involved in solution gen­ eration {e.g., store-received-information), an agent may have multiple operators ready to execute at any given time. The order in which an agent schedules local opera­ tors is not mandated by either TEAM or by the negotiated­ search algorithm. However, because an agent's percep­ tion of the world changes over time, the order in which particular operators are executed does affect system per­ formance and the effect of local scheduling on the over­ all behavior of the system should be considered. Some general policies for local scheduling are useful in most situations, i.e., agents should assimilate any new infor­ mation received before initiating or critiquing solutions. The degree of sophistication required in local scheduling though is highly dependent on the application and the complexity of required interactions.

5 Conclusions

Negotiated search is a flexible and widely applicable distributed-search algorithm. It specifically addresses issues that arise in multi-agent systems comprised of reusable and heterogeneous agents. The algorithm ac­ knowledg~s the inevitability of conflict among the agents, and exploits that conflict to drive agent interaction and guide local search.

Negotiated search has been implemented in TEAM, a generic framework for the integration of reusable agents, and consequently, in two application systems built on top of TEAM: STEAM (a seven-agent system for the mechani­ cal design of steam condensers); and AGREE (a two-agent system for buy/ sell contract negotiation). Testing and analysis of the algorithm within the context of the appli­ cation systems is described in other work [Lander, 1993; Lander and Lesser, 1992a; Lander and Lesser, 1992b]. Results from experiments conducted with negotiated search show that the algorithm can produce high-quality solutions. They also support the claim that the al­ gorithm is flexible enough to work in reusable-agent systems where the search operators are randomly dis­ tributed across the agent set. We see negotiated search as a default algorithm-one that will provide reason­ able solutions in a reasonable amount of time without problem-specific customization. As a complementary approach to developing this general algorithm, we are developing customized algorithms that require specific agent characteristics or inter-agent relationships to exist. By taking advantage of these characteristics, it is often possible to improve solution quality and/or processing­ time performance. TEAM supports the dynamic selection of a search algorithm, thereby enabling an agent set to switch to a customized algorithm if the requirements for application of the algorithm are met. This work is de­ scribed in [Lander, 1993].

Acknowledgements

We thank Margaret Connell and Kevin Gallagher for their support in this project. GBB, a system integration tool from Blackboard Technology Group, was used as the basic platform on which our framework was built.