Distributed constraint optimization
Distributed constraint optimization is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost
of a set of constraints over the variables is minimized.
Distributed Constraint Satisfaction is a framework for describing a problem in terms of constraints that are known and enforced by distinct participants. The constraints are described on some variables with predefined domains, and have to be assigned to the same values by the different agents.
Problems defined with this framework can be solved by any of the algorithms that are designed for it.
The framework was used under different names in the 1980s. The first known usage with the current name is in 1990.
Definitions
DCOP
A DCOP can be defined as a tuple, where:- is a set of agents;
- is a set of variables, ;
- is a set of domains,, where each is a finite set containing the values to which its associated variable may be assigned;
- is a function
that maps every possible variable assignment to a cost. This function can also be thought of as defining constraints between variables however the variables must not be Hermitian; - is a function mapping variables to their associated agent. implies that it is agent 's responsibility to assign the value of variable. Note that it is not necessarily true that is either an injection or surjection; and
- is an operator that aggregates all of the individual costs for all possible variable assignments. This is usually accomplished through summation:
.
Context
A context is a variable assignment for a DCOP. This can be thought of as a function mapping variables in the DCOP to their current values:f can be thought of as the set of all possible contexts for the DCOP. Therefore, in the remainder of this article we may use the notion of a context as an input to the function.Example problems
Distributed graph coloring
The graph coloring problem is as follows: given a graph and a set of colors, assign each vertex,, a color,, such that the number of adjacent vertices with the same color is minimized.As a DCOP, there is one agent per vertex that is assigned to decide the associated color. Each agent has a single variable whose associated domain is of cardinality . For each vertex, create a variable in the DCOP with domain. For each pair of adjacent vertices, create a constraint of cost 1 if both of the associated variables are assigned the same color:
Distributed multiple knapsack problem
The distributed multiple- variant of the knapsack problem is as follows: given a set of items of varying volume and a set of knapsacks of varying capacity, assign each item to a knapsack such that the amount of overflow is minimized. Let be the set of items, be the set of knapsacks, be a function mapping items to their volume, and be a function mapping knapsacks to their capacities.To encode this problem as a DCOP, for each create one variable with associated domain. Then for all possible contexts :
Algorithms
DCOP algorithms can be classified according to the search strategy, the synchronization among agents, the communication among agents and the main communication topology.ADOPT, for example, uses best-first search, asynchronous synchronization, point-to-point communication between neighboring agents in the constraint graph and a constraint tree as main communication topology.
| Algorithm Name | Year Introduced | Memory Complexity | Number of Messages | Correctness / Completeness | Implementations |
| NCBB No-Commitment Branch and Bound | 2006 | Polynomial | Exponential | Proven | Reference Implementation: not publicly released |
| DPOP Distributed Pseudotree Optimization Procedure | 2005 | Exponential | Linear | Proven | Reference Implementation: |
| OptAPO Asynchronous Partial Overlay | 2004 | Polynomial | Exponential | Proven, but proof of completeness has been challenged | Reference Implementation: ; In Development |
| Adopt Asynchronous Backtracking | 2003 | Polynomial | Exponential | Proven | Reference Implementation: |
| Secure Multiparty Computation For Solving DisCSPs | 2003 | Note: secure if 1/2 of the participants are trustworthy | |||
| Secure Computation with Semi-Trusted Servers | 2002 | Note: security increases with the number of trustworthy servers | |||
| ABTR Asynchronous Backtracking with Reordering | 2001 | Note: eordering in ABT with bounded nogoods | |||
| DMAC Maintaining Asynchronously Consistencies | 2001 | Note: the fastest algorithm | |||
| AAS Asynchronous Aggregation Search | 2000 | aggregation of values in ABT | |||
| DFC Distributed Forward Chaining | 2000 | Note: low, comparable to ABT | |||
| DBA Distributed Breakout Algorithm | 1995 | Note: incomplete but fast | |||
| AWC Asynchronous Weak-Commitment | 1994 | Note: reordering, fast, complete | |||
| ABT Asynchronous Backtracking | 1992 | Note: static ordering, complete | |||
| CFL Communication-Free Learning | 2013 | Linear | None Note: no messages are sent, but assumes knowledge about satisfaction of local constraint | Incomplete |
Hybrids of these DCOP algorithms also exist. BnB-Adopt, for example, changes the search strategy of Adopt from best-first search to depth-first branch-and-bound search.
Books and surveys
- A chapter in an edited book.
- See Chapters 1 and 2; .
- Yokoo, M., and Hirayama, K.. Algorithms for distributed constraint satisfaction: A review. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. A survey.