Using Directional Arc Consistency with Asynchronous Forward-Bounding algorithm RachidAdrdor rachid.adrdor@edu.uiz.ac.ma Faculty of Sciences Department of Computer Science Ibn Zohr University
Agadir Morocco
LahcenKoutti l.koutti@uiz.ac.ma Faculty of Sciences Department of Computer Science Ibn Zohr University
Agadir Morocco
Using Directional Arc Consistency with Asynchronous Forward-Bounding algorithm 1613-0073 C11FC56E811908A2B24AE6587508854A GROBID - A machine learning software for extracting information from scholarly documents DCOP AFB_BJ + AC * Directional Arc Consistency

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 effort.
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 literature, 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.

Background
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 values 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. [𝐴

𝐺𝐢(π‘Œ ) = 𝐺𝐢 * (π‘Œ ) = βˆ‘οΈ 𝐢 𝑖𝑗 ,𝐢 𝑖 ,𝐢 𝑗 βˆˆπ’ž 𝑐 𝑖𝑗 (𝑣 𝑖 , 𝑣 𝑗 ) + 𝑐 𝑖 (𝑣 𝑖 ) + 𝑐 𝑗 (𝑣 𝑗 ) | (π‘₯ 𝑖 , 𝑣 𝑖 ), (π‘₯ 𝑗 , 𝑣 𝑗 ) ∈ π‘Œ
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] 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.

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 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 π‘Œ 𝑖 .

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).

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: 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.

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.

Figure 1 :Figure 2 :Figure 1: Total of π‘šπ‘ π‘”π‘  sent and 𝑛𝑐𝑐𝑐𝑠 for meetings scheduling
do 4π‘₯ 𝑖 ∈ 𝒳 | 𝐢 𝑖𝑗 ∈ π’ž, 𝑖 > 𝑗} is the set of neighbors π‘šπ‘–π‘› 𝑣 𝑖 ∈𝐷 𝑖 {𝑐 𝑖 (𝑣 𝑖 )} ; 2 𝐢 πœ‘ 𝑖 ← 𝐢 πœ‘ 𝑖 + 𝛽 ; 3 foreach (𝑣 𝑖 ∈ 𝐷 𝑖 ) 𝑐 𝑖 (𝑣 𝑖 ) ← 𝑐 𝑖 (𝑣 𝑖 ) βˆ’ 𝛽 ;Proc. 1: ProjectUnary()
1 , 𝐴 2 , . . . , 𝐴 𝑛 ] is the lexicographic ordering of agents (the default ordering), Ξ“(π‘₯ 𝑗 ) = {Ξ“ βˆ’ : π‘₯ 𝑖 ∈ 𝒳 | 𝐢 𝑖𝑗 ∈ π’ž, 𝑖 < 𝑗} βˆͺ {Ξ“ + : 1 𝛽 ←
Proc. 2: Extend(π‘₯ 𝑖 , π‘₯ 𝑗 , 𝐸)
1 foreach (𝑣 𝑖 ∈ 𝐷 𝑖 ) do 2 foreach (𝑣 𝑗 ∈ 𝐷 𝑗 ) do 3𝑐 𝑖𝑗 (𝑣 𝑖 , 𝑣 𝑗 ) ← 𝑐 𝑖𝑗 (𝑣 𝑖 , 𝑣 𝑗 ) + 𝐸[𝑣 𝑖 ] ; 𝑐 𝑖 (𝑣 𝑖 ) ← 𝑐 𝑖 (𝑣 𝑖 ) βˆ’ 𝐸[𝑣 𝑖 ] ;
4if (𝐴 𝑖 is the current agent)
5
Proc. 3: DAC * () 1 foreach (π‘Ž ∈ 𝐷 𝑗 ) do 2 if (𝑐 𝑗 (π‘Ž) + 𝐢 πœ‘ β‰₯ π‘ˆ 𝐡 𝑗 )3𝐷 𝑗 ← 𝐷 𝑗 βˆ’ π‘Ž ; 𝐷𝑉 π‘Žπ‘™π‘ [𝑗].π‘Žπ‘‘π‘‘(π‘Ž) ;4 foreach (𝐴 π‘˜ ∈ Ξ“ + ) do5foreach (𝑣 𝑗 ∈ 𝐷 𝑗 ) do6𝐸[𝑣 𝑗 ] ← 𝑐 𝑗 (𝑣 𝑗 ) ;7𝐸π‘₯𝑑𝑒𝑛𝑑(π‘₯ 𝑗 , π‘₯ π‘˜ , 𝐸) ;8𝐸𝑉 π‘Žπ‘™π‘ [π‘—π‘˜].𝑝𝑒𝑑(𝐸) ;9𝑃 π‘Ÿπ‘œπ‘—π‘’π‘π‘‘π΅π‘–π‘›π‘Žπ‘Ÿπ‘¦(π‘₯ π‘˜ , π‘₯ 𝑗 ) ;
Proc. 4: ProjectBinary(π‘₯ 𝑖 , π‘₯ 𝑗 ) 1 foreach (𝑣 𝑖 ∈ 𝐷 𝑖 ) do 2𝛼 ← π‘šπ‘–π‘› 𝑣 𝑗 ∈𝐷 𝑗 {𝑐 𝑖𝑗 (𝑣 𝑖 , 𝑣 𝑗 )} ;
3 foreach (𝑣 𝑗 ∈ 𝐷 𝑗 ) do 4𝑐 𝑖𝑗 (𝑣 𝑖 , 𝑣 𝑗 ) ← 𝑐 𝑖𝑗 (𝑣 𝑖 , 𝑣 𝑗 ) βˆ’ 𝛼 ; 𝑐 𝑖 (𝑣 𝑖 ) ← 𝑐 𝑖 (𝑣 𝑖 ) + 𝛼 ;
5if (𝐴 𝑖 is the current agent)Proc. 5: ProcessPruning(msg)
6 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 * ).
𝐷 𝑖 satisfies 𝐢 πœ‘ + 𝑐 𝑖 (𝑣 𝑖 ) < π‘ˆ 𝐡 𝑖 and there is a value 𝑣 𝑖 ∈ 𝐷 𝑖 with 𝑐 𝑖 (𝑣 𝑖 ) = 0. A problem is NC * if its variables are NC 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 π‘₯ 𝑗(𝑗>𝑖) ., namely: Node Consistency (NC * ) : a variable π‘₯ 𝑖 is NC * if each value 𝑣 𝑖 ∈ * . Directional Arc Consistency (DAC * ) : a variable π‘₯ 𝑖 is DAC *
Init. of data structures 2 if (𝐴 𝑗 = 𝐴 1 ) 𝐢 πœ‘ ← 𝐢 πœ‘ + 𝐢 πœ‘ 𝑗 ; 𝐢 πœ‘ 𝑗 ← 0; π‘ˆ 𝐡 𝑗 ← π‘šπ‘ π‘”.π‘ˆ 𝐡 ; π‘Œ ← {π‘Œ βˆͺ (π‘₯ 𝑗 , 𝑣 𝑗 )} ; 𝐺𝐢, π‘ˆ 𝐡 𝑗 , 𝐷𝑉 π‘Žπ‘™π‘ , 𝐸𝑉 π‘Žπ‘™π‘ , 𝐢 πœ‘ , 𝐺𝐢 * ) ; 𝐺𝐢, π‘ˆ 𝐡 𝑗 , 𝐺𝐢 * ) ;
5𝐸π‘₯𝑑𝑒𝑛𝑑𝐢𝑃 𝐴() ;6 while (¬𝑒𝑛𝑑) do7π‘šπ‘ π‘” ← 𝑔𝑒𝑑𝑀 𝑠𝑔() ;8if (π‘šπ‘ π‘”.π‘ˆ 𝐡 < π‘ˆ 𝐡 𝑗 )10if (π‘šπ‘ π‘”.π‘Œ is stronger than π‘Œ )11π‘Œ ← π‘šπ‘ π‘”.π‘Œ ; 𝐺𝐢 ← π‘šπ‘ π‘”.𝐺𝐢 ;9if (π‘£π‘Žπ‘Ÿ(π‘Œ ) = X)12if (π‘šπ‘ π‘”.𝑑𝑦𝑝𝑒 = ok?)10π‘ˆ 𝐡 𝑗 ← 𝐺𝐢(π‘Œ ) ; π‘Œ ← π‘Œ π‘—βˆ’1 ;13π‘šπ‘’π‘ π‘‘π‘†π‘’π‘›π‘‘πΉ 𝐡 ← 𝑇 π‘Ÿπ‘’π‘’ ;11DAC * () ;𝐺𝐢 17 if (π‘šπ‘ π‘”.𝑑𝑦𝑝𝑒 = fb?) 18 sendMsg : lb to 𝐴 𝑖 (𝑙𝑏 𝑗 (π‘Œ 𝑖 )[], π‘šπ‘ π‘”.π‘Œ ) ;12 13 14 (π‘Œ, 15 𝐸π‘₯𝑑𝑒𝑛𝑑𝐢𝑃 𝐴() ; else sendMsg : ok? to 𝐴 𝑗+1 𝐸𝑉 π‘Žπ‘™π‘ .π‘π‘™π‘’π‘Žπ‘Ÿ ; 16 if (π‘šπ‘’π‘ π‘‘π‘†π‘’π‘›π‘‘πΉ 𝐡)19if (π‘šπ‘ π‘”.𝑑𝑦𝑝𝑒 = lb)17 (π‘Œ, 18 sendMsg : fb? to 𝐴 π‘˜>𝑗 π‘šπ‘’π‘ π‘‘π‘†π‘’π‘›π‘‘πΉ 𝐡 ← 𝑓 π‘Žπ‘™π‘ π‘’ ;
Proc. 6: AFB_BJ + -DAC * () 1 3 4 DAC * () ; 9 * ← π‘šπ‘ π‘”.𝐺𝐢 * ; 14 𝑃 π‘Ÿπ‘œπ‘π‘’π‘ π‘ π‘ƒ π‘Ÿπ‘’π‘›π‘–π‘›π‘”(π‘šπ‘ π‘”) ; 15 if (π‘šπ‘ π‘”.𝑑𝑦𝑝𝑒 = back) 16 π‘Œ ← π‘Œ π‘—βˆ’1 ; 𝑃 π‘Ÿπ‘œπ‘π‘’π‘ π‘ π‘ƒ π‘Ÿπ‘’π‘›π‘–π‘›π‘”(π‘šπ‘ π‘”) ; 20 𝑙𝑏 π‘˜ (π‘Œ 𝑗 ) ← π‘šπ‘ π‘”.𝑙𝑏 ; 21 if (𝑙𝑏(π‘Œ 𝑗 ) β‰₯ π‘ˆ 𝐡 𝑗 ) 𝐸π‘₯𝑑𝑒𝑛𝑑𝐢𝑃 𝐴() ; Proc. 7: ExtendCPA() 1 if (𝑙𝑏(π‘Œ βˆͺ (π‘₯ 𝑗 , 𝑣 𝑗 )) β‰₯ π‘ˆ 𝐡 𝑗 ) ∨ (𝐢 πœ‘ + 𝐺𝐢 * (π‘Œ π‘—βˆ’1 ) + 𝑐 𝑗 (𝑣 𝑗 ) β‰₯ π‘ˆ 𝐡 𝑗 ) 2 for 𝑖 ← 𝑗 βˆ’ 1 to 1 do 3 if (𝑙𝑏(π‘Œ )[𝑖 βˆ’ 1] < π‘ˆ 𝐡 𝑗 ) 4 sendMsg : back to 𝐴 𝑖 (π‘Œ 𝑖 , π‘ˆ 𝐡 𝑗 , 𝐷𝑉 π‘Žπ‘™π‘ , 𝐢 πœ‘ ) ; return ; 5 broadcastMsg : stp(π‘ˆ 𝐡 𝑗 ) ; 6 𝑒𝑛𝑑 ← π‘‘π‘Ÿπ‘’π‘’ ; 7 else 8
Taking dcop to the real world: Efficient complete solutions for distributed multi-event scheduling RTMaheswaran MTambe EBowring JPPearce PVarakantham Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 1 the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 1 IEEE Computer Society 2004 Asynchronous forward bounding for distributed cops AGershman AMeisels RZivan Journal of Artificial Intelligence Research 34 2009 Adopt: Asynchronous distributed constraint optimization with quality guarantees PJModi W.-MShen MTambe MYokoo Artificial Intelligence 161 2005 Bnb-adopt: An asynchronous branch-and-bound dcop algorithm WYeoh AFelner SKoenig Journal of Artificial Intelligence Research 38 2010 Saving messages in adopt-based algorithms PGutierrez PMeseguer Proc. 12th DCR workshop in AAMAS-10 12th DCR workshop in AAMAS-10 Citeseer 2010 Improving bnb-adopt+-ac PGutierrez PMeseguer Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, International Foundation for Autonomous Agents and Multiagent Systems the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, International Foundation for Autonomous Agents and Multiagent Systems 2012 Distributed partial constraint satisfaction problem KHirayama MYokoo International Conference on Principles and Practice of Constraint Programming Springer 1997 Asynchronous forward bounding revisited MWahbi REzzahir CBessiere International Conference on Principles and Practice of Constraint Programming Springer 2013 Connecting afb_bj + with soft arc consistency RAdrdor REzzahir LKoutti International Journal of Computing and Optimization 5 1 2018 Enhancing AFB_BJ + AC * algorithm RAdrdor LKoutti 2019 International Conference of Computer Science and Renewable Energies (ICCSRE), IEEE 2019 Consistance d'arc souple appliquée aux problèmes dcop RAdrdor REzzahir LKoutti Journées d'Intelligence Artificielle Fondamentale 63 2020 Privacy preserving region optimal algorithms for symmetric and asymmetric dcops TGrinshpoun TTassa VLevit RZivan Artificial Intelligence 266 2019 Distributed constraint optimization problems and applications: A survey FFioretto EPontelli WYeoh Journal of Artificial Intelligence Research 61 2018 Distributed gibbs: A linear-space samplingbased dcop algorithm DTNguyen WYeoh HCLau RZivan Journal of Artificial Intelligence Research 64 2019 In the quest of the best form of local consistency for weighted csp JLarrosa TSchiex IJCAI 3 2003 Soft arc consistency revisited MCCooper SDe Givry MSÑnchez TSchiex MZytnicki TWerner Artificial Intelligence 174 2010 Preprocessing techniques for accelerating the dcop algorithm adopt SAli SKoenig MTambe Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems the fourth international joint conference on Autonomous agents and multiagent systems ACM 2005 Sensor networks and distributed csp: communication, computation and complexity RBéjar CDomshlak CFernÑndez CGomes BKrishnamachari BSelman MValls Artificial Intelligence 161 2005