A Decentralized Variable Ordering Method for Distributed Constraint Optimization

Abstract

Many different multi-agent problems, such as distributed scheduling can be formalized as distributed constraint optimization. Ordering the constraint variables is an important preprocessing step of the ADOPT algorithm, the state of the art method of solving distributed constraint optimization problems (DCOP). Currently ADOPT uses depth-first search (DFS) trees for that purpose. For certain classes of tasks DFS ordering does not exploit the problem structure as compared to pseudo-tree ordering. Also the variables are currently ordered in a centralized manner, which requires global information about the problem structure. We present a variable ordering algorithm, which is both decentralized and makes use of pseudo-trees, thus exploiting the problem structure when possible. This allows to apply ADOPT to domains, where global information is unavailable, and find solutions more efficiently. The worst-case pseudo-tree depth resulting from our algorithm is O(2kn), where n is the number of variables, and k is maximum block size in constraint graph. The algorithm has space complexity of O(kn) and time complexity of O(n+|E|+k^(3/2)n^(1/2)), where E is the set of edges in a constraint graph.