Distributed Constraint Satisfaction Workshops

Distributed Constraint Satisfaction

The Distributed Constraint Satisfaction is a general formalism for modeling naturally distributed problems [Yokoo&Durfee&Ishida&Kuwabara'98].

Previously, many related publications have appeared in the Series of International Workshops on Distributed Artificial Intelligence.

History
History of Complete Asynchronous Techniques For Natural DisCSPs
History of Other Ideas
History for DisCSP allowing for problem redistribution

DisCSP Formalism

1998 (IEEE TKDE) - Yokoo&Durfee&Ishida&Kuwabara

DisCSP acronym - proposed by Christian Bessiere at CP DCS Workshop, 2000

References

2000 (made available at the CP DCS Workshop) Yokoo (some references on DisCSPs before 2000)

History of Complete Asynchronous Techniques For Naturally Distributed CSPs

Asynchronous Backtracking

1990 (10th DAI Workshop) - Yokoo&Durfee&Ishida&Kuwabara (Basic Asynchronous Backtracking, 1 agent has1 distinct variable, storing all nogoods)
1998 (ICMAS) - Yokoo&Hirayama (Complex Local Problems)
2000 (AAAI) - Silaghi&Haroud&Faltings (Minimal Space&Complete+Allows shared variables+Cartesian Product Representation of proposals)
2001 (IJCAI DCR Workshop&CP) - Bessiere&Maestre&Meseguer (Getting rid of Add Link Messages)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Faltings (Asynchronous Dichotomous Splitting For Numerical CSPs)

Asynchronous Reordering

1991 (IJCAI) - Zeev&Dechter&Katz (Need For Static Total Ordering)
1993 (12th DAI Workshop) - Yokoo (For Nogood-Based Heuristics - Constrained Agents First)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Faltings (For General Heuristics & Polynomial Space Requirements)
2001 (EPFL-TR-364) - Silaghi&Haroud&Faltings (Reordering Heuristics for Asynchronous Distributed Search)

Strategies for Nogood Selection

1997 (AAAI Workshop) - Havens (Strategies for nogood selection and discarding nogoods)
2000 (AA) - Turner (efficiency for classes of nogoods)
2000 (ICDCS) - Hirayama&Yokoo (efficient nogoods)
2000 (Springer) - Yokoo (Space Complexity with Dynamic Backtracking-like nogood storing)

Relaxation

1993 (ICTAI) - Yokoo (for overconstrained problems-based on tuple value)
1997 (CP) - Hirayama&Yokoo (for overconstrained problems-based on number of conflicting constraints)
2000 (ICMAS) - Hirayama&Yokoo (for overconstrained problems-based on number of conflicting constraints and tuple value)
2000 (DCS Workshop CP) - Silaghi&Haroud&Faltings (based on constraint references)

Asynchronous Consistency Achievement

1990 (IJCAI) - Mackworth&Zhang (General Distribution of Constraints)
1997 (UCL-TR) - Deville&.. (AC4-like)
1999 (CP) - Hamadi (Optimal Distribution of Constraints)
2000 (ACM Symp. on Applied Computing) - Monfroy (General Propagation Algorithm for an Abstract Notion of Consistency)

Asynchronous Consistency Maintenance

2000 (CP DCS Workshop) - Silaghi&Haroud&Faltings (Without Strength Guarantees)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Faltings (offers guarantees&allows to use backtrack nogoods in consistency)

Distributed Optimization

2003 (AAMAS) - Modi&Tambe&Shen&Yokoo (asynchronous A* behaviour)
2003 (IAT) - Silaghi (asynchronous PFCMRDAC-like consistency based bound estimation behavior)

Privacy Tradeoffs

2000 (CP DCS Workshop) - Meseguer&Jimenez (tradeoffs against efficiency)
2001 (IJCAI Workshop) - Freuder&Minca&Wallace (privacy measure)

Asynchronous Use Of Hierarchical Abstractions (IJCAI Workshop)

2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Faltings

Applications

2000 (CP DCS Workshop) - Jung&Tambe&Zhang&Shen (negotiation among Helicopters)
2000 (CP DCS Workshop) - Idrissi&Bouyakhf (Airplanes - traffic control)
2000 (CP DCS Workshop) - Eisenberg (task scheduling)
2001 (IJCAI DCR Workshop) - Silaghi&Haroud&Calisti&Faltings (General English Auctions)
2001 (IJCAI DCR Workshop) - Freuder&Minca&Wallace (meeting scheduling)
2001 (IJCAI DCR Workshop) - Modi&Jung&Tambe&Zhang&Shen and Gomes (multi-sensor target tracking)

History of Other Ideas

    1996 (ICMAS) - Yokoo&Hirayama (Local Search)
    1997 (IJCAI) - Armstrong&Durfee (Reordering heuristics with synchronization)
    2000 (CP DCS Workshop) Hirayama&Yokoo (Phase Transition in DisCSPs)
    2000 (CP DCS Workshop) Hannebauer (Proof with Petri Nets for DisCSPs)
    2000 (ICMAS) Willmott&Faltings&Macho&Calisti (XML-CSP)
    2001 (IJCAI DCR Workshop) - Razgon&Meisels (Value/Variable reordering in synchronous search)

History for DisCSP allowing for problem redistribution

Tutorial on distributed approaches to problem solving

2001 (IJCAI) J.Denzinger (more about distributed genetic algorithms)

Efficient Synchronous Search

1990 (IJCAI) Zeev&Dechter&Katz (Exploiting independent subproblems)

Canonic Model For Constraints that can be Redistributed

1995 (CP Workshop) Solotorevski&Meisels

Redistribution for SAT problems

2001 (IJCAI Workshop) Amir&McIllraith

Send comments to Marius-Calin Silaghi