Improving function filtering for computationally demanding DCOPs
Publication Type:
Conference PaperSource:
Workshop on Distributed Constraint Reasoning at IJCAI 2011, Barcelona, p.99-111 (2011)Abstract:
In this paper we focus on solving DCOPs in computationally demanding scenarios. GDL optimally solves DCOPs, but requires exponentially large cost functions, being impractical in such settings. Function filtering is a technique that reduces the size of cost functions. We improve the effectiveness of function filtering to reduce the amount of resources required to optimally solve DCOPs. As a result, we enlarge the range of problems solvable by algorithms employing function filtering.
Improving DPOP with Function Filtering
Publication Type:
Conference PaperSource:
International Conference Autonomous Agents and Multiagent Systems AAMAS-10, Toronto, Canada (2010)Keywords:
DCOP; function filteringAbstract:
DPOP is an algorithm for distributed constraint optimization which has, as main drawback, the exponential size of some of its messages.
%which uses a solving strategy similar to bucket elimination in the centralized case.
Recently, some algorithms for distributed cluster tree elimination have been proposed. They also suffer from exponential size messages. However, using the strategy of cost function filtering, in practice these algorithms obtain important reductions in maximum message size and total communication cost. In this paper, we explain the relation between DPOP and these algorithms, and show how cost function filtering can be combined with DPOP. We present experimental evidence of the benefits of this new approach.
Cluster Tree Elimination for Distributed Constraint Optimization with Quality Guarantees
Publication Type:
Journal ArticleSource:
Fundamenta Informaticae, IOS Press, Volume 102, Issue 3-4, p.263-286 (2010)Keywords:
DCOP; function filteringAbstract:
Some distributed constraint optimization algorithms use a linear number of messages in the number of agents, but of exponential size. This is often the main limitation for their practical applicability. Here we present some distributed algorithms for these problems when they are arranged in a tree of agents. The exact algorithm, DCTE, computes the optimal solution but requires messages of size $exp(s)$, where $s$ is a structural parameter. Its approximate version, DMCTE$(r)$, requires smaller messages of size $exp(r)$, $r < s$, at the cost of computing approximate solutions. It provides a cost interval that bounds the error of the approximation. Using the technique of cost function filtering, we obtain DMCTEf$(r)$. Combining cost function filtering with bound reasoning, we propose DIMCTEf, an algorithm based on repeated executions of DMCTEf$(r)$ with increasing $r$. DIMCTEf uses messages of previous iterations to decrease the size of messages in the current iteration, which allows to alleviate their high size. We provide evidences of the benefits of our approach on two benchmarks.
