Keywords:

Abstract:

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.

• Tagged
• XML
• BibTex