ER-DCOPs: A framework for distributed constraint optimization with uncertainty in constraint utilities

Tiep Le, Ferdinando Fioretto, William Yeoh, Tran Cao Son, Enrico Pontelli

Research output: Chapter in Book/Entry/PoemConference contribution

14 Scopus citations

Abstract

Distributed Constraint Optimization Problems (DCOPs) have been used to model a number of multi-agent coordination problems. In DCOPs, agents are assumed to have complete information about the utility of their possible actions. However, in many real-world applications, such utilities are stochastic due to the presence of exogenous events that are beyond the direct control of the agents. This paper addresses this issue by extending the standard DCOP model to Expected Regret DCOP (ER-DCOP) for DCOP applications with uncertainty in constraint utilities. Different from other approaches, ER-DCOPs aim at minimizing the overall expected regret of the problem. The paper proposes the ER-DPOP algorithm for solving ER-DCOPs, which is complete and requires a linear number of messages with respect to the number of agents in the problem. We further present two implementations of ER-DPOP-GPU- and ASP-based implementations-that orthogonally exploit the problem structure and present their evaluations on random networks and power network problems.

Original languageEnglish (US)
Title of host publicationAAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages606-614
Number of pages9
ISBN (Electronic)9781450342391
StatePublished - 2016
Externally publishedYes
Event15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016 - Singapore, Singapore
Duration: May 9 2016May 13 2016

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016
Country/TerritorySingapore
CitySingapore
Period5/9/165/13/16

Keywords

  • ASP
  • DCOP
  • Expected regret
  • GPU

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'ER-DCOPs: A framework for distributed constraint optimization with uncertainty in constraint utilities'. Together they form a unique fingerprint.

Cite this