IJCAI-2005 Slides /AAMAS-2004 Slides / IJCAI-2003 Slides


Tutorial on Distributed Constraint Reasoning

Presenters: Jörg Denzinger, Marius Silaghi, Makoto Yokoo



AAMAS-2004 version follows. We will soon post the topics for the IJCAI-2005 edition which will introduce many novelties, specially secure multiparty computations.

Description

Due to the unprecedented expansion of the Internet, a major change occurs in our life and habits. We can expect that some software agents would work on our behalf, representing our interests and defending our privacy. A principled approach to the achievement of this dream is proposed by the Distributed Constraint Reasoning community which offers a general framework and powerful competitive techniques to approach these important applications. Distributed Constraint Satisfaction is the outcome of intensive research performed in the 80ies and tries to offer equal opportunities to participants in cooperative or semi-cooperative distributed resource allocation problems. The field got a clear contour in the beginning of the 90ies when researchers proved the main theoretical limitations of distributed computations. This was followed by a decade of research that continuously increases its intensity.

This tutorial will provide an unified view on Distributed Constraint Reasoning, introducing distributed constraint reasoning systems as semi-cooperative multi-agent systems and concentrating on the communication and organization requirements of such systems. The general ideas behind the known distributed constraint reasoning systems are presented within this multi-agent framework. For each approach, the requirements, limitations, advantages and disadvantages of the different categories will be discussed.

Prerequisite knowledge:

The tutorial is targeted at the general AI audience, both academic and industrial, working in AI fields that employ search at the core of their systems. It requires only a basic knowledge in standard algorithm schemes, like branch-and-bound or local optimization techniques.

Table of Content:

  1. Introduction: Distributed Search and Distributed Constraint Reasoning
    distribution concepts and their motivation, peculiarities and motivations for distributing or maintaining problems distributed.
  2. Frameworks for Distributed Constraint Reasoning
    frameworks for artificially distributed versus frameworks for naturally distributed problems. Frameworks for privacy requirements.
  3. Distributed Consistency Achievement
    1. Local Consistency
      motivations, degrees of consistency, famous techniques for achieving consistency.
    2. Efficiency of Distributed Consistency
      distributed nature of consistency, sequential nature of the process.
    3. Algorithms for achieving distributed local consistency
      striving for optimality, techniques related to constraint graphs, techniques for distributing constraints, continuous domains.
  4. Incomplete Search for DisCSPs
    1. Why (not) completeness
      impossibility results, FA/C distributions, and natural approaches to resource allocation.
    2. Efficient Algorithms with(without) structure
      structure and synchronisation as slowing factors in distributed processes, how far are we from completeness.
  5. Centralized Search and its Distribution
    1. Centralized backtracking and straightforward operational distributions
      centralized search, look-ahead, reordering, and consistency maintenance, the synchronization as simple way of distributing algorithms.
    2. Improved Distributions
      idle processors and parallelism, improved problem distribution as means of improving the communication.
    3. Unhindered parallelism in distributed search
      real impediments to parallelism, theoretical results for distribution techniques as solution to lack of parallelism.
  6. Asynchronous techniques
    1. Asynchronism
      what is asynchronism and why bother, framework and explaining results, need and drawbacks of ordering.
    2. Analysis of equivalences to centralized backtracking
      phenomenal analysis versus operational analysis, enumeration, phenomenal extensions of other centralized search techniques.
    3. Sources of parallelism in asynchronous solving
      parallelism and commitment, the roots of committment.
  7. Properties and Future
    1. Samples of Applications
      open systems for tracking targets, coordinating emitors, scheduling, auctions.
    2. Privacy and openness
      alternative techniques for maintaining privacy, classification of approaches to open and dynamic systems.

Last Change: 10/01/2003