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.^{[ citation needed ]}

Definitions

DCOP

The main ingredients of a DCOP problem are agents and variables. Importantly, each variable is owned by an agent; this is what makes the problem distributed. Formally, a DCOP is a tuple ${\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }$, where:

• ${\displaystyle A}$ is the set of agents, ${\displaystyle \{a_{1},\dots ,a_{|A|}\}}$.
• ${\displaystyle V}$ is the set of variables, ${\displaystyle \{v_{1},v_{2},\dots ,v_{|V|}\}}$.
• ${\displaystyle {\mathfrak {D}}}$ is the set of variable-domains, ${\displaystyle \{D_{1},D_{2},\dots ,D_{|V|}\}}$, where each ${\displaystyle D_{j}\in {\mathfrak {D}}}$ is a finite set containing the possible values of variable ${\displaystyle v_{j}}$.
  • If ${\displaystyle D_{j}\in {\mathfrak {D}}}$ contains only two values (e.g. 0 or 1), then ${\displaystyle v_{j}}$ is called a binary variable.
• ${\displaystyle f}$ is the cost function. It is a function ^[1]
  $${\displaystyle f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R} }$$
  that maps every possible partial assignment to a cost. Usually, only few values of ${\displaystyle 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 ${\displaystyle C}$ in this set is a function ${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$ assigning 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., ${\displaystyle f_{C}:D_{j}\to \mathbb {R} }$ for some ${\displaystyle v_{j}\in V}$.
  • Binary constraints - constraints on two variables, i.e, ${\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }$ for some ${\displaystyle v_{j_{1}},v_{j_{2}}\in V}$.
• ${\displaystyle \alpha }$ is the ownership function. It is a function ${\displaystyle \alpha :V\to A}$ mapping each variable to its associated agent. ${\displaystyle \alpha (v_{j})\mapsto a_{i}}$ means that variable ${\displaystyle v_{j}}$ "belongs" to agent ${\displaystyle a_{i}}$. This implies that it is agent ${\displaystyle a_{i}}$'s responsibility to assign the value of variable ${\displaystyle v_{j}}$. Note that ${\displaystyle \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.
• ${\displaystyle \eta }$ is the objective function. It is an operator that aggregates all of the individual ${\displaystyle f}$ costs for all possible variable assignments. This is usually accomplished through summation:
  $${\displaystyle \eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq 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 ${\displaystyle \eta (f)}$ for a given assignment of the variables.

Assignments

A value assignment is a pair ${\displaystyle (v_{j},d_{j})}$ where ${\displaystyle d_{j}}$ is an element of the domain ${\displaystyle D_{j}}$.

A partial assignment is a set of value-assignments where each ${\displaystyle v_{j}}$ 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:

$${\displaystyle t:V\to (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, ${\displaystyle t(v_{i})\mapsto \emptyset }$ implies that the agent ${\displaystyle \alpha (v_{i})}$ has not yet assigned a value to variable ${\displaystyle v_{i}}$. 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 ${\displaystyle t}$ function) as an input to the ${\displaystyle f}$ function.

A full assignment is an assignment in which each ${\displaystyle v_{j}}$ 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 ${\displaystyle \eta (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

The graph coloring problem is as follows: given a graph ${\displaystyle G=\langle N,E\rangle }$ and a set of colors ${\displaystyle C}$, assign each vertex, ${\displaystyle n\subset N}$, a color, ${\displaystyle 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 ${\displaystyle |C|}$ (there is one domain value for each possible color). For each vertex ${\displaystyle n_{i}\leq N}$, there is a variable ${\displaystyle v_{i}\in V}$ with domain ${\displaystyle D_{i}=C}$. For each pair of adjacent vertices ${\displaystyle \langle n_{i},n_{j}\rangle \in E}$, there is a constraint of cost 1 if both of the associated variables are assigned the same color:

$${\displaystyle (\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}$$

The objective, then, is to minimize ${\displaystyle \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 ${\displaystyle I}$ be the set of items, ${\displaystyle K}$ be the set of knapsacks, ${\displaystyle s:I\to \mathbb {N} }$ be a function mapping items to their volume, and ${\displaystyle c:K\to \mathbb {N} }$ be a function mapping knapsacks to their capacities.

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

$${\displaystyle 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 ${\displaystyle r(t,k)}$ represents the total weight assigned by context ${\displaystyle t}$ to knapsack ${\displaystyle k}$:

$${\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}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]

• Add a binary variable v_ij for each agent i and item j. The variable value is "1" if the agent gets the item, and "0" otherwise. The variable is owned by agent i.
• To express the constraint that each item is given to at most one agent, add binary constraints for each two different variables related to the same item, with an infinite cost if the two variables are simultaneously "1", and a zero cost otherwise.
• To express the constraint that all items must be allocated, add an n-ary constraint for each item (where n is the number of agents), with an infinite cost if no variable related to this item is "1".

Other applications

DCOP was applied to other problems, such as:

• coordinating mobile sensors;
• meeting and task scheduling.

Algorithms

DCOP algorithms can be classified in several ways: ^[3]

• Completeness - complete search algorithms finding the optimal solution, vs. local search algorithms finding a local optimum.
• Search strategy - best-first search or depth-first branch-and-bound search;
• Synchronization among agents - synchronous or asynchronous;
• Communication among agents - point-to-point with neighbors in the constraint graph, or broadcast;
• 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
ABT[ citation needed ] Asynchronous Backtracking	1992	[ citation needed ]	[ citation needed ]	Note: static ordering, complete	[ citation needed ]
AWC[ citation needed ] Asynchronous Weak-Commitment	1994	[ citation needed ]	[ citation needed ]	Note: reordering, fast, complete (only with exponential space)	[ citation needed ]
DBA Distributed Breakout Algorithm	1995	[ citation needed ]	[ citation needed ]	Note: incomplete but fast	FRODO version 1 [ permanent dead link ]
SyncBB [4] Synchronous Branch and Bound	1997	[ citation needed ]	[ citation needed ]	Complete but slow
IDB Iterative Distributed Breakout	1997	[ citation needed ]	[ citation needed ]	Note: incomplete but fast
AAS[ citation needed ] Asynchronous Aggregation Search	2000	[ citation needed ]	[ citation needed ]	aggregation of values in ABT	[ citation needed ]
DFC[ citation needed ] Distributed Forward Chaining	2000	[ citation needed ]	[ citation needed ]	Note: low, comparable to ABT	[ citation needed ]
ABTR[ citation needed ] Asynchronous Backtracking with Reordering	2001	[ citation needed ]	[ citation needed ]	Note: reordering in ABT with bounded nogoods	[ citation needed ]
DMAC[ citation needed ] Maintaining Asynchronously Consistencies	2001	[ citation needed ]	[ citation needed ]	Note: the fastest algorithm	[ citation needed ]
Secure Computation with Semi-Trusted Servers[ citation needed ]	2002	[ citation needed ]	[ citation needed ]	Note: security increases with the number of trustworthy servers	[ citation needed ]
Secure Multiparty Computation For Solving DisCSPs (MPC-DisCSP1-MPC-DisCSP4)[ citation needed ]	2003	[ citation needed ]	[ citation needed ]	Note: secure if 1/2 of the participants are trustworthy	[ citation needed ]
Adopt Asynchronous Backtracking [5]	2003	Polynomial (or any-space [6] )	Exponential	Proven	Reference Implementation: Adopt Archived 2006-09-16 at the Wayback Machine DCOPolis (GNU LGPL) FRODO (AGPL)
OptAPO Asynchronous Partial Overlay [7]	2004	Polynomial	Exponential	Proven, but proof of completeness has been challenged [8]	Reference Implementation: "OptAPO". Artificial Intelligence Center . SRI International. Archived from the original on 2007-07-15. DCOPolis (GNU LGPL); In Development
DPOP Distributed Pseudotree Optimization Procedure [9]	2005	Exponential	Linear	Proven	Reference Implementation: FRODO (AGPL) DCOPolis (GNU LGPL)
NCBB No-Commitment Branch and Bound [10]	2006	Polynomial (or any-space [11] )	Exponential	Proven	Reference Implementation: not publicly released DCOPolis (GNU LGPL)
CFL Communication-Free Learning [12]	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, ^[3] 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: ^[13]

• Event scheduling : agents who attend the same event might derive different values from it.
• Smart grid : the increase in price of electricity in loaded hours may be different agents.

One way to represent an ADCOP is to represent the constraints as functions:

$${\displaystyle f_{C}:D_{1}\times \dots \times D_{k}\to \mathbb {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 ${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}$ with a constraint ${\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$, which equals the sum of the functions ${\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}$. However, this solution requires the agents to reveal their cost functions. Often, this is not desired due to privacy considerations. ^{[14] [15] [16]}

Another approach is called Private Events as Variables (PEAV). ^[17] 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. ^[13]

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: ^[13]

• In a simultaneous game, the agents are selfish - each of them wants to maximize his/her own utility (or minimize his/her own cost). Therefore, the best outcome that can be sought for in such setting is an equilibrium - a situation in which no agent can unilaterally increase his/her own gain.
• In an ADCOP, the agents are considered cooperative: they act according to the protocol even if it decreases their own utility. Therefore, the goal is more challenging: we would like to maximize the sum of utilities (or minimize the sum of costs). A Nash equilibrium roughly corresponds to a local optimum of this problem, while we are looking for a global optimum.

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: ^[18]

• Guaranteed personal benefit: the agents agree to act for the global good if their own utility is at least as high as in the non-cooperative setting (i.e., the final outcome must be a Pareto improvement of the original state).
• Lambda-cooperation: there is a parameter ${\displaystyle \lambda \in [0,1]}$. The agents agree to act for the global good if their own utility is at least as high as ${\displaystyle (1-\lambda )}$ times their non-cooperative utility.

Solving such partial-coopreation ADCOPs requires adaptations of ADCOP algorithms. ^[18]

See also

• Constraint satisfaction problem
• Distributed algorithm
• Distributed algorithmic mechanism design

Notes and references

1. "${\displaystyle \times }$" 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. doi:10.1007/s10458-015-9291-7. ISSN   1387-2532. S2CID   13834856.
3. Yeoh, William; Felner, Ariel; Koenig, Sven (2008), "BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm", Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 591–8, ISBN   9780981738116
4. Hirayama, Katsutoshi; Yokoo, Makoto (1997). Smolka, Gert (ed.). Distributed partial constraint satisfaction problem. Lecture Notes in Computer Science. Vol. 1330. Berlin, Heidelberg: Springer. pp. 222–236. doi:10.1007/BFb0017442. ISBN   978-3-540-69642-1.{{cite book}}: |journal= ignored (help)
5. The originally published version of Adopt was uninformed, see Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), "An asynchronous complete method for distributed constraint optimization" (PDF), Proceedings of the second international joint conference on autonomous agents and multiagent systems, ACM Press, pp. 161–168, archived from the original (PDF) on 2019-11-04, retrieved 2009-09-07. 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 Ali, Syed; Koenig, Sven; Tambe, Milind (2005), "Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT" (PDF), Proceedings of the fourth international joint conference on autonomous agents and multiagent systems, ACM Press, pp. 1041–8, doi:10.1145/1082473.1082631, ISBN   1595930930, S2CID   10882572, archived from the original (PDF) on 2010-07-07, retrieved 2009-09-07. This extension of Adopt is typically used as reference implementation of Adopt.
6. Matsui, Toshihiro; Matsuo, Hiroshi; Iwata, Akira (February 2005), "Efficient Method for Asynchronous Distributed Constraint Optimization Algorithm" (PDF), Proceedings of Artificial Intelligence and Applications, pp. 727–732, CiteSeerX   10.1.1.408.7230
7. Mailler, Roger; Lesser, Victor (2004), "Solving Distributed Constraint Optimization Problems Using Cooperative Mediation" (PDF), Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, IEEE Computer Society, pp. 438–445, ISBN   1581138644 ^{[ permanent dead link ]}
8. Grinshpoun, Tal; Zazon, Moshe; Binshtok, Maxim; Meisels, Amnon (2007), "Termination Problem of the APO Algorithm" (PDF), Proceedings of the Eighth International Workshop on Distributed Constraint Reasoning, pp. 117–124
9. Petcu, Adrian; Faltings, Boi (August 2005), "DPOP: A Scalable Method for Multiagent Constraint Optimization", Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI 2005, Edinburgh, Scotland, pp. 266-271
10. Chechetka, Anton; Sycara, Katia (May 2006), "No-Commitment Branch and Bound Search for Distributed Constraint Optimization" (PDF), Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1427–9, doi:10.1145/1160633.1160900, ISBN   1595933034, S2CID   43918609
11. Chechetka, Anton; Sycara, Katia (March 2006), "An Any-space Algorithm for Distributed Constraint Optimization" (PDF), Proceedings of the AAAI Spring Symposium on Distributed Plan and Schedule Management
12. Duffy, K.R.; Leith, D.J. (August 2013), "Decentralized Constraint Satisfaction", IEEE/ACM Transactions on Networking, 21 (4): 1298–1308, arXiv: 1103.3240 , doi:10.1109/TNET.2012.2222923, S2CID   11504393
13. Grinshpoun, T.; Grubshtein, A.; Zivan, R.; Netzer, A.; Meisels, A. (2013-07-30). "Asymmetric Distributed Constraint Optimization Problems". Journal of Artificial Intelligence Research. 47: 613–647. arXiv: 1402.0587 . doi: 10.1613/jair.3945 . ISSN   1076-9757.
14. 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. ISBN   978-1-57735-281-5.
15. 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. 13 (1): 27–60. doi:10.1007/s10458-006-5951-y. ISSN   1573-7454. S2CID   16962945.
16. Yokoo, Makoto; Suzuki, Koutarou; Hirayama, Katsutoshi (2002). Van Hentenryck, Pascal (ed.). Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information. Lecture Notes in Computer Science. Vol. 2470. Berlin, Heidelberg: Springer. pp. 387–401. doi:10.1007/3-540-46135-3_26. ISBN   978-3-540-46135-7.{{cite book}}: |journal= ignored (help)
17. 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". www.computer.org. Retrieved 2021-04-12.
18. 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. Valencia, Spain: International Foundation for Autonomous Agents and Multiagent Systems. 3: 1267–1268. ISBN   978-0-9817381-3-0.

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 Multi-Agent Systems, 3 (2): 185–207, doi:10.1023/A:1010078712316, S2CID   2139298