Distributed constraint optimization

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

A DCOP can be defined as a tuple $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$, where:

• $A$ is the set of agents, $\{a_{1},\cdots ,a_{|A|}\}$.
• $V$ is the set of variables, $\{v_{1},v_{2},\cdots ,v_{|V|}\}$.
• ${\mathfrak {D}}$ is the set of variable-domains, $\{D_{1},D_{2},\ldots ,D_{|V|}\}$, where each $D_{j}\in {\mathfrak {D}}$ is a finite set containing the possible values of variable $v_{j}$.
• $f$ is the cost function. It is a function$f:\bigcup _{S\in {\text{PowerSet}}(V)}\times _{v_{j}\in S}D_{j}\rightarrow \mathbb {R} \cup \{\infty \}$ 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 $C:D_{1}\times \cdots \times D_{k}\rightarrow \mathbb {R} \cup \{\infty \}$ mapping a real value to each possible assignment of the variables. Some special kinds of constraints are:
  • Unary constraints - constraints on a single variable, i.e., $C:D_{j}\rightarrow \mathbb {R} \cup \{\infty \}$ for some $v_{j}\in V$.
  • Binary constraints - constraints on two variables, i.e, $C:D_{j_{1}}\times D_{j_{2}}\rightarrow \mathbb {R} \cup \{\infty \}$ for some $v_{j}\in V$.
• $\alpha$ is the ownership function. It is a function $\alpha :V\rightarrow A$ mapping each variable to its associated agent. $\alpha (v_{j})\mapsto a_{i}$ means that variable $v_{j}$ "belongs" to agent $a_{i}$. This implies that it is agent $a_{i}$'s responsibility to assign the value of variable $v_{j}$. 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.
• $\eta$ 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 _{s\in \bigcup _{S\in {\text{PowerSet}}(V)}\times _{v_{j}\in S}D_{j}}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 $\eta (f)$ for a given assignment of the variables.

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:

$t:V\rightarrow (D\in {\mathfrak {D}})\cup \{\emptyset \}.$

Note that a context is essentially a partial solution and need not contain values for every variable in the problem; therefore, $t(v_{i})\mapsto \emptyset$ implies that the agent $\alpha (v_{i})$ has not yet assigned a value to variable $v_{i}$. Given this representation, the "domain" (i.e., 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.

Example problems

Distributed graph coloring

The graph coloring problem is as follows: given a graph $G=\langle N,E\rangle$ and a set of colors $C$, assign each vertex, $n\subset N$, a color, $c\leq C$, 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 $|C|$ (there is one domain value for each possible color). For each vertex $n_{i}\leq N$, create a variable in the DCOP $v_{i}\in V$ with domain $D_{i}=C$. For each pair of adjacent vertices $\langle n_{i},n_{j}\rangle \in E$, create 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 $\eta (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\rightarrow \mathbb {N}$ be a function mapping items to their volume, and $c:K\rightarrow \mathbb {N}$ be a function mapping knapsacks to their capacities.

To encode this problem as a DCOP, for each $i\in I$ create one variable $v_{i}\in V$ with associated domain $D_{i}=K$. Then for all possible contexts $t$:

$f(t)\mapsto \sum _{k\in K}{\begin{cases}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{otherwise}},\end{cases}}$

where $r(t,k)$ is a function such that

$r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).$

Algorithms

DCOP algorithms can be classified according to the search strategy (best-first search or depth-first branch-and-bound search), the synchronization among agents (synchronous or asynchronous), the communication among agents (point-to-point with neighbors in the constraint graph or broadcast) and the main communication topology (chain or tree). 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 (computer science)/ Completeness (logic)	Implementations
NCBB No-Commitment Branch and Bound	2006	Polynomial (or any-space)	Exponential	Proven	Reference Implementation: not publicly released DCOPolis (GNU LGPL)
DPOP Distributed Pseudotree Optimization Procedure	2005	Exponential	Linear	Proven	Reference Implementation: FRODO (GNU Affero GPL) DCOPolis (GNU LGPL)
OptAPO Asynchronous Partial Overlay	2004	Polynomial	Exponential	Proven, but proof of completeness has been challenged	Reference Implementation: "OptAPO". Artificial Intelligence Center. SRI International. Archived from the original on 2007-07-15. DCOPolis (GNU LGPL); In Development
Adopt Asynchronous Backtracking	2003	Polynomial (or any-space)	Exponential	Proven	Reference Implementation: Adopt DCOPolis (GNU LGPL) FRODO (GNU Affero GPL)
Secure Multiparty Computation For Solving DisCSPs (MPC-DisCSP1-MPC-DisCSP4)	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	FRODO version 1
AWC Asynchronous Weak-Commitment	1994			Note: reordering, fast, complete (only with exponential space)
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.

See also

• Constraint satisfaction problem

Books and surveys

• Fioretto, Ferdinando; Pontelli, Enrico; Yeoh, William (2018), "Distributed Constraint Optimization Problems and Applications: A Survey", Journal of Artificial Intelligence Research, 61: 623–698, arXiv:1602.06347, doi:10.1613/jair.5565, S2CID 4503761
• Faltings, Boi (2006), "Distributed Constraint Programming", in Walsh, Toby (ed.), Handbook of Constraint Programming, Elsevier, ISBN 978-0-444-52726-4 A chapter in an edited book.
• Meisels, Amnon (2008), Distributed Search by Constrained Agents, Springer, ISBN 978-1-84800-040-7
• Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7 See Chapters 1 and 2; downloadable free online.
• Yokoo, Makoto (2001), Distributed constraint satisfaction: Foundations of cooperation in multi-agent systems, Springer, ISBN 978-3-540-67596-9
• Yokoo, M. Hirayama K. (2000), "Algorithms for distributed constraint satisfaction: A review", Autonomous Agents and Multiagent Systems, 3 (2): 185–207, doi:10.1023/A:1010078712316, S2CID 2139298