Caching Schemes for DCOP Search Algorithms

Publication Type

Conference Proceeding Article

Publication Date

2009

Abstract

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.

Discipline

Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Publication

Proceedings of the Eighth International Conference on Autonomous Agents and Multi Agent Systems, AAMAS

Comments

Nominated for Jay Modi Best Student Paper Award

Additional URL

http://portal.acm.org/citation.cfm?id=1558098

Link to Full Text

Share

COinS