loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.