Local Search for DisCSPs with Complex Local Problems

摘要

Algorithms for solving distributed constraint satisfaction problems (DisCSPs) generally assume, simplistically, that an agent represents a single variable. However, real distributed problems normally have several variables per local problem (called a complex local problem). Two major approaches of compilation and decomposition are used in solving this type of problem. In compilation, a new variable per agent is defined whose domain is the set of compound solutions to the complex local problem while in decomposition virtual agents are created to represent each variable. In this paper, we present Multi-DynAPP which is a local search algorithm for DisCSPs with complex local problems that uses a hybrid of compilation and decomposition approaches: (i) Each agent conducts an exhaustive search to find locally consistent solutions to only its external variables (variables constrained with variables in other agents), (ii) These solutions are used by a distributed local search to solve the inter-agent constraints, producing a partial solution and, (iii) Agents then locally extend the partial solution to satisfy the rest of their intra-agent constraints. Empirical studies show that Multi-DynAPP gives a significant improvement over current local search DisCSP algorithms for DisCSPs where agents' external variables form small groups.