, where xi←di xj←dj,in A. Distributed constraint optimization problems (DisCOP) represents a generic framework for the resolution of distributed problems in multiagent systems (MAS), especially in problems where the challenge is to find the best value attribution for a set of variables that have interdependencies. [1][2][3][4]. DisCOP is a powerfull tool for modeling a wide variety of multiagent coordination problems such as distributed planning, distributed scheduling, distributed resource allocation and others.
Definition 1.-The DisCOP model.
A Distributed Constraint Optimization Problem (DisCOP) is defined by a 6-tuple (X, D, Ag, φ, fi,j, F), where X={x1, x2,…,xn} is a set of n variables with domains D={D1, D2,...,Dn}, Ag = { Ag1, Ag2,...,Agp } is a set of p agents, φ: X → Ag is a function that maps each variable to its agent, fi,j is a set of cost functions fi,j : Di x Dj → R, to the pair of variables xi and xj (soft constraints), F is an objective function F, defined as an aggregation over the set of cost functions. Such a function assigns a utility to each possible combination of values of the variables in the scope of the function. Hard constraints (which forbid certain value combinations) are a special case of utility functions, which assign 0 to feasible tuples, and −∞ to infeasible ones;
The objective is to find the set of values A* for the variables X,, minimizing or maximizing the objective function.
The function F is defined as F(A) = , where xi←di xj←dj,in A.
The cost functions in DisCOP are the analogue of constraints from DisCSP and are sometimes referred to as “valued” or “soft” constraints. In this article we will consider that each agent Ai has allocated a single variable xi, thus p=n. Also, it assume the following communication model from DisCSP:
Definition 2.-The constraint graph.
The constraint graph is defined as the graph which is obtained by connecting all the variables which share a utility function (the constraint graph is a graph which has a node for each variable Xi ∈ X and a edge for each relation fi,j of the pair of variables xi and xj).
The concept of distributed CSP or COP has been introduced to formalize and solve naturally distributed decision problems which generally deal with a set of data, shared out among many sites and whose centralization is often impossible.
For DisCOP there are many algorithms between which we name ADOP (Asynchronous Distributed OPTimization) [1], DPOP (Dynamic Programming Optimization Protocol) [2] or AFB (Asynchronous Forward Bounding) [3]. DisCOP search algorithms use search strategies to search through the solution space to find a cost-minimal solution. Thus, the asynchronous searching techniques for solving the the DisCSP/DisCOP have many different applications.
ADOPT by Modi et al. ( [1]) is a backtracking based bound propagation mechanism. ADOPT was the first decentralized algorithm to guarantee optimality, while at the same time allowing the agents to operate asynchronously.
The algorithm form [1] works as follows: first, the DFS structure is created. Then, backtrack search is
performed top-down, using the following value ordering heuristic: at each point in time, each agent
chooses the value with the smallest lower bound. It announces its descendants of its choice via VALUE
messages, and waits for COST messages to come back from the children.
Each agent adds the costs received from its
children to the lower bound of the current value taken by the agent. If there is another value in the
domain that has a smaller lower bound, the agent switches its value, and the process repeats, refining
the lower bounds iteratively.
The ADOPT algorithm uses 3 types of messages:
• the THRESHOLD messages
• the VALUE messages (similar to the ok ? messages)
• the COST messages.
The algorithm begins by all agents choosing their variable values concurrently. Variable values are sent down constraint edges via VALUE messages – an agent xi sends VALUEmessages only to neighbors lower in the DFS tree and receives VALUE messages only from neighbors higher in the DFS tree. A second type of message, a THRESHOLD message, is sent only from parent to child. A THRESHOLD message contains a single number representing a backtrack threshold, initially zero. Upon receipt of any type of message, an agent i) calculates cost and possibly changes variable value and/ormodifies its backtrack threshold, ii) sends VALUE messages to its lower neighbors and THRESHOLD messages to its children and iii) sends a third type of message, a COST message, to its parent. A COST message is sent only from child to parent. A COST message sent from xi to its parent contains the cost calculated at xi plus any costs reported to xi from its children.
To summarize the communication [1], variable value assignments (VALUE messages) are sent down the DFS tree while cost feedback (COST messages) percolate back up the DFS tree. It may be useful to view COST messages as a generalization of NOGOOD message from DisCSP algorithms. THRESHOLD messages are sent down the tree to reduce redundant search.
DPOP by Petcu and Faltings ( [2]) is an algorithm based on dynamic programming which performs bucket elimination on a DFS tree in a distributed fashion. DPOP’s main advantage is that it requires only a linear number of messages, thus introducing exponentially less network overhead than search algorithms when applied in a distributed setting.
DPOP is a utility propagation
mechanism, and works on arbitrary constraint problems. It
is a complete algorithm, i.e. it guarantees that the optimal
solution is found.
DPOP performs three phases in sequence:
(1) DFS phase. An
agent is selected as root (for instance, by a leader election process).
From this agent, a distributed DFS traversal of the constraint graph
is started. At the end, each agent labels its neighbors as parents,
pseudoparents, children or pseudochildren.
(2) UTIL phase. Each agent (starting from leaves) sends a UTIL message to its parent, that contain an aggregated cost function computed adding received UTIL messages from its children with its own cost functions with parent and pseudoparents. The sent cost function does not contain the agent’s variable, which is projected out.
(3) VALUE phase.
Each agent determines its optimal value using the cost function
computed in phase 2 and the VALUE message received from its
parent. Then, it informs its children using VALUE messages. The
agent at the root starts this phase.
[1]. Modi, P., Shen, W.-M., Tambe, M., Yokoo, M. Asynchronous Distributed Constraint Optimization with quality guarantees, A.I., 2005, 161 (1-2), 149-–180.
[2]. A. Petcu. A Class of Algorithms for Distributed Constraint Optimization. PhD. Thesis No. 3942, Swiss Federal Institute of Technology (EPFL), Lausanne (Switzerland), 2007.
[3]. A. Meisels. Distributed Search by Constrained Agents: algorithms, performance, communication, Springer Verlag, London, 2008.
[4]. J. Vidal. Fundamentals of Multiagent Systems with NetLogo Examples. Available: http://multiagent.com/p/fundamentals-of-multiagent-systems.html.