Increasing Nogoods in Restart-Based Search
Jimmy Ho Man Lee, Christian Schulte, Zichen Zhu.
Restarts are an important technique to make search more robust. The benefit of restarts can be considerably enhanced by recording nogoods generated at the end of each search run and propagating them in future runs to avoid repeating erroneous search decisions. This paper is concerned with how to maintain and propagate nogoods recorded from restarts efficiently. It builds on reduced nld-nogoods introduced for restarts and increasing nogoods introduced for symmetry breaking. The paper shows that reduced nld-nogoods extracted from a single restart are in fact increasing, which can thus benefit from the strong propagation power of the incNGs global constraint. We present a lightweight filtering algorithm for incNGs in the context of restart-based search using dynamic event sets (dynamic subscriptions). We show formally that the lightweight version enforces GAC on each nogood while reducing the number of subscribed decisions. The paper also introduces an efficient approximation to nogood minimization such that all shortened reduced nld-nogoods from the same restart are also increasing and can be propagated with the new filtering algorithm. Experimental results confirm that our lightweight filtering algorithm and approximated nogood minimization successfully trade a slight loss in pruning for considerably better efficiency, and hence compare favorably against existing state-of-the-art techniques.
In: Dale Schuurmans, Michael Wellman, editors, AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA, pages 3426-3433. AAAI Press, February, 2016.
Copyright © by American Association for Artificial Intelligence.