Pushing the Envelope: Abstraction, Refinement, and Quality Bounds – BARQ

Combinatorial search problems are ubiquitous in many fields of
Computer Science. A common technique for addressing them is the
exploitation of lower bounds: optimistic estimates of the cost for
transforming a state into a solution. But how to compute such
estimates? The proposed BARQ project addresses this question, in a
highly inter-disciplinary fashion encompassing Classical Planning,
Probabilistic Planning, Scheduling, and Model Checking. To our
knowledge, BARQ is the first project addressing all these areas in
unison. We use abstraction to obtain the lower bounds, and we use
abstraction refinement to incrementally improve these bounds. Combined
with upper bounding methods, this yields highly practical anytime
algorithms that guarantee bounds on the quality of the current
solution.

The core technique we focus on is state abstraction, which imposes an
equivalence relation over states. We consider a recent scheme, nested
state aggregation (NSA), for constructing such abstractions. NSA
incorporates a computational trick allowing fine-tuned design of the
equivalence relation by selecting individual pairs of states to
aggregate into one. It has been shown in Classical Planning that, in
theory, this approach dominates most other known abstraction
schemes. That power hinges, however, on perfect selection of the
states to aggregate. Hardly anything is known about how to make this
selection. BARQ fills this gap. To this end, we draw on research
traditions from Probabilistic Planning and Model Checking, concerned
with state abstraction and abstraction refinement. These traditions
have addressed similar questions, but for very different purposes
forcing the abstraction to preserve the exact set of solutions. Our
research relaxes this restriction to obtain lower bounding methods
instead, thus uncovering several new connections between the addressed
areas.

BARQ is mainly motivated by basic research questions. However, each of
the four areas addressed has a tradition of practical applications,
which we will leverage for the final evaluation of the developed
techniques.