Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs
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 promisi...
Saved in:
Main Authors: | , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2015
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/3155 https://ink.library.smu.edu.sg/context/sis_research/article/4155/viewcontent/P_ID_52423_EMDCOP.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-4155 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-41552018-06-27T05:43:04Z Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs GHOSH, Supriyo Akshat KUMAR, Pradeep VARAKANTHAM, 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. 2015-07-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/3155 https://ink.library.smu.edu.sg/context/sis_research/article/4155/viewcontent/P_ID_52423_EMDCOP.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Algorithms Artificial intelligence Benchmarking Constrained optimization Artificial Intelligence and Robotics Operations Research, Systems Engineering and Industrial Engineering |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Algorithms Artificial intelligence Benchmarking Constrained optimization Artificial Intelligence and Robotics Operations Research, Systems Engineering and Industrial Engineering |
spellingShingle |
Algorithms Artificial intelligence Benchmarking Constrained optimization Artificial Intelligence and Robotics Operations Research, Systems Engineering and Industrial Engineering GHOSH, Supriyo Akshat KUMAR, Pradeep VARAKANTHAM, Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs |
description |
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. |
format |
text |
author |
GHOSH, Supriyo Akshat KUMAR, Pradeep VARAKANTHAM, |
author_facet |
GHOSH, Supriyo Akshat KUMAR, Pradeep VARAKANTHAM, |
author_sort |
GHOSH, Supriyo |
title |
Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs |
title_short |
Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs |
title_full |
Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs |
title_fullStr |
Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs |
title_full_unstemmed |
Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs |
title_sort |
probabilistic inference based message-passing for resource constrained dcops |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2015 |
url |
https://ink.library.smu.edu.sg/sis_research/3155 https://ink.library.smu.edu.sg/context/sis_research/article/4155/viewcontent/P_ID_52423_EMDCOP.pdf |
_version_ |
1770572868872044544 |