The distributed breakout algorithms

摘要

We present a new series of distributed constraint satisfaction algorithms, the distributed breakout algorithms, which is inspired by local search algorithms for solving the constraint satisfaction problem (CSP). The basic idea of these algorithms is for agents to repeatedly improve their tentative and flawed sets of assignments for variables simultaneously while communicating such tentative sets with each other until finding a solution to an instance of the distributed constraint satisfaction problem (DisCSP). We introduce four implementations of the distributed breakout algorithms: Single-DB, Multi-DB, Multi-DB+, and Multi-DB++. Single-DB is a distributed breakout algorithm for solving the DisCSP, where each agent has a single local variable and its related constraints. Multi-DB, on the other hand, is another distributed breakout algorithm for solving the distributed SAT (DisSAT) problem, where each agent has multiple local variables and their related clauses. Multi-DB+ and Multi-DB++ are stochastic variations of Multi-DB. In Multi-DB+, we introduce a technique called random break into Multi-DB; in Multi-DB++, we introduce a technique called random walk into Multi-DB+. We conducted experiments to compare these algorithms with the asynchronous type of distributed constraint satisfaction algorithm. Through these experiments, we found that Single-DB, Multi-DB, and Multi-DB+ scale up better than the asynchronous type of distributed constraint satisfaction algorithms, but they sometimes show very poor performance. On the other hand, we also found that Multi-DB++, which uses random walk, provides a clear performance improvement.