Caching Schemes for DCOP Search Algorithms

• Main Authors: YEOH, William, VARAKANTHAM, Pradeep Reddy, Koenig, Sven
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2009
• Subjects: Artificial Intelligence and Robotics; Business; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/953; http://portal.acm.org/citation.cfm?id=1558098
• Institution: Singapore Management University

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.