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 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||