SBDO: a new robust approach to dynamic distributed constraint optimisation
RIS ID
76732
Abstract
Dynamic distributed constraint optimisation problems are a very effective tool for solving multi-agent problems. However they require protocols for agents to collaborate in optimising shared objectives in a decentralised manner without necessarily revealing all of their private constraints. In this paper, we present the details of the Support-Based Distributed Optimisation (SBDO) algorithm for solving dynamic distributed constraint optimisation problems. This algorithm is complete wrt hard constraints but not wrt objectives. Furthermore, we show that SBDO is completely asynchronous, sound and fault tolerant. Finally, we evaluate the performance of SDBO with respect to DynCOAA for DynDCOP and ADOPT, DPOP for DCOP. The results highlight that in general, SBDO out performs these algorithms on criteria such as time, solution quality, number of messages, non-concurrent constraint checks and memory usage.
Publication Details
Billiau, G., Chang, C. & Ghose, A. (2012). SBDO: a new robust approach to dynamic distributed constraint optimisation. Lecture Notes in Computer Science, 7057 (N/A), 11-26.