Generalizing ADOPT and BnB-ADOPT

1 Introduction

Distributed Constraint Optimization Problems (DCOPs) [Modi et al., 2005; Petcu and Faltings, 2005] are well-suited for modeling multi-agent coordination problems where interactions are primarily between subsets of agents, such as meeting scheduling [Maheswaran et al., 2004], sensor network [Farinelli et al., 2008] and coalition structure generation [Ueda et al., 2010] problems. DCOPs involve a finite number of agents, variables and binary cost functions. The cost of an assignment of a subset of variables is the evaluation of all cost functions on that assignment. The goal is to find a complete assignment with minimal cost. Researchers have proposed several distributed search algorithms to solve DCOPs optimally. They include ADOPT [Modi et al., 2005], which uses best-first search, and BnB-ADOPT [Yeoh et al., 2010], which uses depth-first branch-and-bound search.

We present a new algorithm, called ADOPT(k), that generalizes ADOPT and BnB-ADOPT. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnBADOPT when k = ∞ and like a hybrid of ADOPT and BnBADOPT when 1 < k < ∞. The main difference between ADOPT(k) and its predecessors is the condition by which an agent changes its value. While an agent in ADOPT changes its value when another value is more promising by at least 1 unit, an agent in ADOPT(k) changes its value when another value is more promising by at least k units. When k = ∞, like agents in BnB-ADOPT, an agent in ADOPT(k) changes its value when the optimal solution for that value is provably no better than the best solution found so far. We prove that ADOPT(k) is correct and complete and experimentally show that ADOPT(k) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.

2 Preliminaries

In this section, we formally define DCOPs and summarize ADOPT and BnB-ADOPT.

2.1 DCOP

A DCOP is defined by 〈X,D,F,A,α〉, where X = {x1 , . . . , xn} is a set of variables; D = {D1 , . . . ,Dn} is a set of finite domains, where Di is the domain of variable xi; F is a set of binary cost functions, where each cost function Fij : Di×Dj ↦→ N∪{0,∞} specifies the cost of each combination of values of variables xi and xj ; A = {a1 , . . . , ap} is a set of agents and α : X → A maps each variable to one agent. We assume that each agent has only one variable mapped to it, and we thus use the terms variable and agent interchangeably. The cost of an assignment of a subset of variables is the evaluation of all cost functions on that assignment. Agents communicate through messages, which are never lost and delivered in the order that they were sent.

A constraint graph visualizes a DCOP instance, where nodes in the graph correspond to variables and edges connect pairs of variables appearing in the same cost function. A depth-first search (DFS) pseudo-tree arrangement has the same nodes and edges as the constraint graph and satisfies that (i) there is a subset of edges, called tree edges, that form a rooted tree and (ii) two variables in a cost function appear in the same branch of that tree. The other edges are called backedges. Tree edges connect parent-child nodes, while backedges connect a node with its pseudo-parents and its pseudo-children. DFS pseudo-trees can be constructed using distributed DFS algorithms [Hamadi et al., 1998].

2.2 ADOPT

ADOPT [Modi et al., 2005] is a distributed search algorithm that solves DCOPs optimally. ADOPT first constructs a DFS pseudo-tree, after which each agent knows its parent, pseudoparents, children and pseudo-children. Each agent xi maintains: its current value di; its current context Xi, which is its assumption on the current value of its ancestors; the lower and upper bounds LBi and UBi, which are bounds on the optimal cost OPTi given that its ancestors take on their respective values in Xi; the lower and upper bounds LBi(d) and UBi(d) for all values d ∈ Di, which are bounds on the optimal costs OPTi(d) given that xi takes on the value d and its ancestors take on their respective values in Xi; the lower and upper bounds lbci (d) and ubci (d) for all values d ∈ Di and children xc, which are its assumption on the bounds LBc and UBc of its children xc with context Xi ∪ (xi, d); and the thresholds THi and thci (d) for all values d ∈ Di and children xc, which are used to speed up the solution reconstruction process. The optimal costs are calculated using:

for all values d ∈ Di, where Ci is the set of children of agent xi and δi(d) is the sum of the costs of all cost functions between xi and its ancestors given that xi takes on the value d and the ancestors take on their respective values in Xi.

ADOPT agents use four types of messages: VALUE, COST, THRESHOLD and TERMINATE. At the start, each agent xi initializes its current context Xi to ∅, lower and upper bounds lbci (d) and ubci (d) to user-provided heuristic values hci (d) and ∞, respectively. For all values d ∈ Di and all children xc, xi calculates the remaining lower and upper bounds and takes on its best value using:

xi sends a VALUE message containing its value di to its children and pseudo-children. It also sends a COST message containing its context Xi and its bounds LBi and UBi to its parent. Upon receipt of a VALUE message, if its current context Xi is compatible with the value in the VALUE message, it updates its context to reflect the new value of its ancestor and reinitializes its lower and upper bounds lbci (d) and ubci (d). Contexts are compatible iff they agree on common agentvalue pairs. Upon receipt of a COST message from child xc, if its current context Xi is compatible with the context in the message, then it updates its lower and upper bounds lbci (d) and ubci (d) to the lower and upper bounds in the message, respectively. Otherwise, the COST message is discarded. After processing either message, it recalculates the remaining lower and upper bounds and takes on its best value using the above equations and sends VALUE and COST messages. This process repeats until the root agent xr reaches the termination condition LBr = UBr, which means that it has found the optimal cost. It then sends a TERMINATE message to each of its children and terminate. Upon receipt of a TERMINATE message, each agent does the same.

Due to memory limitations, each agent xi can only store lower and upper bounds for one context. Thus, it reinitializes its bounds each time the context changes. If its context changes back to a previous one, it has to update its bounds from scratch. ADOPT optimizes this process by having the parent of xi send xi the lower bound computed earlier as threshold THi in a THRESHOLD message. This optimization changes the condition for which an agent changes its value. Each agent xi now changes its value di only when LBi(di) ≥ THi.

2.3 BnB-ADOPT

BnB-ADOPT [Yeoh et al., 2010] shares most of the data structures and messages of ADOPT. The main difference is their search strategies. ADOPT employs a best-first search strategy while BnB-ADOPT employs a depth-first branchand-bound search strategy. This difference in search strategies is reflected by how the agents change their values. While each agent xi in ADOPT eagerly takes on the value that minimizes its lower bound LBi(d), each agent xi in BnB-ADOPT changes its value only when it is able to determine that the optimal solution for that value is provably no better than the best solution found so far for its current context. In other words, when LB(di) ≥ UBi for its current value di.

The role of thresholds in the two algorithms is also different. As described earlier, each agent in ADOPT uses thresholds to store the lower bound previously computed for its current context such that it can reconstruct the partial solution more efficiently. On the other hand, each agent in BnBADOPT uses thresholds to store the cost of the best solution found so far for all contexts and uses them to change its values more efficiently. Therefore, each agent xi now changes its value di only when LBi(di) ≥ min{THi, UBi}.

BnB-ADOPT also has several optimizations that can be applied to ADOPT: (1) Agents in BnB-ADOPT processes messages differently compared to agents in ADOPT. Each agent in ADOPT updates its lower and upper bounds and takes on a new value, if necessary, after each message that it receives. On the other hand, each agent in BnB-ADOPT does so only after it processes all its messages. (2) BnB-ADOPT includes thresholds in VALUE messages such that THRESHOLD messages are no longer required. (3) BnB-ADOPT includes a time stamp for each value in contexts such that their recency can be compared. 1

Researchers recently observed that some of the messages in BnB-ADOPT are redundant and thus introduced BnBADOPT+, an extension of BnB-ADOPT without most of the redundant messages [Gutierrez and Meseguer, 2010b]. BnBADOPT+ is shown to outperform BnB-ADOPT in a variety of metrics, especially in the number of messages sent. Researchers have also applied the same message reduction techniques to extend ADOPT to ADOPT+ [Gutierrez and Meseguer, 2010a]. However, it is not as competitive since ADOPT has fewer redundant messages than BnB-ADOPT.

3 ADOPT(k)

Each agent in ADOPT always changes its value to the most promising value. This strategy requires the agent to repeatedly reconstruct partial solutions that it previously found, which can be computationally inefficient. On the other hand, each agent in BnB-ADOPT changes its value only when the optimal solution for that value is provably no better than the best solution found so far, which can be computationally inefficient if the agent takes on bad values before good values. Therefore, we believe that there should be a good trade off between the two extremes, where an agent keeps its value longer than it otherwise would as an ADOPT agent and shorter than it otherwise would as a BnB-ADOPT agent.

1 The first two optimizations were in the implementation of ADOPT [Yin, 2008] but not in the publication [Modi et al., 2005].

With this idea in mind, we developed ADOPT(k), which generalizes ADOPT and BnB-ADOPT. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < ∞. ADOPT(k) uses mostly identical data structures and messages as ADOPT and BnB-ADOPT. Each agent xi in ADOPT(k) maintains two thresholds, THAi and THBi , which are the thresholds in ADOPT and BnB-ADOPT, respectively. They are initialized and updated in the same way as in ADOPT and BnB-ADOPT, respectively.

The main difference between ADOPT(k) and its predecessors is the condition by which an agent changes its value. Each agent xi in ADOPT(k) changes its value di when LBi(di) > THAi + (k -1) or LBi(di) ≥min{THBi ,UBi}. If k = 1, then the first condition degenerates to LBi(di) > THAi , which is the condition for agents in ADOPT. The agents use the second condition, which remains unchanged, to determine if the optimal solution for their current value is provably no better than the best solution found so far. If k = ∞, then the first condition is always false and the second condition, which remains unchanged, is the condition for agents in BnBADOPT. If 1 < k < ∞, then each agent in ADOPT(k) keeps its current value until the lower bound of that value is at least k units larger than the lower bound of the most promising value, at which point it takes on the most promising value.

3.1 Pseudocode

Figures 1 and 2 show the pseudocode of ADOPT(k), where xi is a generic agent, Ci is its set of children, PCi is its set of pseudo-children and SCPi is the set of agents that are either ancestors of xi or parent and pseudo-parents of either xi or its descendants. The pseudocode uses the predicate Compatible(X,X′ ) to determine if two contexts X and X′ are compatible and the procedure PriorityMerge(X,X′ ) to replace the values of agents in context X′ with more recent values, if available, of the same agents in context X (see [Yeoh et al., 2010] for more details). The pseudocode is similar to ADOPT's pseudocode with the following changes:

• The pseudocode includes the optimizations described in Section 2.3 that was presented for BnB-ADOPT but can be applied to ADOPT (Lines 03, 08-12, 35-36 and 40-41).
• In ADOPT, the MaintainThresholdInvariant(), MaintainChildThresholdInvariant() and MaintainAllocationInvariant() procedures are called after each message is processed. Here, they are called in the Backtrack() procedure (Lines 28 and 38-39). The invariants are maintained only after all incoming messages are processed.
• In addition to THAi , each agent maintains THBi . It is ini-

01 procedure Start() 02 Xi := {(xp, ValInit(xp), 0) | xp ∈ SCPi}; 03 IDi := 0; 04 forall xc ∈ Ci and d ∈ Di InitChild(xc, d); 05 InitSelf(); 06 Backtrack(); 07 loop forever 08 if (message queue is not empty) 09 while (message queue is not empty) 10 pop msg off message queue; 11 When Received(msg); 12 Backtrack(); 13 procedure InitChild(xc, d) 14 lbci (d) := hci (d); 15 ubci (d) :=∞; 16 thci (d) := lbci (d); 17 procedure InitSelf() 18 di := argmind∈Di {δi(d) + ∑xc∈Ci lbci (d)}; 19 IDi := IDi + 1; 20 THAi := mind∈Di {δi(d) + ∑xc∈Ci lbci (d)}; 21 THBi :=∞; 22 procedure Backtrack() 23 forall d ∈ Di 24 LBi(d) := δi(d) + ∑xc∈Ci lbci (d); 25 UBi(d) := δi(d) + ∑xc∈Ci ubci (d); 26 LBi := mind∈Di {LBi(d)}; 27 UBi := mind∈Di {UBi(d)}; 28 MaintainThresholdInvariant(); 29 if (THAi = UBi) 30 di := argmind∈Di {UBi(d)} 31 else if (LBi(di) > THAi + (k - 1)) 32 di := argmind∈Di|LBi(d)=LBi {UBi(d)} 33 else if (LBi(di) ≥ min{THBi , UBi}) 34 di := argmind∈Di|LBi(d)=LBi {UBi(d)} 35 if (a new di has been chosen) 36 IDi := IDi + 1; 37 MaintainCurrentValueThresholdInvariant(); 38 MaintainChildThresholdInvariant(); 39 MaintainAllocationInvariant(); 40 Send(VALUE, xi, di, IDi, thci (di), min(THBi , UBi) - δi(di) - ∑xc′∈Ci|xc′ ̸=xc lbc′ i (di)) to each xc ∈ Ci; 41 Send(VALUE, xi, di, IDi, ∞, ∞) to each xc ∈ PCi; 42 if (THAi = UBi) 43 if (xi is root or termination message received) 44 Send(TERMINATE) to each xc ∈ Ci; 45 terminate execution; 46 Send(COST, xi, Xi, LBi, UBi) to parent; 47 procedureWhen Received(TERMINATE) 48 record termination message received; 49 procedureWhen Received(VALUE, xp, dp, IDp, THAp , THBp ) 50 X′ := Xi ; 51 PriorityMerge((xp, dp, IDp), Xi); 52 if (!Compatible(X′ , Xi)) 53 forall xc ∈ Ci and d ∈ Di 54 if (xp ∈ SCPc) 55 InitChild(xc, d); 56 InitSelf(); 57 if (xp is parent) 58 THAi := THAp ; 59 THBi := THBp ; 60 procedureWhen Received(COST, xc, Xc, LBc, UBc) 61 X′ := Xi ; 62 PriorityMerge(Xc, Xi); 63 if (!Compatible(X′ , Xi)) 64 forall xc ∈ Ci and d ∈ Di 65 if (!Compatible({(xp, dp, IDp) ∈ X′ | xp ∈ SCPc},Xi)) 66 InitChild(xc, d); 67 if (Compatible(Xc, Xi)) 68 lbci (d) := max{lbci (d), LBc} for the unique (a′ , d, ID) ∈ Xc with a′ = a; 69 ubci (d) := min{ubci (d), UBc} for the unique (a′ , d, ID) ∈ Xc with a′ = a; 70 if (!Compatible(X′ , Xi)) 71 InitSelf();

Figure 2: Pseudocode of ADOPT(k) (2)

tialized, propagated and used in the same way as in BnBADOPT (Lines 21, 33-34, 40 and 59).

• The condition by which each agent xi changes its value is now LBi(di) > THAi + (k - 1) or LBi(di) ≥ min{THBi ,UBi} (Lines 31 and 33). Thus, the agent keeps its value until the lower bound of that value is k units larger than the lower bound of the most promising value or the optimal solution for that value is provably no better than the best solution found so far.
• InADOPT, theMaintainAllocationInvariant() procedure ensures that the invariant THAi = ∑xc∈Ci THAc always hold. This procedure assumes that THAi ≥ LBi(di) for the current value di of agent xi, which is always true since the agent would change its value otherwise. However, this assumption is no longer true in ADOPT(k). Therefore, the pseudocode includes a new threshold THAi (di), which is set to THAi and updated such that it satisfies the invariant LBi(di) ≤ THAi (di) ≤ UBi(di) in the MaintainCurrentValueThresholdInvariant() procedure (Lines 84-89). This new threshold then replaces THAi in the MaintainAllocationInvariant() procedure (Lines 91 and 93).

3.2 Correctness and Completeness

The proofs for the following lemmata and theorem closely follow those in [Modi et al., 2005; Yeoh et al., 2010]. We thus only provide proof sketches.

Lemma 1 For all agents xi and all values d ∈ Di, LBi ≤ OPTi ≤ UBi and LBi(d) ≤ OPTi(d) ≤ UBi(d) at all times.

Proof sketch: We prove the lemma by induction on the depth of the agent in the pseudo-tree. It is clear that for each leaf agent xi, LBi(d) = OPTi(d) = UBi(d) for all values d ∈ Di (Lines 24-25 and Eq. 1). Furthermore,

So, the lemma holds for each leaf agent. Assume that it holds for all agents at depth q in the pseudo-tree. For all agents xi at depth q1,

for all values d ∈ Di. The proof for LBi ≤ OPTi ≤ UBi is similar to the proof for the base case. Thus, the lemma holds.

Lemma 2 For all agents xi, if the current context of xi is fixed, then LBi = THAi = UBi will eventually occur.

Proof sketch: We prove the lemma by induction on the depth of the agent in the pseudo-tree. The lemma holds for leaf agents xi since LBi = UBi (see proof for the base case of Lemma 1) and LBi ≤ THAi ≤ UBi (lines 79-83). Assume that the lemma holds for all agents at depth q in the pseudo-tree. For all agents xi at depth q - 1,

Additionally, LBi ≤ THAi ≤ UBi (Lines 79-83). Therefore, LBi = THAi = UBi.

Lemma 3 For all agents xi, THAi (d) = THAi on termination. Proof sketch: Each agent xi terminates when THAi = UBi (Line 42).

After THAi (di) is set to THAi for the current value di of xi (Line 85) in the last execution of the MaintainCurrentValueThresholdInvariant() procedure,

Thus, LBi(di) ≤ THAi = UBi and THAi (di) is not set to a different value later (Lines 86-89). Then, THAi (d) = THAi on termination.

Proof sketch: We prove the theorem by induction on the depth of the agent in the pseudo-tree. The theorem holds for the root agent xi since THAi = UBi on termination (Lines 42-45), THAi = LBi at all times (Lines 20 and 28), and LBi ≤ OPTi ≤ UBi (Lemma 1). Assume that the theorem holds for all agents at depth q in the pseudotree. We now prove that the theorem holds for all agents at depth q +1. Let xp be an arbitrary agent at depth q in the pseudo-tree and dp is its current value on termination. Then,

Thus, ∑xc∈Cp ubcp(dp) = ∑xc∈Cp thcp(dp). Furthermore, for all agents xc ∈ Cp, thcp(dp) ≤ ubcp(dp) (Lines 77-78). Combining the inequalities, we get thcp(dp) = ubcp(dp). Additionally, THAc = thcp(dp) (Lines 57-58) and UBc = ubcp(dp) (Line 69). Therefore, THAc = UBc. Next,

Thus, ∑xc∈Cp OPTc = ∑xc∈Cp THAc = ∑xc∈Cp UBc (see above). Furthermore, for all agents xc ∈ Cp, OPTc ≤ UBc (Lemma 1). Combining the inequalities, we get OPTc = UBc. Therefore, THAc = UBc = OPTc.

4 Experimental Results

We compare ADOPT+(k) to ADOPT+ and BnB-ADOPT+. ADOPT+(k) is an optimized version of ADOPT(k) with the message reduction techniques used by ADOPT+ and BnBADOPT+. All the algorithms use the DP2 heuristic values [Ali et al., 2005]. We measure runtimes in (synchronous) cycles [Modi et al., 2005] and non-concurrent constraint checks (NCCCs) [Meisels et al., 2002], and we measure the network load in the number of VALUE and COST messages sent. 2 We do not report the number of TERMINATE messages sent because every algorithm sends the same number, namely |X| - 1. Also, we report the trivial upper bound UB as the sum of the maximums over cost functions. Table 1 shows the results. Due to space constraints, we omit ADOPT+ in Tables 1(a) and 1(b) since BnB-ADOPT+ performs better than ADOPT+ across all metrics.

2 We differentiate them because the size of VALUE messages is O(1) and the size of COST messages is O(|X |).

Table 1(a) shows the results on random binary DCOP instances with 10 variables of domain size 10. The costs are randomly chosen over the range 〈1000, . . . , 2000〉. We impose n(n - 1)/2 ∗ p1 cost functions, where n is the number of variables and p1 is the network connectivity. We vary p1 from 0.5 to 0.8 in 0.1 increments and average our results over 50 instances for each value of p1. The table shows that ADOPT+(k) requires a large number of messages, cycles and NCCCs when k is small. These numbers decrease as k increases until a certain point where they increase again. For the best value of k, ADOPT+(k) performs significantly better than BnB-ADOPT+ across all metrics.

Table 1(b) shows the results on sensor network instances from a publicly available repository [Yin, 2008]. We use instances from all four available topologies and average our results over 30 instances for each topology. We observe the same trend as in Table 1(a) but only report the results for the best value of k due to space constraints.

Lastly, Table 1(c) shows the results on sensor network instances of 100 variables arranged into a chain following the [Maheswaran et al., 2004] formulation. All the variables have a domain size of 10. The cost of hard constraints is 1,000,000. The cost of soft constraints is randomly chosen over the range 〈0, . . . , 200〉. Additionally, we use discounted heuristic values, which we obtain by dividing the DP2 heuristic values by two, to simulate problems where well informed heuristics are not available due to privacy reasons. We average our results over 30 instances. The table shows that ADOPT+ terminates earlier than BnB-ADOPT+ but sends more messages. When k = 1, the results for ADOPT+(k) and ADOPT+ are almoust the same. Agents in ADOPT+(k) sends more VALUE messages because they need to send VALUE messages when THBp changes even if THAp remains unchanged. These additional messages then trigger the need for more constraint checks. Agents in ADOPT+ do not need to send VALUE messages in such a case. We observe that as k increases, the runtime of ADOPT+(k) increases but the number of messages sent decreases. Therefore, ADOPT+(k) provides a good mechanism for balancing the tradeoff between runtime and network load.

5 Conclusions

We introduced ADOPT(k), which generalizes ADOPT and BnB-ADOPT. The behavior of ADOPT(k) depends on the parameter k. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of the two algorithms when 1 < k < ∞. Our experimental results show that ADOPT(k) can outperform ADOPT and BnBADOPT in terms of runtime and network load on random DCOP instances and sensor network instances. Additionally, ADOPT(k) provides a good mechanism for balancing the tradeoff between runtime and network load. It is future work to better understand the characteristics of ADOPT(k) such that the best value of k can be chosen automatically.

Table 1: The number of messages, cycles and NCCCs of ADOPT+, BnB-ADOPT+ and ADOPT+(k) on several benchmarks.

Acknowledgments

Patricia Gutierrez has an FPI scholarship BES-2008-006653. She and Pedro Meseguer are partially supported by the Spanish project TIN-2009-13591-C02-02.