IJCAI-2001 Tutorial on Distributed Knowledge-based Search

Presenter: Jörg Denzinger


With the increasing availability of multiprocessor computers and networks of computers the wish to use the massive computing power provided by them has become stronger and stronger. With the maturity of the field multi-agent systems, we now have the conceptual and modeling tools to adequately describe and compare different approaches to solve AI problems while employing the additional ``dimension'' of teams of computers. Knowledge-based search is at the core of many AI systems and even a number of systems that have found their way into ``mainstream'' computer science, such as scheduling systems and many standard optimization systems.

This tutorial will provide a unified view on different concepts used to distribute knowledge-based search. We will introduce distributed search systems as cooperative multi-agent systems and concentrate on the communication and organization requirements of such systems. The general ideas behind the known distributed search systems will be presented within this multi-agent framework, and the systems will be classified into different categories.

For each category, we will present its basic idea independent from a particular application. We will present one typical homogeneous and one typical heterogeneous distribution concept for each category. Finally, we will discuss and compare the requirements, limitations, advantages and disadvantages of the different categories.

Prerequisite knowledge:

The tutorial is suitable for a general AI audience, both academic and industrial. Knowledge of some basic search algorithm schemes would be helpful, but it is not essential.

Table of Content:

  1. Introduction: Why Distributed Knowledge-based Search?
    use of several processing units, adequately representing different, vague, even contradictory knowledge, potential gains by synergy.
  2. Search: Basic Definitions and General Problems
    1. Basic Definitions
      static description: search model, search process;
      analysis of search runs: search instance, search derivation
    2. General Problems
      what knowledge to use, what search model, what search control, how to analyze search runs, how to measure efficiency
  3. Distributed Search: Cooperating Search Agents
    1. Basic Definitions
      static description: communication structure, search agent, distributed search system;
      analysis of search runs: time frame, search course protocol;
      some coarse classifications: homogeneous vs heterogeneous distr. search systems, distribution vs parallelization
    2. General Problems
      taking available hardware into account: fitting communication needs to reality, taking available application-specific knowledge into account: preselecting distribution concepts, selecting the team of agents, planing the search: parameters, alternative agents, etc.
  4. Basic Idea 1: Working on a Common Search State
    1. General Idea
      all search agents contribute to a search state common to all agents, state might be stored centrally or distributed among the agents
    2. General Problems
      concurrent access, global vs. local view of problem instance, determining next transition from common state
    3. Possible Variations
      with respect to distributed state: when to send which parts of state to other agents;
      with respect to central state: central or decentralized control, synchronous or asynchronous communication;
      combinations of both ideas
    4. Example for a Homogeneous Concept: Distributed Branch-and-Bound
      simultaneously working on the leafs of an AND-tree
    5. Example for a Heterogeneous Concept: Solving the TSP with A-teams
      agents use data from areas in common state to generate new data in some area
  5. Basic Idea 2: Dividing the Problem into Subproblems
    1. General Idea
      find a set of subproblem instances whose solutions can be put together to form a solution of the given problem instance; assign a well-suited search agent to each subproblem; if subproblems depend on each other: guarantee that subproblem solutions are compatible by introducing negotiation among agents, general goal: enhance local views of other agents with information about an agent's own subproblem until they produce compatible solution
    2. General Problems
      finding an appropriate division of a problem, finding good and less communication-intensive negotiation concepts, detecting key problems that have only a small number of different solutions
    3. Possible Variations
      static vs. dynamic division of the problems, negotiating also to assign subproblems, different negotiation concepts
    4. Example for a Homogeneous Concept: Distributed Constraint Satisfaction
      agents using OR-tree-based search, dividing variables among agents, concrete negotiation concept: asynchronous weak commitment
    5. Example for a Heterogeneous Concept: Cooperative Transportation Scheduling with MARS
      dynamic division of problems, negotiation on two levels: extension of contract-net to assign problems, simulated trading to optimize the solutions
  6. Basic Idea 3: Improving on the Competition Approach
    1. General Idea
      all agents get the full problem instance and compete in solving it, periodically an agent interrupts its search process, selects good results and communicates them to other agents (maybe using specific requests from other agents), among the results it received it selects the ones best suited for it, integrates them into its search and then continues the search
    2. General Problems
      avoiding too much redundancy between agents, selecting good and helpful results for other agents
    3. Possible Variations
      result selection: success-oriented vs demand-oriented, change of agents during search or not, central control or not
    4. Example for a Homogeneous Concept: Distributed Genetic Algorithms by Niche-Search
      agents using set-based search processes, search control is based on several parameters, the distributed search system also searches for a good team by employing a central control that exchanges search agents
    5. Example for a Heterogeneous Concept: Distributed Job-Shop Scheduling with TECHS
      Genetic-Algorithm agents and Branch-and-Bound agents exchange several kinds of information, such as good solutions and control information, that all together achieve synergetic speed-ups
  7. Comparison of the three Basic Ideas
    with respect to: preferred hardware configurations; exchanged information, such as format, amount, frequency, type; usable search models and agents; coupling of agents; system control, limitations on agents
  8. Open Questions / Future Work

Last Change: 16/02/2001