Automated planning is one of the traditional and central research areas in artificial intelligence. In this context, planning means that an agent reasons over its possible courses of action in order to find out which activities it needs to carry out in order to reach its goals. For many applications of planning, it is desirable to produce not just any plan, but one that minimizes some cost metric, a problem called optimal planning. The most successful optimal planning algorithms of the last decade fall into the general class of heuristic search methods, typically using A* or a similar search algorithm.

A heuristic function, or heuristic for short, is a function that estimates how far away the planning agent is from its goal. More formally, a heuristic maps states s of the task to be solved to numerical estimates of the minimal cost of reaching the goal from s. For a heuristic search algorithm such as A* to be efficient, it must be supplied with a heuristic that is reasonably quickly computable as well as accurate (i.e., it should provide estimates that are close to the actual cost). To provide optimality guarantees, the heuristic must also be admissible, i.e., never overestimate the true cost.

Abstraction heuristics, such as pattern database heuristics and merge-and-shrink heuristics, have been a very successful class of admissible heuristics for optimal planning and related search problems. An abstraction heuristic maps states from the actual (concrete) state space of the planning task into a smaller space (the abstract state space) in a homomorphic manner, i.e., preserving state transitions and goal states. The cost to reach the goal in the abstract space then serves as a cost estimate for the concrete space.

Abstraction heuristics have been a subject of intense study in the planning literature in recent years, leading to several key breakthroughs both for practical algorithms and in the theoretical understanding of such heuristics. The latter theoretical studies in particular have shown that state-of-the-art abstraction heuristics, despite their significant successes, do not realize the power of the general approach to its full potential.

The research we propose here aims at reducing this gap between practical performance and theoretical promises. Specifically, we
pursue three objectives:

1. To advance the theory of abstraction heuristics in order to improve our theoretical understanding of their capabilities, their limitations, and their relationship to other commonly used approaches for deriving admissible heuristics.
2. To develop improved abstraction heuristics for optimal planning, hence raising the state of the art for optimal planning systems.
3. To transfer the new insights on abstraction heuristics to applications of optimal search outside of automated planning, in order to advance the state of the art in these areas.