The Effect of Nogood Learning in Distributed Constraint
Satisfaction
Katsutoshi Hirayama, Makoto Yokoo,
20th International Conference on Distributed Computing Systems
(ICDCS-2000), 2000.
We present resolvent-based learning as a
new nogood learning method for a distributed constraint satisfaction
algorithm. This method is based on a look-back technique in constraint
satisfaction algorithms and can efficiently make effective nogoods.
We combine the method with the asynchronous weak-commitment
search algorithm} (AWC) and evaluate the performance of the resultant
algorithm on distributed 3-coloring problems and distributed 3SAT problems.
As a result, we found that the resolvent-based learning works well
compared to previous learning methods for distributed constraint
satisfaction algorithms. We also
found that the AWC with the resolvent-based learning is able to find a
solution with fewer cycles than the \textit{distributed breakout
algorithm}, which was known to be the most efficient algorithm (in terms
of cycles) for solving distributed constraint satisfaction problems.