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, ...
详细信息
ISBN:
(纸本)9781614998068;9781614998051
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.
暂无评论