Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
12-2015
Abstract
Distributed constraint optimization (DCOP) problems are well-suited for modeling multi-agent coordination problems. However, it only models static problems, which do not change over time. Consequently, researchers have introduced the Dynamic DCOP (DDCOP) model to model dynamic problems. In this paper, we make two key contributions: (a) a procedure to reason with the incremental changes in DDCOPs and (b) an incremental pseudo-tree construction algorithm that can be used by DCOP algorithms such as any-space ADOPT and any-space BnB-ADOPT to solve DDCOPs. Due to the incremental reasoning employed, our experimental results show that any-space ADOPT and any-space BnB-ADOPT are up to 42% and 38% faster, respectively, with the incremental procedure and the incremental pseudo-tree reconstruction algorithm than without them.
Keywords
ADOPT, BnB-ADOPT, dynamic DCOP, DCOP
Discipline
Databases and Information Systems
Publication
Web Intelligent and Intelligent Agent Technologies, WI-IAT, 2015
First Page
1
Last Page
8
Identifier
10.1109/WI-IAT.2015.114
Publisher
IEEE
City or Country
Singapore
Citation
YEOH, William; Pradeep VARAKANTHAM; SUN, Xiaoxun; and KOENIG, Sven.
Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems. (2015). Web Intelligent and Intelligent Agent Technologies, WI-IAT, 2015. 1-8.
Available at: https://ink.library.smu.edu.sg/sis_research/3153
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/WI-IAT.2015.114