=Paper= {{Paper |id=Vol-2987/paper9 |storemode=property |title=Using Directional Arc Consistency with Asynchronous Forward-Bounding algorithm |pdfUrl=https://ceur-ws.org/Vol-2987/paper9.pdf |volume=Vol-2987 |authors=Rachid Adrdor,Lahcen Koutti |dblpUrl=https://dblp.org/rec/conf/gandalf/AdrdorK21 }} ==Using Directional Arc Consistency with Asynchronous Forward-Bounding algorithm== https://ceur-ws.org/Vol-2987/paper9.pdf 
Using Directional Arc Consistency with
Asynchronous Forward-Bounding algorithm
Rachid Adrdor1 , Lahcen Koutti1
1
    Ibn Zohr University, Faculty of Sciences, Department of Computer Science, Agadir, Morocco


                                         Abstract
                                         The AFB_BJ+ -AC* algorithm is one of the latest algorithms used to solve Distributed Constraint Op-
                                         timization 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
                                         effort.

                                         Keywords
                                         DCOP, AFB_BJ+ , AC* , Directional Arc Consistency




1. Introduction
A large number of multi-agent problems can be modeled as DCOPs such as meetings scheduling
[1]. In a DCOP, variables, domains, and constraints are distributed among a set of agents. Each
agent has full control over a subset of variables and the constraints that involve them [2]. A
solution to a DCOP is a set of value assignments, each representing the value assigned to one of
the variables in that DCOP.
   To solve DCOPs, algorithms with different search strategies have been suggested in the liter-
ature, for example, Adopt[3], BnB-Adopt[4], BnB-Adopt+ [5], BnB-Adopt+ -AC* [6], SyncBB[7],
AFB[2], AFB_BJ+ [8], etc. AFB_BJ+ -AC* [9, 10, 11] is one of the recent algorithms that uses arc
consistency (AC* ) to solve DCOPs.
   In this paper, instead of using the basic level of arc consistency (AC* ), we use directional
arc consistency (DAC* ). DAC* allows AFB_BJ+ to generate more deletions and thus quickly
reach the optimal solution to 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 different benchmarks show the superiority
of AFB_BJ+ -DAC* algorithm in terms of communication load and computation effort.


2. Background
2.1. Distributed Constraint Optimization Problem (DCOP)
A DCOP [11, 12, 13] is defined by 4 sets, agents π’œ = {𝐴1 , 𝐴2 , ..., π΄π‘˜ }, variables 𝒳 =
{π‘₯1 , π‘₯2 , ..., π‘₯𝑛 }, domains π’Ÿ = {𝐷1 , 𝐷2 , ..., 𝐷𝑛 }, where each 𝐷𝑖 contains the possible val-
ues for π‘₯𝑖 , and constraints π’ž = {𝐢𝑖𝑗 : 𝐷𝑖 Γ— 𝐷𝑗 β†’ R+ } βˆͺ {𝐢𝑖 : 𝐷𝑖 β†’ R+ }. In this article, we
consider that each agent of a given DCOP is responsible for a single variable and that at most
two variables are related by a constraint (i.e. unary or binary constraint) [14].
   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

OVERLAY 2021: 3rd Workshop on Artificial Intelligence and Formal Verification, Logic, Automata, and Synthesis,
September 22, 2021, Padova, Italy
" rachid.adrdor@edu.uiz.ac.ma (R. Adrdor); l.koutti@uiz.ac.ma (L. Koutti)
                                       Β© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073       CEUR Workshop Proceedings (CEUR-WS.org)
       Proc. 1: ProjectUnary()                            Proc. 4: ProjectBinary(π‘₯𝑖 , π‘₯𝑗 )
   1 𝛽 ← π‘šπ‘–π‘›π‘£π‘– βˆˆπ·π‘– {𝑐𝑖 (𝑣𝑖 )} ;                          1 foreach (𝑣𝑖 ∈ 𝐷𝑖 ) do
   2 πΆπœ‘ ← πΆπœ‘ + 𝛽 ;                                       2    𝛼 ← π‘šπ‘–π‘›π‘£π‘— βˆˆπ·π‘— {𝑐𝑖𝑗 (𝑣𝑖 , 𝑣𝑗 )} ;
        𝑖         𝑖
   3 foreach (𝑣𝑖 ∈ 𝐷𝑖 ) do                               3    foreach (𝑣𝑗 ∈ 𝐷𝑗 ) do
   4    𝑐𝑖 (𝑣𝑖 ) ← 𝑐𝑖 (𝑣𝑖 ) βˆ’ 𝛽 ;                        4        𝑐𝑖𝑗 (𝑣𝑖 , 𝑣𝑗 ) ← 𝑐𝑖𝑗 (𝑣𝑖 , 𝑣𝑗 ) βˆ’ 𝛼 ;
                                                         5    if (𝐴𝑖 is the current agent)
       Proc. 2: Extend(π‘₯𝑖 , π‘₯𝑗 , 𝐸)                      6        𝑐𝑖 (𝑣𝑖 ) ← 𝑐𝑖 (𝑣𝑖 ) + 𝛼 ;
   1 foreach (𝑣𝑖 ∈ 𝐷𝑖 ) do
   2    foreach (𝑣𝑗 ∈ 𝐷𝑗 ) do                             Proc. 5: ProcessPruning(msg)
   3        𝑐𝑖𝑗 (𝑣𝑖 , 𝑣𝑗 ) ← 𝑐𝑖𝑗 (𝑣𝑖 , 𝑣𝑗 ) + 𝐸[𝑣𝑖 ] ;   1  𝐷𝑉 π‘Žπ‘™π‘  ← π‘šπ‘ π‘”.𝐷𝑉 π‘Žπ‘™π‘  ;
   4    if (𝐴𝑖 is the current agent)                     2  foreach (π΄π‘˜ ∈ Ξ“) do
   5        𝑐𝑖 (𝑣𝑖 ) ← 𝑐𝑖 (𝑣𝑖 ) βˆ’ 𝐸[𝑣𝑖 ] ;                3    foreach (π‘Ž ∈ 𝐷𝑉 π‘Žπ‘™π‘ [π‘˜]) do
                                                          4       π·π‘˜ ← π·π‘˜ βˆ’ π‘Ž ;
       Proc. 3: DAC* ()                                   5 𝐸𝑉 π‘Žπ‘™π‘  ← π‘šπ‘ π‘”.𝐸𝑉 π‘Žπ‘™π‘  ;
                                                          6 foreach (π΄π‘˜ ∈ Ξ“βˆ’ ) do
   1 foreach (π‘Ž ∈ 𝐷𝑗 ) do
   2    if (𝑐𝑗 (π‘Ž) + πΆπœ‘ β‰₯ π‘ˆ 𝐡𝑗 )                          7    𝐸π‘₯𝑑𝑒𝑛𝑑(π‘₯π‘˜ , π‘₯𝑗 , 𝐸𝑉 π‘Žπ‘™π‘ [π‘˜π‘—]) ;
   3        𝐷𝑗 ← 𝐷𝑗 βˆ’ π‘Ž ; 𝐷𝑉 π‘Žπ‘™π‘ [𝑗].π‘Žπ‘‘π‘‘(π‘Ž) ;              8    𝐸𝑉 π‘Žπ‘™π‘ [π‘˜π‘—].π‘π‘™π‘’π‘Žπ‘Ÿ ;
                                                          9    𝑃 π‘Ÿπ‘œπ‘—π‘’π‘π‘‘π΅π‘–π‘›π‘Žπ‘Ÿπ‘¦(π‘₯𝑗 , π‘₯π‘˜ ) ;
   4 foreach (π΄π‘˜ ∈ Ξ“+ ) do
                                                         10    𝑃 π‘Ÿπ‘œπ‘—π‘’π‘π‘‘π‘ˆ π‘›π‘Žπ‘Ÿπ‘¦() ;
   5    foreach (𝑣𝑗 ∈ 𝐷𝑗 ) do                                           {οΈ€             }οΈ€
                                                         11 πΆπœ‘ ← π‘šπ‘Žπ‘₯ πΆπœ‘ , π‘šπ‘ π‘”.πΆπœ‘ + πΆπœ‘ ;
   6       𝐸[𝑣𝑗 ] ← 𝑐𝑗 (𝑣𝑗 ) ;                                                                𝑗
   7    𝐸π‘₯𝑑𝑒𝑛𝑑(π‘₯𝑗 , π‘₯π‘˜ , 𝐸) ;                            12 πΆπœ‘ ← 0 ;
                                                               𝑗
   8    𝐸𝑉 π‘Žπ‘™π‘ [π‘—π‘˜].𝑝𝑒𝑑(𝐸) ;                              13 DAC* () ;
   9    𝑃 π‘Ÿπ‘œπ‘—π‘’π‘π‘‘π΅π‘–π‘›π‘Žπ‘Ÿπ‘¦(π‘₯π‘˜ , π‘₯𝑗 ) ;                       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* ).
                                  βˆ‘οΈ
     𝐺𝐢(π‘Œ ) = 𝐺𝐢 * (π‘Œ ) =                    𝑐𝑖𝑗 (𝑣𝑖 , 𝑣𝑗 ) + 𝑐𝑖 (𝑣𝑖 ) + 𝑐𝑗 (𝑣𝑗 ) | (π‘₯𝑖 , 𝑣𝑖 ), (π‘₯𝑗 , 𝑣𝑗 ) ∈ π‘Œ
                                       𝐢𝑖𝑗 ,𝐢𝑖 ,𝐢𝑗 βˆˆπ’ž


2.2. Soft arc consistency
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 [15], namely:
   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.

2.3. AFB_BJ+ -AC* algorithm
Each agent 𝐴𝑗 carries out the AFB_BJ+ -AC* [9] according to three phases. First, 𝐴𝑗 initializes
its data structures and performs the AC* in which it deletes permanently all suboptimal values
from its domain 𝐷𝑗 . Second, 𝐴𝑗 chooses, for its variable π‘₯𝑗 , a value from its previously filtered
domain 𝐷𝑗 in order to extend the CPA π‘Œ 𝑗 by its value assignment (π‘₯𝑗 , 𝑣𝑗 ). If 𝐴𝑗 has successfully
       Proc. 6: AFB_BJ+ -DAC* ()                       Proc. 7: ExtendCPA()
   1 Init. of data structures                         1 if (𝑙𝑏(π‘Œ βˆͺ (π‘₯𝑗 , 𝑣𝑗 )) β‰₯ π‘ˆ 𝐡𝑗 ) ∨
   2 if (𝐴𝑗 = 𝐴1 )                                        (πΆπœ‘ + 𝐺𝐢 * (π‘Œ π‘—βˆ’1 ) + 𝑐𝑗 (𝑣𝑗 ) β‰₯ π‘ˆ 𝐡𝑗 )
   3     πΆπœ‘ ← πΆπœ‘ + πΆπœ‘ 𝑗 ; πΆπœ‘ 𝑗 ← 0;                   2     for 𝑖 ← 𝑗 βˆ’ 1 to 1 do
   4     DAC* () ;                                    3        if (𝑙𝑏(π‘Œ )[𝑖 βˆ’ 1] < π‘ˆ 𝐡𝑗 )
   5     𝐸π‘₯𝑑𝑒𝑛𝑑𝐢𝑃 𝐴() ;                               4            sendMsg : back(π‘Œ 𝑖 , π‘ˆ 𝐡𝑗 , 𝐷𝑉 π‘Žπ‘™π‘ , πΆπœ‘ ) ;
                                                                              to 𝐴𝑖
   6 while (¬𝑒𝑛𝑑) do                                                return ;
   7     π‘šπ‘ π‘” ← 𝑔𝑒𝑑𝑀 𝑠𝑔() ;                             5    broadcastMsg : stp(π‘ˆ 𝐡𝑗 ) ;
   8     if (π‘šπ‘ π‘”.π‘ˆ 𝐡 < π‘ˆ 𝐡𝑗 )                          6    𝑒𝑛𝑑 ← π‘‘π‘Ÿπ‘’π‘’ ;
   9         π‘ˆ 𝐡𝑗 ← π‘šπ‘ π‘”.π‘ˆ 𝐡 ;                          7 else
  10     if (π‘šπ‘ π‘”.π‘Œ is stronger than π‘Œ )                8    π‘Œ ← {π‘Œ βˆͺ (π‘₯𝑗 , 𝑣𝑗 )} ;
  11         π‘Œ ← π‘šπ‘ π‘”.π‘Œ ; 𝐺𝐢 ← π‘šπ‘ π‘”.𝐺𝐢 ;                 9    if (π‘£π‘Žπ‘Ÿ(π‘Œ ) = X)
  12     if (π‘šπ‘ π‘”.𝑑𝑦𝑝𝑒 = ok?)                          10        π‘ˆ 𝐡𝑗 ← 𝐺𝐢(π‘Œ ) ; π‘Œ ← π‘Œ π‘—βˆ’1 ;
  13         π‘šπ‘’π‘ π‘‘π‘†π‘’π‘›π‘‘πΉ 𝐡 ← 𝑇 π‘Ÿπ‘’π‘’ ;                    11        DAC* () ;
               𝐺𝐢 * ← π‘šπ‘ π‘”.𝐺𝐢 * ;                      12        𝐸π‘₯𝑑𝑒𝑛𝑑𝐢𝑃 𝐴() ;
  14         𝑃 π‘Ÿπ‘œπ‘π‘’π‘ π‘ π‘ƒ π‘Ÿπ‘’π‘›π‘–π‘›π‘”(π‘šπ‘ π‘”) ;                  13    else
  15     if (π‘šπ‘ π‘”.𝑑𝑦𝑝𝑒 = back)                         14        sendMsg : ok? (π‘Œ, 𝐺𝐢, π‘ˆ 𝐡𝑗 , 𝐷𝑉 π‘Žπ‘™π‘ ,
                                                                         to 𝐴𝑗+1
  16         π‘Œ ← π‘Œ π‘—βˆ’1 ; 𝑃 π‘Ÿπ‘œπ‘π‘’π‘ π‘ π‘ƒ π‘Ÿπ‘’π‘›π‘–π‘›π‘”(π‘šπ‘ π‘”) ;
  17     if (π‘šπ‘ π‘”.𝑑𝑦𝑝𝑒 = fb?)                                    𝐸𝑉 π‘Žπ‘™π‘ , πΆπœ‘ , 𝐺𝐢 * ) ;
  18         sendMsg : lb (𝑙𝑏𝑗 (π‘Œ 𝑖 )[], π‘šπ‘ π‘”.π‘Œ ) ;    15      𝐸𝑉 π‘Žπ‘™π‘ .π‘π‘™π‘’π‘Žπ‘Ÿ ;
                         to 𝐴𝑖                        16      if (π‘šπ‘’π‘ π‘‘π‘†π‘’π‘›π‘‘πΉ 𝐡)
  19       if (π‘šπ‘ π‘”.𝑑𝑦𝑝𝑒 = lb)                         17          sendMsg : fb? (π‘Œ, 𝐺𝐢, π‘ˆ 𝐡𝑗 , 𝐺𝐢 * ) ;
                                                                              to π΄π‘˜>𝑗
  20           π‘™π‘π‘˜ (π‘Œ 𝑗 ) ← π‘šπ‘ π‘”.𝑙𝑏 ;
  21           if (𝑙𝑏(π‘Œ 𝑗 ) β‰₯ π‘ˆ 𝐡𝑗 ) 𝐸π‘₯𝑑𝑒𝑛𝑑𝐢𝑃 𝐴() ;   18         π‘šπ‘’π‘ π‘‘π‘†π‘’π‘›π‘‘πΉ 𝐡 ← 𝑓 π‘Žπ‘™π‘ π‘’ ;




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* [9] by executing a set of cost
extensions. These extensions have already been proved which are correct in [15, 16], and they
are executed by the AFB_BJ+ -DAC* without any cost redundancy (Proc. 2, 𝑙. 4), (Proc. 3, 𝑙. 9),
and (Proc. 5, 𝑙. 7-8).


4. Experimental Results
We experimentally compare AFB_BJ+ -DAC* with its older versions [8, 9] and with the BnB-
Adopt+ -DP2 algorithm [17], which is its famous competitor. Two benchmarks are used in these
experiments:
                                     1,000                   AFB_BJ+                                                     AFB_BJ+
                                                             AFB_BJ+ -AC*                         6,000                  AFB_BJ+ -AC*
                                                             AFB_BJ+ -DAC*                                               AFB_BJ+ -DAC*




                number of messages
                                      800                    BnB-Adopt+ -DP2                                             BnB-Adopt+ -DP2




                                                                                number of ncccs
                                                                                                  4,000
                                      600

                                      400
                                                                                                  2,000
                                      200

                                        0                                                            0
                                             A    B          C              D                             A   B          C              D
                                                      case                                                        case


                                     Figure 1: Total of π‘šπ‘ π‘”π‘  sent and 𝑛𝑐𝑐𝑐𝑠 for meetings scheduling

                                     3,000                   AFB_BJ+                                                     AFB_BJ+
                                                             AFB_BJ+ -AC*                         8,000                  AFB_BJ+ -AC*
                                                             AFB_BJ+ -DAC*                                               AFB_BJ+ -DAC*
                number of messages




                                                             BnB-Adopt+ -DP2                                             BnB-Adopt+ -DP2




                                                                                number of ncccs
                                                                                                  6,000
                                     2,000

                                                                                                  4,000

                                     1,000
                                                                                                  2,000


                                        0                                                            0
                                             A    B          C              D                             A   B          C              D
                                                      case                                                        case


                                       Figure 2: Total of π‘šπ‘ π‘”π‘  sent and 𝑛𝑐𝑐𝑐𝑠 for sensors network


   Meetings scheduling [1]: are defined by the number of meetings/variables, the number of
participants, and the number of time slots for each meeting. We have evaluated 4 cases A, B, C,
and D, which are different in terms of meetings/participants [1].
   Sensors network [18]: are defined by the number of targets/variables, the number of sensors,
and the number of possible combinations of 3 sensors reserved for tracking each target. We
have evaluated 4 cases A, B, C, and D, which are different in terms of targets/sensors [1].
   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 effort.
   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.


5. Conclusion
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.
References
 [1] R. T. Maheswaran, M. Tambe, E. Bowring, J. P. Pearce, P. Varakantham, Taking dcop
     to the real world: Efficient complete solutions for distributed multi-event scheduling,
     in: Proceedings of the Third International Joint Conference on Autonomous Agents and
     Multiagent Systems-Volume 1, IEEE Computer Society, 2004, pp. 310–317.
 [2] A. Gershman, A. Meisels, R. Zivan, Asynchronous forward bounding for distributed cops,
     Journal of Artificial Intelligence Research 34 (2009) 61–88.
 [3] P. J. Modi, W.-M. Shen, M. Tambe, M. Yokoo, Adopt: Asynchronous distributed constraint
     optimization with quality guarantees, Artificial Intelligence 161 (2005) 149–180.
 [4] W. Yeoh, A. Felner, S. Koenig, Bnb-adopt: An asynchronous branch-and-bound dcop
     algorithm, Journal of Artificial Intelligence Research 38 (2010) 85–133.
 [5] P. Gutierrez, P. Meseguer, Saving messages in adopt-based algorithms, in: Proc. 12th DCR
     workshop in AAMAS-10, Citeseer, 2010, pp. 53–64.
 [6] P. Gutierrez, P. Meseguer, Improving bnb-adopt+-ac, in: Proceedings of the 11th Interna-
     tional Conference on Autonomous Agents and Multiagent Systems-Volume 1, International
     Foundation for Autonomous Agents and Multiagent Systems, 2012, pp. 273–280.
 [7] K. Hirayama, M. Yokoo, Distributed partial constraint satisfaction problem, in: Interna-
     tional Conference on Principles and Practice of Constraint Programming, Springer, 1997,
     pp. 222–236.
 [8] M. Wahbi, R. Ezzahir, C. Bessiere, Asynchronous forward bounding revisited, in: Interna-
     tional Conference on Principles and Practice of Constraint Programming, Springer, 2013,
     pp. 708–723.
 [9] R. Adrdor, R. Ezzahir, L. Koutti, Connecting afb_bj+ with soft arc consistency, International
     Journal of Computing and Optimization 5 no. 1 (2018) 9–20.
[10] R. Adrdor, L. Koutti, Enhancing AFB_BJ+ AC* algorithm, in: 2019 International Conference
     of Computer Science and Renewable Energies (ICCSRE), IEEE, 2019, pp. 1–7.
[11] R. Adrdor, R. Ezzahir, L. Koutti, Consistance d’arc souple appliquΓ©e aux problΓ¨mes dcop,
     JournΓ©es d’Intelligence Artificielle Fondamentale (JIAF) (2020) 63.
[12] T. Grinshpoun, T. Tassa, V. Levit, R. Zivan, Privacy preserving region optimal algorithms
     for symmetric and asymmetric dcops, Artificial Intelligence 266 (2019) 27–50.
[13] F. Fioretto, E. Pontelli, W. Yeoh, Distributed constraint optimization problems and applica-
     tions: A survey, Journal of Artificial Intelligence Research 61 (2018) 623–698.
[14] D. T. Nguyen, W. Yeoh, H. C. Lau, R. Zivan, Distributed gibbs: A linear-space sampling-
     based dcop algorithm, Journal of Artificial Intelligence Research 64 (2019) 705–748.
[15] J. Larrosa, T. Schiex, In the quest of the best form of local consistency for weighted csp, in:
     IJCAI, volume 3, 2003, pp. 239–244.
[16] M. C. Cooper, S. De Givry, M. SΓ‘nchez, T. Schiex, M. Zytnicki, T. Werner, Soft arc
     consistency revisited, Artificial Intelligence 174 (2010) 449–478.
[17] S. Ali, S. Koenig, M. Tambe, Preprocessing techniques for accelerating the dcop algorithm
     adopt, in: Proceedings of the fourth international joint conference on Autonomous agents
     and multiagent systems, ACM, 2005, pp. 1041–1048.
[18] R. BΓ©jar, C. Domshlak, C. FernΓ‘ndez, C. Gomes, B. Krishnamachari, B. Selman, M. Valls, Sen-
     sor networks and distributed csp: communication, computation and complexity, Artificial
     Intelligence 161 (2005) 117–147.