Traversing large search spaces can be done more efficiently by exploiting the dead-ends –in formal terms nogoods– discovered during search. If a previously found nogood appears again, the search process can avoid it, saving some search effort. Storing all found nogoods may require exponential memory, which is unaffordable. However, current memories allow to store a large set of nogoods, to be maintained during the solving process. In many cases, a solution is found before memory is exhausted. In the context of Distributed Constraint Satisfaction, the AWC algorithm allows to compute a solution quickly but, to guarantee completeness, it requires storing all found nogoods. Trading space per time, we develop a new iterative version of the algorithm that delays the exponential effects. We present this new version in the context of distributed SAT, where agents hold several Boolean variables. Taking advantage of existing SAT technology, this version perform calls to external MaxSAT solver. Experimentally, we confirm the benefits of the proposed approach on several benchmarks.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com