Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
7-2015
Abstract
Distributed constraint optimization (DCOP) is an important framework for coordinated multiagent decision making. We address a practically useful variant of DCOP, called resource-constrained DCOP (RC-DCOP), which takes into account agents’ consumption of shared limited resources. We present a promising new class of algorithm for RC-DCOPs by translating the underlying co- ordination problem to probabilistic inference. Using inference techniques such as expectation- maximization and convex optimization machinery, we develop a novel convergent message-passing algorithm for RC-DCOPs. Experiments on standard benchmarks show that our approach provides better quality than previous best DCOP algorithms and has much lower failure rate. Comparisons against an efficient centralized solver show that our approach provides near-optimal solutions, and is significantly faster on larger instances.
Keywords
Algorithms, Artificial intelligence, Benchmarking, Constrained optimization
Discipline
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Intelligent Systems and Optimization
Publication
Proceedings of the 24th International Joint Conference on Artificial Intelligence IJCAI 2015: Buenos Aires, Argentina, 25-31 July
First Page
411
Last Page
417
ISBN
9781577357384
Publisher
AAAI Press
City or Country
Palo Alto, CA
Citation
GHOSH, Supriyo; Akshat KUMAR; and Pradeep VARAKANTHAM.
Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs. (2015). Proceedings of the 24th International Joint Conference on Artificial Intelligence IJCAI 2015: Buenos Aires, Argentina, 25-31 July. 411-417.
Available at: https://ink.library.smu.edu.sg/sis_research/3155
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons