TítuloRemoving Redundant Messaegs in N-ary BnB-ADOPT
Publication TypeJournal Article
Year of Publication2012
AuthorsGutierrez P, Meseguer P
JournalJournal of Artificial Intelligence Research
Volume45
Paginación287-304
Palabras claveBnB-ADOPT, DCOP
Resumen

This note considers how to modify BnB-ADOPT (Yeoh, Felner,& Koenig, 2010), 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, dividing in most cases the number of messages by 3 and more (keeping the other measures almost unchanged) and maintaining termination and optimality properties. 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.