The AFB_BJ+-AC* algorithm is one of the latest algorithms used to solve Distributed Constraint Optimization Problems (DCOPs). It is based on simple arc consistency (AC* ) to speed up the process of solving a problem by permanently removing any value that doesn't belong to its optimal solution. In this paper, we use a directional arc consistency (DAC* ), the next higher level of AC* , to erase more values and thus to quickly reach the optimal solution of a problem. Experiments on some benchmarks show that the new algorithm, AFB_BJ+-DAC* , is better in terms of communication load and computation efort.
A DCOP [
We consider these notations: is an agent, where is its level. ( , ) is an assignment of , where ∈ and ∈ . is a constraint between and . is a constraint on . is a zero-arity constraint that represents a lower bound of any problem solution. is the contribution value of in . is the cost of the optimal solution reached so far. [1, 2, . . . , ] is the lexicographic ordering of agents (the default ordering), Γ( ) = {Γ− : ∈ | ∈ , < } ∪ {Γ+ : ∈ | ∈ , > } is the set of neighbors
Proc. 1: ProjectUnary() 1 ← ∈ {()} ; 2 ← + ; 3 foreach ( ∈ ) do 4 () ← () − ; Proc. 2: Extend(, , ) 1 foreach ( ∈ ) do 2 foreach ( ∈ ) do 3 (, ) ← (, ) + [] ; 4 if ( is the current agent) 5 () ← () − [] ; Proc. 3: DAC* () 1 foreach ( ∈ ) do 2 if (() + ≥ ) 3 ← − ; [].() ; 4 foreach ( ∈ Γ+) do 5 foreach ( ∈ ) do 6 [] ← () ; 7 (, , ) ; 8 [].() ; 9 (, ) ;
Proc. 4: ProjectBinary(, ) 1 foreach ( ∈ ) do 2 ← ∈ {(, )} ; 3 foreach ( ∈ ) do 4 (, ) ← (, ) − ; 5 if ( is the current agent) 6 () ← () + ; Proc. 5: ProcessPruning(msg) 1 ← . ; 2 foreach ( ∈ Γ) do 3 foreach ( ∈ []) do 4 ← − ; 5 ← . ; 6 foreach ( ∈ Γ− ) do 7 (, , []) ; 8 []. ; 9 (, ) ; 10 () ; 11 ← {︀ , .}︀ + ; 12 ← 0 ; 13 DAC* () ; 14 () ; ∑︁ ,,∈ of . = = [(1, 1), . . . , ( , )] is a current partial assignment (CPA) or a feasible solution. [][ ] are the lower bounds of a lower neighbor obtained for . is a list of arrays containing values deleted by each agent . is a list of arrays containing extension values. (resp. * ) is the guaranteed cost of (resp. in AC* ). ( ) = * ( ) =
(, ) + () + ( ) | (, ), ( , ) ∈
Soft arc consistency techniques are used when solving a problem to delete values that are not part of its optimal solution. They are based on three operations:
The binary projection (Proc. 4) is an operation which subtracts, for a value of , the
smallest cost of a binary constraint and adds it to the unary constraint . The unary
projection (Proc. 1) is an operation which subtracts the smallest cost of a unary constraint
and adds it to the zero-arity constraint . The extension (Proc. 2) is an operation which
subtracts, for a value of , the extension value ([]) of from a unary constraint and
adds it to the binary constraint , with 0 < [] ≤ (). All of these operations are applied
to a problem under a set of conditions represented by soft arc consistency levels [
Node Consistency (NC* ) : a variable is NC* if each value ∈ satisfies + () < and there is a value ∈ with () = 0. A problem is NC* if its variables are NC* .
Directional Arc Consistency (DAC* ) : a variable is DAC* with respect to its neighbor (>) if is NC* and there is, for each value ∈ , a value ∈ which satisfies (, ) + ( ) = 0. is called a full support of . A problem is DAC* if any variable of this problem is DAC* with its neighbors (>).
To make a given problem DAC* , we first compute, for each variable with respect to its neighbors of lower priority (>), the extension values appropriate to the values of its domain (Proc. 3, . 6). Next, we perform the extension operation (Proc. 3, . 7) by subtracting the extension values from the unary constraints and adding them to the binary ones (Proc. 2). Then, each neighbor performs, successively, a binary projection (Proc. 4), a unary projection (Proc. 1), and finally a deletion of non-NC * values.
Each agent carries out the AFB_BJ+-AC* [
* ← .* ; 14 () ; 15 if (. = back) 16 ← − 1 ; () ; 17 if (. = fb?) 18 sendMsg : tolb(( )[], . ) ; 19 if (. = lb) 20 ( ) ← . ; 21 if (( ) ≥ ) () ; extended the CPA, it sends an ok? message to the next agent asking it to continue the extension of CPA . Otherwise, that is to say, the agent fails to extend the CPA, either because it doesn’t find a value that gives a valid CPA, or because all the values in its domain are exhausted, it stops the CPA extension and sends a back message to the appropriate agent. If such an agent doesn’t exist or the domain of becomes empty, stops its execution and informs the others via stp messages. A CPA is said to be valid if its lower bound doesn’t exceed the global upper bound, which represents the cost of the optimal solution achieved so far. Third, evaluates the extended CPA by sending fb? messages to unassigned agents asking them to evaluate the CPA and send the result of the evaluation. When an agent has completed its evaluation, it sends the result directly to the sender agent via an lb message. The evaluation is based on the calculation of appropriate lower bounds for the received CPA . The lower bound of is the minimal lower bound over all values of with respect to . 3. The AFB_BJ+-DAC* algorithm The AFB_BJ+-DAC* algorithm (Proc. 6) is the improved version of the AFB_BJ+-AC* algorithm, which uses DAC* to further reduce the domains of a given DCOP. AFB_BJ+-DAC* follows the same steps as the AFB_BJ+-AC* (§2.3), except that it performs DAC* instead of AC* before each extension of CPA (Proc. 7). DAC* is based on executing a set of cost extensions from unary constraints to binary ones, then on executing of AC* . DAC* () (Proc. 3) is the procedure responsible for calculating the extension costs (i.e., costs to be transferred) and () (Proc. 2) is the one that performs the extension of costs from the unary constraints towards the binary ones (§2.2). All the extension costs used by an agent are stored in a list, , and routed to its lower neighbors via an ok? message in order to keep the symmetry of constraints in each agent and its neighbors. The list of extension values, , is processed in the procedure () (Proc. 5, . 7-8).
Theorem 1. AFB_BJ+-DAC* is guaranteed to calculate the optimum and terminates.
Proof. The AFB_BJ+-DAC* algorithm outperforms AFB_BJ+-AC* [
We experimentally compare AFB_BJ+-DAC* with its older versions [
0 A 3,000 s e g a se2,000 s m f o r e b m1,000 u n 0 A
AFB_BJ+ AFB_BJ+-AC* AFB_BJ+-DAC*
BnB-Adopt+-DP2 B
C
D case
AFB_BJ+ AFB_BJ+-AC* AFB_BJ+-DAC*
BnB-Adopt+-DP2 0 A 0 A
B
C
D case
AFB_BJ+ AFB_BJ+-AC* AFB_BJ+-DAC* BnB-Adopt+-DP2 AFB_BJ+ AFB_BJ+-AC* AFB_BJ+-DAC*
BnB-Adopt+-DP2 B
C
D case
B
C
D case
Meetings scheduling [
Sensors network [
To compare the algorithms, we use two metrics, the total of messages exchanged () for the communication load and the total of non-concurrent constraint checks () for the computation efort.
Regarding meetings scheduling problems (Fig. 1), the results show a clear improvement of the AFB_BJ+-DAC* compared to others, whether for or for . But with regard to sensors network problems (Fig. 2), the BnB-Adopt+-DP2 retains the pioneering role, despite the superiority of the AFB_BJ+-DAC* to its older versions.
By analyzing the results, we can conclude that the AFB_BJ+-DAC* is better than its earlier versions because of the existence of DAC* which allows agents to remove more suboptimal values. This is due to a set of cost extensions applied to the problem. Regarding the superiority of the BnB-Adopt+-DP2 over the AFB_BJ+-DAC* in sensors network problems, this is mainly due to the arrangement of the pseudo-tree used by this algorithm that corresponds to the structure of these problems, as well as the existence of DP2 heuristic facilitates the proper choice of values.
In this paper, we have introduced the AFB_BJ+-DAC* algorithm. It is based on DAC* to increase the number of deletions made by each agent on its domain. DAC* mainly relies on performing a set of cost extensions in one direction from an agent to its lower priority neighbors in order to perform AC* multiple times and thus generate more deletions of non-optimal values. Experiments on some benchmarks show that the AFB_BJ+-DAC* algorithm behaves better than its older versions. As future work, we propose to exploit the change in the size of the agent domains in variable ordering heuristics.