Skip to main content
placeholder image

SBDO: a new robust approach to dynamic distributed constraint optimisation

Journal Article


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.

UOW Authors


  •   Billiau, Graham (external author)
  •   Chang, Chee (external author)
  •   Ghose, Aditya

Publication Date


  • 2012

Citation


  • Billiau, G., Chang, C. & Ghose, A. (2012). SBDO: a new robust approach to dynamic distributed constraint optimisation. Lecture Notes in Computer Science, 7057 11-26. Kolkata SBDO: a new robust approach to dynamic distributed constraint optimisation

Scopus Eid


  • 2-s2.0-84877699843

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/1007

Number Of Pages


  • 15

Start Page


  • 11

End Page


  • 26

Volume


  • 7057

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.

UOW Authors


  •   Billiau, Graham (external author)
  •   Chang, Chee (external author)
  •   Ghose, Aditya

Publication Date


  • 2012

Citation


  • Billiau, G., Chang, C. & Ghose, A. (2012). SBDO: a new robust approach to dynamic distributed constraint optimisation. Lecture Notes in Computer Science, 7057 11-26. Kolkata SBDO: a new robust approach to dynamic distributed constraint optimisation

Scopus Eid


  • 2-s2.0-84877699843

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/1007

Number Of Pages


  • 15

Start Page


  • 11

End Page


  • 26

Volume


  • 7057