19th IEEE International Conference on Tools with Artificial Intelligence - Vol.2 (ICTAI 2007)
Adaptive Lookahead for Answer Set Computation
Paris, France
October 29-October 31
ISBN: 0-7695-3015-X
Lookahead is a well-known constraint propagation tech- nique for DPLL-based SAT and answer set solvers. Despite its space pruning power, it can also slow down the search, due to its high overhead. In this paper, this twofold effect is analyzed. On one side, we give characterizations of the problems for which the cause for the reduction of search efficiency shows clearly. On the other we show that prob- lem instances that lie in the phase transition regions often significantly benefit from the use of lookahead. Our anal- ysis leads to a proposal of adaptive lookahead, which per- forms lookahead according to the learned information dur- ing the search. Adaptive lookahead is implemented in one of the best-known answer set solvers, smodels. Our experi- ments show that adaptive lookahead adapts well to different search environments it is going through.
Citation:
Guohua Liu, Jia-Huai You, "Adaptive Lookahead for Answer Set Computation," ictai, vol. 2, pp.230-237, 19th IEEE International Conference on Tools with Artificial Intelligence - Vol.2 (ICTAI 2007), 2007