Caching Schemes for DCOP Search Algorithms
Conference Proceeding Article
Distributed Constraint Optimization (DCOP) is useful for solving agent-coordination problems. Any-space DCOP search algorithms require only a small amount of memory but can be sped up by caching information. However, their current caching schemes do not exploit the cached information when deciding which information to preempt from the cache when a new piece of information needs to be cached. Our contributions are three-fold: (1) We frame the problem as an optimization problem. (2) We introduce three new caching schemes (MaxPriority, MaxEffort and MaxUtility) that exploit the cached information in a DCOP-specific way. (3) We evaluate how the resulting speed up depends on the search strategy of the DCOP search algorithm. Our experimental results show that, on all tested DCOP problem classes, our MaxEffort and MaxUtility schemes speed up ADOPT (which uses best-first search) more than the other tested caching schemes, while our MaxPriority scheme speeds up BnB-ADOPT (which uses depth-first branch-and-bound search) at least as much as the other tested caching schemes.
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
Proceedings of the Eighth International Conference on Autonomous Agents and Multi Agent Systems, AAMAS
YEOH, William; VARAKANTHAM, Pradeep Reddy; and Koenig, Sven.
Caching Schemes for DCOP Search Algorithms. (2009). Proceedings of the Eighth International Conference on Autonomous Agents and Multi Agent Systems, AAMAS. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/953