Trading Off Solution Quality for Faster Computation in DCOP Search Algorithms
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 354-359.
Abstract
Distributed Constraint Optimization (DCOP) is a key technique for solving agent coordination problems. Because finding cost-minimal DCOP solutions is NP-hard, it is important to develop mechanisms for DCOP search algorithms that trade off their solution costs for smaller runtimes. However, existing tradeoff mechanisms do not provide relative error bounds. In this paper, we introduce three tradeoff mechanisms that provide such bounds, namely the Relative Error Mechanism, the Uniformly Weighted Heuristics Mechanism and the Non-Uniformly Weighted Heuristics Mechanism, for two DCOP algorithms, namely ADOPT and BnB-ADOPT. Our experimental results show that the Relative Error Mechanism generally dominates the other two tradeoff mechanisms for ADOPT and the Uniformly Weighted Heuristics Mechanism generally dominates the other two tradeoff mechanisms for BnB-ADOPT.William Yeoh, Xiaoxun Sun, Sven Koenig
@inproceedings{ijcai2009p67,
title = {Trading Off Solution Quality for Faster Computation in DCOP Search Algorithms},
author = {Yeoh, William and Sun, Xiaoxun and Koenig, Sven},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {354--359},
year = {2009},
url = {https://ijcai.org/proceedings/2009/67},
}
TY - CPAPER TI - Trading Off Solution Quality for Faster Computation in DCOP Search Algorithms AU - Yeoh, William AU - Sun, Xiaoxun AU - Koenig, Sven T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 354 EP - 359 UR - https://ijcai.org/proceedings/2009/67 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
