Local search for distributed SAT with complex local problems
Katsutoshi Hirayama, Makoto Yokoo · 2002
A distributed constraint satisfaction problem(DisCSP) is a general framework that can formalize various application problems in Multi-Agent Systems. The authors have developed a series of algorithms for solving DisCSPs, including an iterative improvement algorithm called the distributed breakout (DB) algorithm. This algorithm, however, deals only with DisCSPs where each agent has exactly one local variable and the relevant constraints to the variable. In this paper, we propose a new algorithm called Multi-DB for solving distributed SAT (DisSAT) where each agent has multiple local variables and the relevant clauses to the variables. We conduct an experiment to compare Multi-DB with the previous algorithm called Multi-AWC on well-known (Dis)3-SAT benchmarks. The results are very impressive since Multi-DB has much less average communication and computation costs for almost all cases (at least an order of magnitude less for larger problems). We also identify a trade-off between communication and computation costs of algorithms when we vary the degree of decentralization.