Asynchronous Search with Aggregations

Abstract

Many problem-solving tasks can be formalized as constraint satisfaction problems (CSPs). In a multi-agent setting, information about constraints and variables may belong to different agents and be kept confidential. Existing algorithms for distributed constraint satisfaction consider mainly the case where access to variables is restricted to certain agents, but constraints may have to be revealed. In this paper, we propose methods where constraints are private but variables can be manipulated by any agent. We describe a new search technique for distributed CSPs, called asynchronous aggregation search (AAS). It differs from existing methods in that it treats sets of partial solutions, exchanges information about aggregated valuations for combinations of variables and uses customized messages to allow distributed solution detection. Three new distributed backtracking algorithms based on AAS are then presented and analyzed. While the approach we propose provides a more general framework for dealing with privacy requirements on constraints, our experiments show that its overall performance is comparable or better than that of existing methods. Keywords: search, distributed AI, constraint satisfaction