Distributed constraint optimization explained

Distributed constraint optimization (DCOP or DisCOP) 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 (agents). 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

\langleA,V,ak{D},f,\alpha,η\rangle

, where:

A

is the set of agents,

\{a1,...,a|A|\}

.

V

is the set of variables,

\{v1,v2,...,v|V|\}

.

ak{D}

is the set of variable-domains, where each

Dj\inak{D}

is a finite set containing the possible values of variable

vj

.

Dj\inak{D}

contains only two values (e.g. 0 or 1), then

vj

is called a binary variable.

f

is the cost function. It is a function[1] f : \bigcup_ \times_ D_j \to \R that maps every possible partial assignment to a cost. Usually, only few values of

f

are non-zero, and it is represented as a list of the tuples that are assigned a non-zero value. Each such tuple is called a constraint. Each constraint

C

in this set is a function

fC:D1 x … x Dk\to\R

assigning a real value to each possible assignment of the variables. Some special kinds of constraints are:

fC:Dj\to\R

for some

vj\inV

.

fC:

D
j1

x

D
j2

\to\R

for some

\alpha

is the ownership function. It is a function

\alpha:V\toA

mapping each variable to its associated agent.

\alpha(vj)\mapstoai

means that variable

vj

"belongs" to agent

ai

. This implies that it is agent

ai

's responsibility to assign the value of variable

vj

. Note that

\alpha

is not necessarily an injection, i.e., one agent may own more than one variables. It is also not necessarily a surjection, i.e., some agents may own no variables.

η

is the objective function. It is an operator that aggregates all of the individual

f

costs for all possible variable assignments. This is usually accomplished through summation:\eta(f) \mapsto \sum_ f(s).

The objective of a DCOP is to have each agent assign values to its associated variables in order to either minimize or maximize

η(f)

for a given assignment of the variables.

Assignments

A value assignment is a pair

(vj,dj)

where

dj

is an element of the domain

Dj

.

A partial assignment is a set of value-assignments where each

vj

appears at most once. It is also called a context. This can be thought of as a function mapping variables in the DCOP to their current values:t : V \to (D \in \mathfrak) \cup \.Note that a context is essentially a partial solution and need not contain values for every variable in the problem; therefore,

t(vi)\mapsto\emptyset

implies that the agent

\alpha(vi)

has not yet assigned a value to variable

vi

. Given this representation, the "domain" (that is, the set of input values) of the function 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 (i.e., the

t

function) as an input to the

f

function.

A full assignment is an assignment in which each

vj

appears exactly once, that is, all variables are assigned. It is also called a solution to the DCOP.

An optimal solution is a full assignment in which the objective function

η(f)

is optimized (i.e., maximized or minimized, depending on the type of problem).

Example problems

Various problems from different domains can be presented as DCOPs.

Distributed graph coloring

G=\langleN,E\rangle

and a set of colors

C

, assign each vertex,

n\subsetN

, a color,

c\leqC

, such that the number of adjacent vertices with the same color is minimized.

|C|

(there is one domain value for each possible color). For each vertex

ni\leqN

, there is a variable

vi\inV

with domain

Di=C

. For each pair of adjacent vertices

\langleni,nj\rangle\inE

, there is a constraint of cost 1 if both of the associated variables are assigned the same color: (\forall c \subseteq C : f(\langle v_i, c \rangle, \langle v_j, c \rangle) \mapsto 1). The objective, then, is to minimize

η(f)

.

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

I

be the set of items,

K

be the set of knapsacks,

s:I\to\N

be a function mapping items to their volume, and

c:K\to\N

be a function mapping knapsacks to their capacities.

To encode this problem as a DCOP, for each

i\inI

create one variable

vi\inV

with associated domain

Di=K

. Then for all possible contexts

t

:f(t) \mapsto \sum_ \begin 0 & r(t,k) \leq c(k), \\ r(t,k)-c(k) & \text,\endwhere

r(t,k)

represents the total weight assigned by context

t

to knapsack

k

:r(t,k) = \sum_ s(i).

Distributed item allocation problem

The item allocation problem is as follows. There are several items that have to be divided among several agents. Each agent has a different valuation for the items. The goal is to optimize some global goal, such as maximizing the sum of utilities or minimizing the envy. The item allocation problem can be formulated as a DCOP as follows.[2]

Other applications

DCOP was applied to other problems, such as:

Algorithms

DCOP algorithms can be classified in several ways:

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 NameYear IntroducedMemory ComplexityNumber of MessagesCorrectness (computer science)/
Completeness (logic)
Implementations
ABT
Asynchronous Backtracking
1992Note: static ordering, complete
AWC
Asynchronous Weak-Commitment
1994Note: reordering, fast, complete (only with exponential space)
DBA
Distributed Breakout Algorithm
1995Note: incomplete but fastFRODO version 1
SyncBB[3] Synchronous Branch and Bound1997Complete but slow
IDBIterative Distributed Breakout1997Note: incomplete but fast
AAS
Asynchronous Aggregation Search
2000aggregation of values in ABT
DFC
Distributed Forward Chaining
2000Note: low, comparable to ABT
ABTR
Asynchronous Backtracking with Reordering
2001Note: reordering in ABT with bounded nogoods
DMAC
Maintaining Asynchronously Consistencies
2001Note: the fastest algorithm
Secure Computation with Semi-Trusted Servers2002Note: security increases with the number of trustworthy servers
Secure Multiparty Computation For Solving DisCSPs
(MPC-DisCSP1-MPC-DisCSP4)
2003Note: secure if 1/2 of the participants are trustworthy
Adopt
Asynchronous Backtracking[4]
2003Polynomial (or any-space)ExponentialProvenReference Implementation: Adopt
DCOPolis (GNU LGPL)
FRODO (AGPL)
OptAPO
Asynchronous Partial Overlay
2004PolynomialExponentialProven, but proof of completeness has been challengedReference Implementation: Web site: OptAPO. https://web.archive.org/web/20070715063706/http://www.ai.sri.com/~mailler/optapo.html. 2007-07-15. Artificial Intelligence Center. SRI International.
DCOPolis (GNU LGPL); In Development
DPOP
Distributed Pseudotree Optimization Procedure
2005ExponentialLinearProvenReference Implementation: FRODO (AGPL)
DCOPolis (GNU LGPL)
NCBB
No-Commitment Branch and Bound
2006Polynomial (or any-space)ExponentialProvenReference Implementation: not publicly released
DCOPolis (GNU LGPL)
CFL
Communication-Free Learning
2013LinearNone Note: no messages are sent, but assumes knowledge about satisfaction of local constraintIncomplete

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.

Asymmetric DCOP

An asymmetric DCOP is an extension of DCOP in which the cost of each constraint may be different for different agents. Some example applications are:[5]

One way to represent an ADCOP is to represent the constraints as functions: f_C: D_1\times\dots\times D_k \to \R^k

Here, for each constraint there is not a single cost but a vector of costs - one for each agent involved in the constraint. The vector of costs is of length k if each variable belongs to a different agent; if two or more variables belong to the same agent, then the vector of costs is shorter - there is a single cost for each involved agent, not for each variable.

Approaches to solving an ADCOP

A simple way for solving an ADCOP is to replace each constraint

fC:D1 x … x Dk\toRk

with a constraint

fC':D1 x … x Dk\toR

, which equals the sum of the functions
1
f
C

++

k
f
C
. However, this solution requires the agents to reveal their cost functions. Often, this is not desired due to privacy considerations.[6] [7] [8]

Another approach is called Private Events as Variables (PEAV).[9] In this approach, each variable owns, in addition to his own variables, also "mirror variables" of all the variables owned by his neighbors in the constraint network. There are additional constraints (with a cost of infinity) that guarantee that the mirror variables equal the original variables. The disadvantage of this method is that the number of variables and constraints is much larger than the original, which leads to a higher run-time.

A third approach is to adapt existing algorithms, developed for DCOPs, to the ADCOP framework. This has been done for both complete-search algorithms and local-search algorithms.

Comparison with strategic games

The structure of an ADCOP problem is similar to the game-theoretic concept of a simultaneous game. In both cases, there are agents who control variables (in game theory, the variables are the agents' possible actions or strategies). In both cases, each choice of variables by the different agents result in a different payoff to each agent. However, there is a fundamental difference:

Partial cooperation

There are some intermediate models in which the agents are partially-cooperative: they are willing to decrease their utility to help the global goal, but only if their own cost is not too high. An example of partially-cooperative agents are employees in a firm. On one hand, each employee wants to maximize their own utility; on the other hand, they also want to contribute to the success of the firm. Therefore, they are willing to help others or do some other time-consuming tasks that help the firm, as long as it is not too burdensome on them. Some models for partially-cooperative agents are:[10]

λ\in[0,1]

. The agents agree to act for the global good if their own utility is at least as high as

(1-λ)

times their non-cooperative utility.

Solving such partial-coopreation ADCOPs requires adaptations of ADCOP algorithms.

See also

Notes and references

  1. "

    x

    " or "×" denotes the Cartesian product.
  2. Netzer. Arnon. Meisels. Amnon. Zivan. Roie. 2016-03-01. Distributed envy minimization for resource allocation. Autonomous Agents and Multi-Agent Systems . 30. 2. 364–402. 10.1007/s10458-015-9291-7. 13834856. 1387-2532.
  3. Book: Hirayama. Katsutoshi. Yokoo. Makoto. 1997. Smolka. Gert. Distributed partial constraint satisfaction problem. https://link.springer.com/chapter/10.1007/BFb0017442. Principles and Practice of Constraint Programming-CP97. Lecture Notes in Computer Science. 1330. en. Berlin, Heidelberg. Springer. 222–236. 10.1007/BFb0017442. 978-3-540-69642-1.
  4. The originally published version of Adopt was uninformed, see. The original version of Adopt was later extended to be informed, that is, to use estimates of the solution costs to focus its search and run faster, see. This extension of Adopt is typically used as reference implementation of Adopt.
  5. Grinshpoun. T.. Grubshtein. A.. Zivan. R.. Netzer. A.. Meisels. A.. 2013-07-30. Asymmetric Distributed Constraint Optimization Problems. Journal of Artificial Intelligence Research. en. 47. 613–647. 10.1613/jair.3945. 1076-9757. free. 1402.0587.
  6. Greenstadt. Rachel. Pearce. Jonathan P. . Tambe. Milind. 2006-07-16. Analysis of privacy loss in distributed constraint optimization . Proceedings of the 21st National Conference on Artificial Intelligence - Volume 1. AAAI'06. Boston, Massachusetts. AAAI Press . 647–653 . 978-1-57735-281-5.
  7. Maheswaran. Rajiv T.. Pearce. Jonathan P.. Bowring . Emma. Varakantham. Pradeep. Tambe. Milind. 2006-07-01. Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications. Autonomous Agents and Multi-Agent Systems. en. 13. 1. 27–60. 10.1007/s10458-006-5951-y. 16962945. 1573-7454.
  8. Book: Yokoo . Makoto . Suzuki . Koutarou . Hirayama. Katsutoshi. 2002. Van Hentenryck. Pascal. Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information. https://link.springer.com/chapter/10.1007/3-540-46135-3_26 . Principles and Practice of Constraint Programming – CP 2002. Lecture Notes in Computer Science . 2470. en. Berlin, Heidelberg . Springer . 387–401 . 10.1007/3-540-46135-3_26 . 978-3-540-46135-7.
  9. Web site: Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, Pradeep Varakantham. 2004. Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling. 2021-04-12. www.computer.org.
  10. Zivan . Roie. Grubshtein. Alon. Friedman. Michal. Meisels. Amnon. 2012-06-04. Partial cooperation in multi-agent search. Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3. AAMAS '12. 3 . Valencia, Spain . International Foundation for Autonomous Agents and Multiagent Systems. 1267–1268. 978-0-9817381-3-0.

Books and surveys