A Decentralized Variable Ordering Method for Distributed Constraint Optimization

Anton Chechetka and Katia Sycara
tech. report CMU-RI-TR-05-18, Robotics Institute, Carnegie Mellon University, May, 2005


Download
  • Adobe portable document format (pdf) (246KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Keywords
constraint satisfaction

Notes
Sponsor: AFOSR
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Advanced Agent - Robotics Technology Lab
Number of pages: 26

Text Reference
Anton Chechetka and Katia Sycara, "A Decentralized Variable Ordering Method for Distributed Constraint Optimization," tech. report CMU-RI-TR-05-18, Robotics Institute, Carnegie Mellon University, May, 2005

BibTeX Reference
@techreport{Chechetka_2005_5107,
   author = "Anton Chechetka and Katia Sycara",
   title = "A Decentralized Variable Ordering Method for Distributed Constraint Optimization",
   booktitle = "",
   institution = "Robotics Institute",
   month = "May",
   year = "2005",
   number= "CMU-RI-TR-05-18",
   address= "Pittsburgh, PA",
}