Abstraction Heuristics Extended with Counting Abstractions

Abstract

State-of-the-art abstraction heuristics are those constructed by the merge-and-shrink approach in which an abstraction consists of a labeled transition system, and the composition of abstractions correspond to the synchronized product of transition systems. Merge-and-shrink heuristics build a composite abstraction from atomic abstractions that are directly associated with the variables of the planning problem. In this paper, we show that the framework of labeled transition systems is more general, and propose a new type of abstraction called the counting abstraction. Counting abstractions can be transparently combined with other type of abstractions to get more informative heuristics. We show how to effectively construct the counting abstractions and presents preliminary experiments over benchmark problems.