Affiliations: IIIA, Artificial Intelligence Research Institute, CSIC, Spanish National Research Council, Campus UAB, 08193 Bellaterra, Spain. [email protected]; [email protected]
Note: [] This work has been partially supported by the project TIN2009-13591-C02-02.
Note: [] Address for correspondence: IIIA, CSIC, Campus UAB 08193 Bellaterra, Spain
Abstract: 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.
Keywords: Distributed constraint optimization, distributed cluster-tree elimination, function filtering
