20th IEEE International Conference on Distributed Computing Systems (ICDCS'00)
The Effect of Nogood Learning in Distributed Constraint Satisfaction
Taipei, Taiwan
April 10-April 13
ISBN: 0-7695-0601-1
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 distributed breakout algorithm, which was known to be the most efficient algorithm (in terms of cycles) for solving distributed constraint satisfaction problems.
Citation:
Katsutoshi Hirayama, Makoto Yokoo, "The Effect of Nogood Learning in Distributed Constraint Satisfaction," icdcs, pp.169, 20th IEEE International Conference on Distributed Computing Systems (ICDCS'00), 2000