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 [1], 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 [2]. 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 p2kn, 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 2005
- Accession Number
- ADA598539
Entities
People
- Anton Chechetka
- Katia Sycara
Organizations
- Carnegie Mellon University