Title: | Impact of Problem Centralization in Distributed Constraint Optimization Algorithms |

Author: | John Davin and Pragnesh Jay Modi |

Book Tittle: | Proceedings of the Fourth International Joint Conference on Autonomous Agents and MultiAgent Systems |

Pages: | 1057--1066 |

Year: | 2005 |

Crossref: | aamas05 |

Abstract: | Recent progress in Distributed Constraint Optimization Problems (DCOP) has led to a range of algorithms now available which differ in their amount of problem centralization. Problem centralization can have a significant impact on the amount of computation required by an agent but unfortunately the dominant evaluation metric of “number of cycles” fails to account for this cost. We analyze the relative performance of two recent algorithms for DCOP: OptAPO, which performs partial centralization, and Adopt, which maintains distribution of the DCOP. Previous comparison of Adopt and OptAPO has found that OptAPO requires fewer cycles than Adopt. We extend the cycles metric to define “Cycle-Based Runtime (CBR)” to account for both the amount of computation required in each cycle and the communication latency between cycles. Using the CBR metric, we show that Adopt outperforms OptAPO under a range of communication latencies. We also ask: What level of centralization is most suitable for a given communication latency? We use CBR to create performance curves for three algorithms that vary in degree of centralization, namely Adopt, OptAPO, and centralized Branch and Bound search. |

Cited by 27

@InProceedings{davin05a, author = {John Davin and Pragnesh Jay Modi}, title = {Impact of Problem Centralization in Distributed Constraint Optimization Algorithms}, booktitle = {Proceedings of the Fourth International Joint Conference on Autonomous Agents and MultiAgent Systems}, crossref = {aamas05}, pages = {1057--1066}, year = 2005, abstract = {Recent progress in Distributed Constraint Optimization Problems (DCOP) has led to a range of algorithms now available which differ in their amount of problem centralization. Problem centralization can have a significant impact on the amount of computation required by an agent but unfortunately the dominant evaluation metric of ``number of cycles'' fails to account for this cost. We analyze the relative performance of two recent algorithms for DCOP: OptAPO, which performs partial centralization, and Adopt, which maintains distribution of the DCOP. Previous comparison of Adopt and OptAPO has found that OptAPO requires fewer cycles than Adopt. We extend the cycles metric to define ``Cycle-Based Runtime (CBR)'' to account for both the amount of computation required in each cycle and the communication latency between cycles. Using the CBR metric, we show that Adopt outperforms OptAPO under a range of communication latencies. We also ask: What level of centralization is most suitable for a given communication latency? We use CBR to create performance curves for three algorithms that vary in degree of centralization, namely Adopt, OptAPO, and centralized Branch and Bound search.}, keywords = {multiagent distributed-search dcop}, url = {http://jmvidal.cse.sc.edu/library/davin05a.pdf}, googleid = {m23paRkdgGIJ:scholar.google.com/}, cluster = {7097705007724195227} }Last modified: Wed Mar 9 10:16:27 EST 2011