English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/138166
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


Removing Redundant Messages in N-ary BnB-ADOPT

AuthorsGutierrez, Patricia; Meseguer, Pedro
KeywordsRedundant messages
Communication efficiency
Distributed constraint optimizations
Issue Date2012
PublisherMorgan Kaufmann
CitationJournal of Artificial Intelligence Research 45: 287- 304 (2012)
AbstractThis note considers how to modify BnB-ADOPT, a well-known algorithm for optimally solving distributed constraint optimization problems, with a double aim: (i) to avoid sending most of the redundant messages and (ii) to handle cost functions of any arity. Some of the messages exchanged by BnB-ADOPT turned out to be redundant. Removing most of the redundant messages increases substantially communication efficiency: the number of exchanged messages is ¿in most cases¿ at least three times fewer (keeping the other measures almost unchanged), and termination and optimality are maintained. On the other hand, handling n-ary cost functions was addressed in the original work, but the presence of thresholds makes their practical usage more complex. Both issues ¿removing most of the redundant messages and efficiently handling n-ary cost functions¿ can be combined, producing the new version BnB-ADOPT+. Experimentally, we show the benefits of this version over the original one.
Identifiersissn: 1076-9757
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.