A scalable method for multiagent constraint optimization

TLDR

The method is a utility‑propagation approach inspired by the sum‑product algorithm, correct only for tree‑shaped constraint networks. The paper proposes a complete dynamic‑programming based method for distributed constraint optimization and extends it to arbitrary topologies via a pseudotree arrangement. The algorithm performs dynamic programming over a pseudotree, sends a linear number of messages whose size depends on induced width, and is applicable to both optimization and satisfaction problems, with experimental comparison to backtracking algorithms. Experimental results show orders‑of‑magnitude fewer messages than backtracking algorithms and enable handling arbitrarily large problems.

Abstract

We present in this paper a new, complete method for distributed constraint optimization, based on dynamic programming. It is a utility propagation method, inspired by the sum-product algorithm, which is correct only for tree-shaped constraint networks. In this paper, we show how to extend that algorithm to arbitrary topologies using a pseudotree arrangement of the problem graph. Our algorithm requires a linear number of messages, whose maximal size depends on the induced width along the particular pseudotree chosen. We compare our algorithm with backtracking algorithms, and present experimental results. For some problem types we report orders of magnitude fewer messages, and the ability to deal with arbitrarily large problems. Our algorithm is formulated for optimization problems, but can be easily applied to satisfaction problems as well.