Speaker:
John Hooker
GSIA, Carnegie Mellon University
Title:
Resolution-Based Dynamic Search
Abstract:
This talk presents a family of search methods that
combine the completeness of branching with some of the
flexibility of local search. Completeness is achieved
by applying a limited form of resolution to the set of
nogoods so far generated. Stronger forms of resolution
allow greater freedom but incur more overhead. At one
extreme, full resolution allows complete freedom, and
at the other, chronological backtracking is inflexible
but uses a very fast form of resolution. This family
of methods generalizes backjumping, dependency-directed
backtracking, dynamic backtracking, and the partial order
dynamic backtracking of Ginsberg and McAllester. The
ideas are presented through a series of examples.