The AFB_BJ+-AC* algorithm is one of the latest algorithms used to solve Distributed Constraint Optimization Problems known as DCOPs. It is based on soft arc consistency techniques (AC* ) to speed up the process of solving a problem by permanently removing any value that doesn't belong to the optimal solution. In fact, these techniques have greatly contributed to improving the performance of the AFB_BJ+ algorithm in solving DCOPs, but there are some exceptions in which they have no efect due to the limited number of deletions made. For that, we use in this paper a higher consistency level, which is a directional arc consistency (DAC* ). This level makes it possible 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.
more deletions and thus quickly reach the optimal solution of a problem. The new algorithm is called AFB_BJ+-DAC* . It uses DAC* to filter agent domains by performing a set of cost extensions from an agent to its neighbors, then executing AC* . Our experiments on diferent benchmarks show the superiority of AFB_BJ+-DAC* algorithm in terms of communication load and computation efort.
This paper comprises four sections. Section 2 gives an overview of DCOPs, soft arc consistency rules, and AFB_BJ+-AC* algorithm. Section 3 gives a description of AFB_BJ+-DAC* algorithm. Section 4 talks about experiments fulfilled on some benchmarks. The last section gives the conclusion.
A DCOP [
In this paper, while maintaining the generality, each DCOP is characterized in that each agent
is responsible for a single variable and that two variables, at most, are linked by a constraint
(i.e., unary or binary constraint) [
We consider these notations: is an agent, where is its level. ( , ) is an assignment of , where ∈ and ∈ . is a binary constraint between and , and is its binary cost. is an identical copy of the constraint, used in the AC* process. is a unary constraint on and is its unary cost. 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 and it is also the lowest unacceptable cost used for AC* process. [1, 2, . . . , ] is the lexicographic ordering of agents (the default ordering), Γ( ) = {Γ− : ∈ | ⊆ × , < } ∪ {Γ+ : ∈ | ⊆ × , > } is the set of neighbors of . Γ− (resp. Γ+) is a set of neighbors with a higher priority (resp. with a lower priority). = = [(1, 1), . . . , ( , )] is a current partial assignment (CPA). * is the optimal value of . [][ ] are the lower bounds of a lower neighbor obtained for . (resp. * ) are the guaranteed costs of (resp. in AC* ). is a list of arrays containing deleted values, each array, [], contains two elements, which is the list of values deleted by and which is a counter of the neighbors that have not yet processed . is a list of arrays containing extension values.
The guaranteed cost of is the sum of involved in (1).
( ) = ∑︁ (, ) | (, ), ( , ) ∈ (1) ∈
A CPA is said to be a complete assignment (i.e., a solution) when it comprises a value assignment for each variable of a DCOP. Solving a DCOP is to find a solution such that the sum of the Proc. 1: ProjectUnary() 1 ← ∈ {()} ; 2 ← + ; 3 foreach ( ∈ ) do 4 () ← () − ; Proc. 2: ProjectBinary(, ) 1 foreach ( ∈ ) do 2 ← ∈ {(, )} ; 3 foreach ( ∈ ) do 4 (, ) ← (, ) − ; 5 if ( is the current agent) 6 () ← () + ; Proc. 3: Extend(, , ) 1 foreach ( ∈ ) do 2 foreach ( ∈ ) do 3 (, ) ← (, ) + [] ; 4 if ( is the current agent) 5 () ← () − [] ; Proc. 4: CheckPruning() 1 foreach ( ∈ ) do 2 if (() + ≥ ) 3 ← − { } ; 4 []. .() ; 5 if ( ℎ) 6 []. ← . ; 7 if ( ) 8 broadcastMsg : stp( ) ; 9 ← ; Proc. 5: DAC* () 1 foreach ( ∈ Γ+) do 2 foreach ( ∈ ) do 3 [] ← () ; 4 (, , ) ; 5 [].() ; 6 (, ) ; Proc. 6: ProcessPruning(msg) 1 ← . ; 2 foreach ( ∈ Γ) do 3 foreach ( ∈ []) do 4 ← − { } ; 5 if ( ℎ) 6 []. .(− 1) ; 7 if ( []. = 0) 8 []. . ; 9 if (. = ok?) 10 ← . ; 11 foreach ( ∈ Γ− ) do 12 (, , []) ; 13 []. ; 14 (, ) ; 15 () ; 16 ← {︀ , .}︀ + ; 17 ← 0 ; 18 if ( ≥ ) 19 broadcastMsg : stp() ; 20 ← ; 21 ℎ () ; 22 DAC* () ; 23 () ; }.
costs of constraints involved in this solution is minimal, i.e., * = arg min{( ) | ( ) = Soft arc consistency techniques are used when solving a problem to delete values that are not part of the optimal solution of this problem. To apply these techniques to a problem, a set of transformations known as equivalence preserving transformations are used. They allow the exchange of costs between the constraints of the problem according to three manners that are a binary projection, a unary projection, and an extension.
The binary projection (Proc. 2) 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. 3) 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 transformations 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 each variable of this problem is NC* .
Arc Consistency (AC* ) : a variable is AC* with respect to its neighbor if is NC* and there is, for each value ∈ , a value ∈ which satisfies (, ) = 0. is called a simple support of . A problem is AC* if each variable of this problem is AC* .
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 each 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. 5, . 3). Next, we perform the extension operation (Proc. 5, . 4) by subtracting the extension values from the unary constraints and adding them to the binary ones (Proc. 3). Then, each neighbor performs, successively, a binary projection (Proc. 2), a unary projection (Proc. 1), and finally a deletion of non-NC * values. These last three instructions ensure the fulfillment of arc consistency (AC * ).
In a distributed case, each agent performs DAC* locally and shares the value of its
zeroarity constraint with the other agents in order to calculate the global (i.e., =
∑︀∈ )(Proc. 6, . 16). Each agent keeps locally for each of its constraints an
identical copy marked by and used in DAC* procedure. During DAC* , constraints are
changed. To keep the symmetry of these constraints in the agents, each agent applies, on its
copy , the same action of its neighbor and vice versa (Proc. 5, . 6) [
Each agent carries out the AFB_BJ+-AC* [
( )[] = ( − 1) +
∑︁ (,)∈ − 1 | <
(, ) * ( ) = * ( − 1) + ( ) + ∑︁ (, ) (,)∈ − 1 ∈ (2) (3) 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, containing the same data structures as an ok? message excluding and * , 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 (4) 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, which hold the same data structures excluding and , 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 (5) is the minimal lower bound over all values of with respect to .
(ℎ≤ <) ( )[ℎ] = min ∈ ︂{
∑︁ (,)∈ ℎ (≤ ℎ)
(, ) + (, ) + − 1 ∑︁ =ℎ+1 (ℎ<<) ∑︁ ∈Γ+() (>) min ∈ min ∈ { (, )} + {( , )} ︂} 3. The AFB_BJ+-DAC* algorithm The AFB_BJ+-DAC* algorithm uses a higher consistency level, which is a directional arc consistency (DAC* ). It improves the ability of AFB_BJ+-AC* algorithm to generate more deletions. It is based on executing a set of cost extensions from unary constraints to binary ones, then on executing of AC* . DAC* () (Proc. 5) is the procedure responsible for calculating the extension values (i.e., costs to be transferred) and () (Proc. 3) is the one that performs the extension of costs from the unary constraints towards the binary ones (§2.2). All the extension values 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. 6, . 9-13) in which DAC* () is also performed (Proc. 6, . 22).
The AFB_BJ+-DAC* (Proc. 7) is performed by each agent as follows :
starts with the initialization step (Proc. 7, . 1-3). If is the 1 agent (Proc. 7, . 4), it filters its domain by calling ℎ () (Proc. 4), then performs the appropriate extensions through DAC* () (Proc. 5), and finally calls () to generate a CPA .
Next, starts processing the messages (Proc. 7, . 9). First, it updates and * (Proc. 7, . 12). Then, updates and and erases all unrelated lower bounds if the received CPA (. ) is fresh compared to the local one ( ) (Proc. 7, . 13). Thereafter, restores all temporarily deleted values (Proc. 7, . 28). (4) (5)
When receiving an ok? message (Proc. 7, . 16), authorizes the sending of fb? messages and calls () (Proc. 6).
When calling () (Proc. 6), deals initially, for ok? messages only, with extensions of its higher neighbors (Proc. 6, . 9-13). Afterward, it updates its , then its neighbors’ domains separately in order to keep the same domains as these agents (Proc. 6, . 1-4). After that, it performs the two projections fulfilling the condition of AC * (Proc. 6, . 14-15). Next, decrements the unvisited neighbors of , []. , and then checks whether it is the last visited neighbor of this agent in order to reset its list of deleted values []. (Proc. 6, . 5-8). Then, updates its global (Proc. 6, . 16). If exceeds the , turns of its execution and notifies the others (Proc. 6, . 18-20). Finally, calls ℎ () to prune its domain, DAC* () (Proc. 5) to make the proper extensions, and () to extend the received CPA (Proc. 6, . 21-23).
When calling DAC* () (Proc. 5), performs the proper extensions from to each (Proc. 5, . 4-5). To do that, calculates, for each value of , its extension value (Proc. 5, . 2-3) based on the unary cost of this value (0 < [] ≤ ()). Once completed, performs a binary projection to keep the symmetry of constraints (Proc. 5, . 6). It should be noted that the direction taken into account by each agent for the extension of its costs is towards its lower neighbors (Γ+( )).
When calling ℎ () (Proc. 4), deletes any value from its domain for which the sum of the with the unary cost of this value exceeds (Proc. 4, . 2-3). With each new deletion, initializes the number of its neighbors not yet visited (Proc. 4, . 5-6). If domain becomes empty, turns of its execution and notifies the others (Proc. 4, . 7-9).
When calling () (Proc. 8), looks for a value for its variable (Proc. 8, . 1). If no value exists, returns to the priority agents by sending a back message to the contradictory agent (Proc. 8, . 2-5). If no agent exists, turns of its execution and notifies the others via stp messages (Proc. 8, . 6-7). Otherwise, extends by adding its assignment (Proc. 8, . 9). If is the last agent (Proc. 8, . 10) then a new solution is obtained and the is updated, which obliges to call ℎ () to filter again its domain and then () to proceed the search (Proc. 8, . 11-14). Otherwise, sends an ok? message loaded with the extended to the next agent (Proc. 8, . 16) and fb? messages to unassigned agents (Proc. 8, . 19).
When receives an fb? message, it filters its domain with respect to the received (Proc. 7, . 24-28), calculates the appropriate lower bounds (5), and immediately sends them to the sender via lb message (Proc. 7, . 29).
When receives an lb message, it stores the lower bounds received (Proc. 7, . 34) and performs () to modify its assignment if the lower bound calculated, based on the cost of (4), exceeds the .
Theorem 1. AFB_BJ+-DAC* is guaranteed to calculate the optimum and terminates.
Proof. The AFB_BJ+-DAC* algorithm outperforms AFB_BJ+-AC* [
In this section, we experimentally compare the AFB_BJ+-DAC* algorithm with its older versions
[
Meetings scheduling [
Sensors network [
To compare the algorithms, we use two metrics which are the total of messages exchanged () that represents the communication load and the total of non-concurrent constraint checks () that represents 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* algorithm 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 directional arc consistency (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 an algorithm that relies on DAC* to generate more deletions and thus quickly reach the optimal solution of a problem. 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, which increases the number of deletions made by each agent and thereby speed up the process of solving a problem. 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.