Speeding Up Incomplete GDL-based Algorithms for Multi-agent Optimization with Dense Local Utilities

1 Introduction

Distributed Constraint Optimization Problems (DCOPs) [Modi et al., 2005; Fioretto et al., 2018] are a fundamental model for multi-agent optimization and coordination, in which agents cooperatively find assignments to optimize a global objective. DCOPs have been successfully applied to model many real-world problems where information and controls are inherently distributed among agents such as distributed scheduling [Hirayama et al., 2019; Li et al., 2016], smart-grids [Fioretto et al., 2017] and radio frequency allocation [Monteiro et al., 2012].

Complete algorithms for DCOPs [Hirayama and Yokoo, 1997; Petcu and Faltings, 2005; Modi et al., 2005; Yeoh et al., 2010; Netzer et al., 2012; Litov and Meisels, 2017] aim to find the optimal solution but incur exponential coordination overheads since solving DCOPs is NP-Hard. In contrast, incomplete algorithms [Maheswaran et al., 2004; Zhang et al., 2005; Okamoto et al., 2016; Ottens et al., 2017; Hoang et al., 2018; Nguyen et al., 2019] trade the solution quality for smaller computational efforts and can scale up to large problems.

Max-sum and its variants [Farinelli et al., 2008; Rogers et al., 2011; Zivan et al., 2017; Chen et al., 2018] are popular incomplete algorithms built upon the Generalized Distributive Law (GDL) [Aji and McEliece, 2000] and have been applied to many real-world domains due to their ability of directly handling n-ary constraints. However, these algorithms face a significant scalability challenge. Inmore detail, Max-sum implements belief propagation on a factor graph [Kschischang et al., 2001] by optimizing the sum of local utility functions and corresponding query messages. As a result, the computational effort grows exponentially with respect to the arity of each utility function, which prohibits Max-sum from scaling up to large systems.

Therefore, a number of acceleration algorithms for GDLbased algorithms were proposed to improve their scalability and can be generally divided into BnB-based and sortingbased algorithms. BnB-based algorithms including BnB-MS [Stranders et al., 2009] and BnB-FMS [Macarthur et al., 2011] construct an estimation for each partial assignment and employ branch-and-bound to reduce the search space. Nevertheless, these algorithms compute estimations by either bruteforce or domain-specific knowledge, which limits their generality. Recently, FDSP [Chen et al., 2019] was proposed to implement generic branch-and-bound by using dynamicprogramming to construct domain-agnostic estimations.

On the other hand, sorting-based algorithms including GFBP [Kim and Lesser, 2013] and GDP [Khan et al., 2018] require (partially) sorted local utilities to perform acceleration. Specifically, G-FBP only sorts for top cd n-1 2 values of the search space and presumes that the highest utility can be found in the range. Here, c is a constant, d is the maximal domain size and n is the arity of a utility function, respectively. However, the algorithm has to perform an exhaustive traverse when the assumption fails. In contrast, GDP constructs a completely sorted local utility list for each assignment of each variable. Then it uses the entry with the highest local utility to compute a one-shot lower bound to prune suboptimal entries.

However, the existing methods could perform poorly when dealing with dense local utilities. In more detail, FDSP would not be able to find a high-quality lower bound promptly when utility functions are highly structured since it sequentially exhausts the whole search space. On the other hand, although GDP attempts to find a more efficient one by considering the local utilities, the one-shot nature still cannot guarantee the quality. Additionally, the pruned range returned by GDP would contain many entries whose local utilities are close to each other, which also results in a poorly pruned rate. Unfortunately, dense utility functions and ties are very common in real-world scenarios. For example, in a NetRad system [Kim et al., 2011] the utility of scanning a weather phenomenon does not increase linearly w.r.t. the scanning quality. As a result, the utility function could be extremely dense when the scanning quality is high.

In this paper, we aim to cope with dense local utilities from the perspectives of both bound quality and search space organization and develop more efficient sorting-based acceleration algorithms. To ensure bound quality, we integrate both search and pruning by iteratively updating the lower bound. Then we overcome the inability of pruning tied entries in domain pruning techniques by organizing the search space of these entries into AND/OR trees to enable efficient branchand-bound. Finally, we discretize the utility range to balance the reconstruction overhead and the pruning efficiency and to further reduce the sorting overhead. We theoretically show our algorithms are sound and outperform GDP in terms of pruning efficiency. Our extensive empirical evaluations also confirm the great superiorities over the state-of-the-art.

2 Backgrounds

In this section, we review preliminaries including DCOPs, Max-sum and GDP.

2.1 Distributed Constraint Optimization Problems

A Distributed Constraint Optimization Problem (DCOP) [Modi et al., 2005] can be defined by a tuple 〈A,X,D, F〉 where A = {a1, . . . , ap} is the set of agents, X = {x1, . . . , xq} is the set of variables, D = {D1, . . . ,Dq} is the set of discrete domains and F = {f1, . . . , fm} is the set of utility functions. Each variable xi takes a value from domain Di and each function fj : xj → R≥0 specifies a utility for each possible combination of involved variables xj ⊆ X. For the sake of simplicity, we assume that each agent controls a variable (i.e., p = q). The objective of a DCOP is to find an assignment for each variable to maximize the global utility. That is,

2.2 Max-sum

Max-sum [Farinelli et al., 2008] is a GDL-based messagepassing incomplete algorithm for DCOPs operating on a factor graph. A factor graph [Kschischang et al., 2001] is a bipartite graph representation to a DCOP, which consists of variable nodes representing variables and function nodes representing utility functions in the DCOP, respectively. Fig.1

presents a factor graph consisting of 3 function nodes and 5 variable nodes.

Max-sum implements belief propagation via query messages and response messages. Formally, the query message from variable node xi ∈ xj to function node fj is given by

where Nxi is neighboring function nodes of xi, rfk→xi (xi) is the response message from fk and α is a normalization term to control the magnitude of each entry in the message. The response message from function node fj to variable node xi ∈ xj is given by

A variable node xi makes a decision by choosing the assignment with the highest utility under the current belief. That is,

2.3 Generic Domain Pruning

It can be concluded that the computational overhead of Eq.(2) is exponential in the arity of utility function fj, which prohibits Max-sum from scaling up to large systems. Generic Domain Pruning (GDP) [Khan et al., 2018] is the state-ofthe-art acceleration algorithm operating on completely sorted utility functions. In more detail, for each variable xi ∈ xj and assignment vi ∈ Di, fj computes an ordered list SortedEntriesi(vi) according to its local utilities, where each entry e ∈ SortedEntriesi(vi) is an assignment to xj such that xi = vi. When computing the utility for xi = vi, fj constructs a one-shot lower bound lb and the message upper bound msgUB. That is,

• (b) The traces of GDP when computing for x1 = R

Figure 3: The traces of GDP when applied to the example in Fig.2

where e0 is the first element in SortedEntriesi(vi) and e0[xk] is the assignment of xk in entry e0. Then fj returns a pruned range P ⊆ SortedEntriesi(vi) such that fj (e) + msgUB ≥ lb, ∀e ∈ P .

3 Motivation

In this section, we show GDP could fail to reduce the search space when there exist dense local utilities. Consider a part of a NetRad system [Kim et al., 2011] shown in the lefthand side of Fig.2. There are four radars and a weather phenomenon P. For the sake of simplicity, we assume that each radar can only scan one of two sectors (i.e., {L, R} for x1 and x3, {U,D} for x2 and x4). The utility for a radar xi scanning P depends on the distance between xi and P. Assume that the utilities for scanning P by individual radars are 0.9, 0.6, 0.4 and 0.8, respectively. Finally, we consider the task as nonpinpointing. That is, given the scanning strategies of radars, the aggregated utility is the maximal one among the individual radars that scan P.

Given the incoming query messages shown in the righthand side of Fig.2, we are going to compute the response message for radar x1. It can be concluded from Fig.3 that GDP could perform poorly due to dense local utilities and ties. More specifically, when computing the utility for x1 = L, the one-shot lower bound is 1.5 and the message upper bound is 1.1. As a result, any entry with local utility less than 0.4 is filtered out. However, since the local utilities are densely distributed in the range of [0.4, 0.8], GDP can only prune one entry and result in a poorly pruned rate of 12.5%.

The pathology could be exacerbated when computing for x1 = R where all the local utilities are the same. In this case GDP still cannot prune any entry even if we construct the most efficient lower bound according to {R,U,R,D}. That is because given a linearly structured search space GDP cannot discard suboptimal entries with the same local utility in advance.

In fact, dense local utilities are ubiquitous in real-world scenarios due to the law of diminishing marginal utility. Therefore, we aim to develop more efficient sorting-based acceleration algorithms for incomplete GDL-based algorithms by alleviating the negative effect of dense local utilities.

4 ProposedMethods

In this section, we first present our proposed algorithms for accelerating Max-sum. Then we briefly discuss the modifications when applying our methods to other versions of belief propagation.

4.1 GD2P

As demonstrated earlier, the quality of the lower bound is the key of effective pruning, especially when local utilities are dense. Therefore, we propose to integrate both search and pruning to iteratively reduce the search space. Thus, the pruning is no longer a one-shot procedure and the scheme is referred as Generic Dynamic Domain Pruning (GD2P). Alg.1 presents the sketch of GD2P.

Similar to GDP, GD2P also begins with complete sorting of each utility function (line 1-3). When computing a response message for a variable node xi ∈ xj, it searches for the highest utility for each assignment vi ∈ Di by exhausting the sorted entries whose local utility is no less than the running lower bound lb in a sequential order (line 8-13). Here, the lower bound is updated whenever a higher utility is found (line 10-11).

Next, we theoretically show its correctness and superiority over GDP.

Theorem 1. GD2P guarantees the optimality of Eq.(2).

Proof. Assume that the optimal entry e∗ is pruned by GD2P when xi = vi. According to line 4, 8 and 11 of Alg.1, we have

where util∗ is the highest utility returned by GD2P. Combing with query messages, we have

it must have

which is contradictory to the assumption. Thus, GD2P guarantees the optimality of Eq.(2).

Theorem 2. GD2P never explores the entries pruned by GDP.

Proof. Assume that GD2P explores an entry e which is pruned by GDP. Denote the lower bound constructed by GDP as lbGDP and the running lower bound in GD2P as lbGD2P . According to line 8 of Alg.1, since e is explored by GD2P but pruned by GDP, it must have

which is contradictory to line 10-11.

4.2 ART-GD2P

Both GDP and GD2P perform poorly when there are ties in utility functions since they use a linear structure to organize the search space. As a result, they have to exhaust all the tied entries whose local utility is no less than the lower bound. Thus, we propose to organize the search space of tied entries into an AND/OR tree so as to enable branch-andbound to reduce the search space. The scheme is referred as And/oR Tree-based GD2P (ART-GD2P) and Alg.2 presents the sketch.

Different than completely sorting a utility function in GDP and GD2P, ART-GD2P only sorts for distinct local utilities for each assignment of each variable in the preprocessing phase (line 1-4). After that, it builds an AND/OR tree for the entries with the same local utility (line 5-6). Note that the construction of AND/OR trees can be done by a sequential iteration over the utility function as the trees can be built incrementally. Similar to GD2P, it maintains a running lower bound lb and terminates whenever the local utility is less than the lower bound (line 11-16).

It is noteworthy that instead of iterating over the sorted entries in GDP and GD2P, ART-GD2P iterates over the distinct sorted utilities and performs branch-and-bound to reduce the search space of tied entries. In more detail, for each distinct local utility u, ART-GD2P exhausts the corresponding AND/OR tree treei(vi, u) by constructing an estimation ubPA for each partial assignment PA and discarding the partial assignment whenever the estimation is less than the known highest utility (line 12-13). Formally, the estimation is given by

Take Fig.2 as an example. Given x1 = L, ART-GD2P first sorts distinct local utilities {0.8, 0.6, 0.4, 0} and builds an AND/OR tree for each of them. Fig.4 presents the AND/OR trees. Here, we omit the AND/OR nodes for x1. When computing utility for x1 = L, ART-GD2P first performs depth-first branch-and-bound to exhaust the AND/OR tree tree1(L, 0.8). It can be concluded that the algorithm terminates after reaching the first two complete assignments {L, U, L, D} and {L, U, R, D} since it finds the highest utility 1.9, which results in a pruned rate of 75%.

We now show its correctness and its superiority over GD2P. Theorem 3. ART-GD2P guarantees the optimality of Eq.(2).

Proof. There are two lines that prune the search space, i.e., line 11 and line 13 of Alg.2. We have shown that line 11 cannot prune the highest utility in Theorem 1. Thus we only need to show that line 13 never prunes the optimal assignment. Assume that the optimal full assignment A∗ is pruned by line 13. Thus it must exist a prefix PA ⊂ A∗ such that

where util∗ is the highest utility found by ART-GD2P. In fact,

is hereby guaranteed.

Theorem 4. ART-GD2P never explores the assignments pruned by GD2P.

Proof. Assume that ART-GD2P explores a full assignment A which is pruned by GD2P. Denote the lower bound of ARTGD2P when exploring A as lbART and the lower bound of GD2P when pruning A as lbGD2P , respectively. It must have

Since GD2P sequentially exhausts the search space, it must exist an assignment A′ ≺ A such that

which indicates that fj(A′ ) > fj(A). On the other hand, ART-GD2P explores distinct local utilities in a descending order (line 4, 9 and 15 of Alg.2). According to Eqs.(3-4), A′ produces a higher utility than A. Thus, ART-GD2P must have explored an assignment A′′ such that

which implies

Therefore, Eq.(5) is contradictory to Eq.(3), which concludes the theorem.

4.3 DiscretizationMechanism

Since ART-GD2P builds an AND/OR tree for each distinct local utility, each tree would correspond to a small search space when the local utilities are extremely dense, which would incur solution reconstructions. Consider the example in Fig.5. Assume that all the assignments with prefix {F, T} are pruned by line 13 and the highest utility corresponds to assignment {F, F, F, F}. Obviously, ART-GD2P has to visit the suboptimal partial assignment {F, T} for 4 times in this case. Besides, a large number of distinct local utilities also result in a high sorting overhead.

We overcome the problems by introducing a discretization mechanism. That is, instead of sorting and building AND/OR trees for distinct local utilities directly, we first group the utilities into several discrete slots. Then all the operations are applied to these slots. In more detail, we first divide the range of the local utilities into disjoint slots by a step size of t. Then we group all the utilities {u|val(si) - t < u ≤ val(si)} into slot si ∈ S. Here, val(·) returns the maximal utilities in a slot, which is used to perform pruning in line 11.

Finally, it is worth mentioning that ART-GD2P with the discretization mechanism offers a tradeoff between domain pruning and reconstruction overhead. In more detail, a small t produces fine-grained slots and could prune the suboptimal utilities promptly (line 11). In contrast, a large t tends to build AND/OR trees corresponding to large search spaces, which reduces the reconstruction overhead.

4.4 Generalizing to Other GDL-based Algorithms

We note that our proposed algorithms can be easily adapted to the variants of Max-sum and other versions of belief propagation. For example, we could adapt our algorithms to speed up Max-product [Weiss and Freeman, 2001] by changing the summation operations to the product operations (i.e., line 4, 9 and 11 of Alg. 1, line 7, 13 and 15 of Alg. 2).

When combining with Max-sum variants like damped Max-sum [Cohen et al., 2020], bounded Max-sum [Rogers et al., 2011] and Max-sum AD [Zivan et al., 2017], our algorithms require few modifications since these variants still use Eq.(2) to compute response messages. However, there are variants which do not exactly follow Eq.(2). For example, a function node in Max-sum ADSSVP [Chen et al., 2018] needs to consider the assignments of some neighbors when computing the maximal utility. In this case, an additional verification procedure needs to be introduced to filter out the incompatible entries.

5 Experimental Evaluations

We empirically evaluate the performance of GDP, FDSP and our proposed algorithms when accelerating Max-sum on both random DCOPs and NetRad systems. The performance metrics we consider include pruned rate [Khan et al., 2018], concurrent speedup, which is the improvement of the number of concurrent basic operations over vanilla Max-sum, and runtime. Here, basic operations are the access to query messages. For each of the configuration, we generate 50 random instances and terminate algorithms after 250 iterations, reporting the averaged metrics and standard errors as the results and the confidence intervals, respectively.

5.1 Results on RandomDCOPs

We generate high arity and low arity factor graphs by uniformly selecting an arity for each function node from [2,5] and [5,8], respectively. Further, we generate large domain problems and small domain problems by uniformly selecting a domain size from [5,8] and [2,5] for each variable, respectively. Finally, we consider the factor graphs with the variable tightness [Chen et al., 2019] between 0.1 and 0.5 as sparse graphs and the ones with the variable tightness between 0.5 and 0.9 as dense graphs. The utilities of each function node are uniformly sampled from (0,1000). For ART-GD2P, we use an empirically tuned step size t = 50.

Fig.6 presents the results when solving sparse problems. It can be seen that FDSP performs worse than ART-GD2P. That is due to the fact that FDSP performs a depth-first search on a huge AND/OR tree without any a priori knowledge. On the other hand, our ART-GD2P performs branch-and-bound on a sorted array of AND/OR trees and can find an efficient lower bound more promptly, reducing about 95% - 99.9% of concurrent operations, which demonstrates great superiorities over the other competitors. Besides, our GD2P maintains a running lower bound and significantly improves the performance of GDP, which highlights the importance of tight lower bounds in domain pruning techniques.

Fig.7 presents the results when solving dense problems. Compared to the ones in sparse problems, the variable nodes in these problems are over-constrained due to high variable tightness. As a result, the query messages could be multimodal and the one-shot lower bound constructed by GDP is not necessarily efficient. Therefore, GDP performs poorly and is strictly dominated by other competitors. Besides, it is interesting to find that compared to the results on sparse problems, the gaps between GD2P and FDSP are widened. In addition to the multimodality of query messages, another reason for this is that FDSP performs a depth-first search on AND/OR trees, which significantly reduces solution reconstructions. Finally, combing both domain pruning and branch-and-bound techniques, our proposed ART-GD2P exhibits the best performance on all of the tasks, which demonstrates its merits on general n-ary DCOPs.

To examine the performance on the problems with dense local utilities, we consider the problems with 100 function nodes, low arity, large domain size and the variable tightness of 0.5. For each problem, there are a number of dense function nodes whose utilities are selected according to a powerlaw distribution. More specifically, the probability of selecting a utility u ∈ (0, 1000) is proportional to (1000 - u)-α.

In our experiments, we set α = 1.1. Fig.8 presents the performance comparison in terms of the pruned rate.

It can be seen that the performance of GDP decreases by near 20% w.r.t. growing dense function nodes, which indicates that GDP is sensitive to dense utility functions. That is due to the fact that the pruned range could contain many entries since the utilities are close to each other in dense utility functions. On the other hand, although GD2P also relies on domain pruning to reduce the search space, it is much more robust to the presence of dense function nodes due to the iteratively tighten lower bound. In fact, with the growing of dense function nodes its performance only drops by 4%. Finally, dense function nodes can hardly deteriorate the performance of ART-GD2P since it can still perform effective branch-and-bound according to the query messages when local utilities are not distinguishable.

5.2 Results on NetRad Systems

We consider the NetRad systems with 48 and 96 radars which are arranged into 6×8 and 8×12 grids, respectively. Weather phenomena with different sizes, weights and types are randomly generated across grids. Each phenomenon is associated with a utility function defined according to [Pepyne et al., 2007]. In this set of experiments, the maximal utility of a function is 1, the maximal arity is 4 and the domain size of a variable can go up to 15. Fig.9 gives the experimental results.

It can be concluded that GDP performs poorly and the runtime grows quickly w.r.t. the number of phenomena in both cases. In contrast, our proposed GD2P and ART-GD2P significantly outperform GDP, only requiring about a half and one-eighth of its runtimes, respectively. On the other hand, although FDSP outperforms domain pruning variants, it is still dominated by ART-GD2P. This is due to the fact that with the sorted AND/OR trees our proposed ART-GD2P can find a high-quality lower bound quickly despite of highly-structured utility functions. Finally, ART-GD2P with a large t reduces the runtimes in both preprocessing phase and pruning phase, which demonstrates the necessity of the discretization mechanism.

6 Conclusion

In this paper, we demonstrate that the presence of dense utility functions or utility ties would deteriorate the performance of GDP. To alleviate the negative effect of densely distributed local utilities, we propose to iteratively update the lower bound and organize the tied entries to AND/OR trees. Finally, we present a discretization mechanism which offers a tradeoff between the reconstruction overhead and pruning efficiency. We theoretically show their correctness and superiorities over GDP. Our empirical evaluations also demonstrate their effectiveness on both synthetic and realistic benchmarks.

We consider two lines of future work. First, ART-GD2P relies on an empirically tuned step size t and uninformed depthfirst search, which could be undesirable in real-world applications. Therefore, heuristics for determining t and mechanisms for improving pruning ability need to be further investigated. Second, we plan to extend our work to cope with changing utility functions in a dynamic environment.

Acknowledgements

This research is supported by Singapore National Research Foundation projects AISG-RP2019-0013, NSOE-TSS201901, and NTU.