IJCAI-2001 Tutorial on Distributed Knowledge-based Search
Description:
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:
- Introduction: Why Distributed Knowledge-based Search?
use of several processing units, adequately representing different,
vague, even contradictory knowledge, potential gains by synergy.
- Search: Basic Definitions and General Problems
- Basic Definitions
static description: search model, search process;
analysis of search runs: search instance, search derivation
- General Problems
what knowledge to use, what search model, what search control, how
to analyze search runs, how to measure efficiency
- Distributed Search: Cooperating Search Agents
- 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
- 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.
- Basic Idea 1: Working on a Common Search State
- General Idea
all search agents contribute to a search state common to all agents,
state might be stored centrally or distributed among the agents
- General Problems
concurrent access, global vs. local view of problem instance,
determining next transition from common state
- 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
- Example for a Homogeneous Concept: Distributed Branch-and-Bound
simultaneously working on the leafs of an AND-tree
- 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
- Basic Idea 2: Dividing the Problem into Subproblems
- 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
- 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
- Possible Variations
static vs. dynamic division of the problems, negotiating also to
assign subproblems, different negotiation concepts
- Example for a Homogeneous Concept: Distributed Constraint Satisfaction
agents using OR-tree-based search, dividing variables among agents,
concrete negotiation concept: asynchronous weak commitment
- 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
- Basic Idea 3: Improving on the Competition Approach
- 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
- General Problems
avoiding too much redundancy between agents, selecting good and
helpful results for other agents
- Possible Variations
result selection: success-oriented vs demand-oriented, change of
agents during search or not, central control or not
- 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
- 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
- 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
- Open Questions / Future Work
Last Change: 16/02/2001