Understanding the Role of Negotiation in Distributed Search Among Heterogereous Agents

TL;DR

This paper introduces "negotiated search," a novel distributed search algorithm that explicitly uses conflict among heterogeneous agents as a driving force for problem-solving. It enables reusable agents to cooperate effectively by providing a flexible framework for negotiation, conflict resolution, and the incremental refinement of shared solutions.

What Problem Does This Paper Address?

Building complex application systems today often involves integrating various software components. The trend towards "reusable agents" aims to overcome the prohibitive cost of building everything from scratch. However, a significant challenge arises when these reusable agents, developed independently and potentially with different internal architectures and knowledge, need to cooperate. This heterogeneity inevitably leads to conflicts in their requirements and perspectives. Traditional multi-agent systems often struggle to manage this inherent conflict, treating it as something to be avoided or resolved through predefined protocols. This paper addresses the gap by proposing a method where conflict isn't just a problem to be solved, but a valuable source of control information that can actively guide the distributed search process towards a mutually acceptable solution.

Methods

The core contribution is the negotiated search algorithm. This algorithm is designed for loosely coupled, heterogeneous, and reusable agents. It interleaves four key tasks:

  1. Local Search: Each agent independently searches for a solution to a subproblem within its local domain.
  2. Integration: Local subproblem solutions are integrated into a shared, composite solution.
  3. Negotiation: Agents engage in information exchange to define and refine the shared search space, explicitly addressing conflicts.
  4. Assessment: Emerging solutions are continuously assessed and reassessed.

The algorithm is built around a set of negotiated-search operators (e.g., initiate-solution, extend-solution, critique-solution, relax-solution-requirement). These operators allow agents to propose, evaluate, and modify solutions. A key aspect is how agents handle conflicts:

  • Hard conflicts (violating non-relaxable requirements) lead to pruning a solution path.
  • Soft conflicts (violating relaxable requirements) are flagged as potential compromises, which can become acceptable if requirements are relaxed later.

The system uses a state-based view of composite solutions, tracking their acceptability, completeness, and search state. Agents also have mechanisms for assimilating information, specifically conflict information received from other agents, to refine their local understanding of the problem space.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic framework and its conceptualization, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Conflict as a Driver: The most significant insight is reframing conflict not as a failure, but as a crucial mechanism for driving negotiation and directing search in heterogeneous agent systems.
  • Reusability and Heterogeneity: The algorithm is specifically designed to accommodate agents that are unaware of each other's internal workings or specific capabilities, making it ideal for integrating diverse, reusable components.
  • Democratic Decision-Making: Solution acceptance is a joint, democratic process, ensuring that all agents have a voice and that solutions are truly mutually acceptable.
  • Incremental Refinement: The process allows for solutions to evolve through iterative proposals, critiques, and relaxations, rather than requiring a perfect solution upfront.
  • Shared Search Space: The negotiation process aims to build a shared understanding of the search space, even among agents with different local perspectives.

Key Results

The paper describes the successful incorporation of negotiated search into two implemented systems: a seven-agent steam condenser design system and a two-agent contract negotiation system. While specific quantitative results are not detailed in this particular paper (as it focuses on the general framework), the authors claim that the algorithm can produce high-quality solutions and is flexible enough to work in reusable-agent systems where search operators are distributed. They position negotiated search as a strong default algorithm that provides reasonable solutions without requiring problem-specific customization.

Limitations and Future Work

  • Complexity of Assimilation: While agents share conflict information, there's no guarantee that receiving agents will use it appropriately due to heterogeneity. The paper notes that agents don't depend on others reacting in a fixed way.
  • Local Scheduling: The order in which agents schedule their local operators can affect system performance, and while general policies are suggested (e.g., assimilating information first), the optimal local scheduling is application-dependent.
  • Future Work: The authors mention developing customized algorithms that leverage specific agent characteristics or inter-agent relationships to improve performance further. They also allude to more sophisticated mechanisms for problem-state relaxation beyond simple time-based heuristics. The paper also points to other work for details on concurrency handling and more advanced assimilation mechanisms.

Summary updated

BibTeX
@inproceedings{1993understanding,
  title = {{Understanding the Role of Negotiation in Distributed Search Among Heterogereous Agents}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
}
Figure