Action planning is one of the oldest and one of the central research problems in artificial intelligence. A planning problem arises whenever an intelligent agent (virtual or embodied) needs to decide which activities it must carry out in order
to achieve its goals, or as Patrik Haslum put it succinctly: "Planning is the art and practice of thinking before acting."

Classical planning, the most widely studied variant of the planning problem with which this project is concerned, can be formalized as finding shortest paths (optimal planning) or any path (satisficing planning) from a given initial state to some goal state in an implicitly given planning task, essentially a directed graph. Planning is hard because these graphs are often enormous in size in practical applications, comprising 10¹⁰⁰ states or more, precluding the application of traditional "blind" graph search methods.

The most successful planning algorithms of the last decade fall into the general class of heuristic search methods, usually based on A* or a related search algorithm. In this context, the word heuristic, which carries a wide range of meanings in different areas of computer science, is a very specific technical term: a heuristic is a function whose input is a state s of a planning task and which returns an estimate of the distance from s to a nearest goal state. Heuristics are the heart and soul of planning algorithms based on state-space search. Depending on the accuracy of the heuristic estimates, heuristic search algorithms can range from solving planning tasks blindingly fast to being worse than blind search.

Hence, much of the most influential classical planning research in the recent past has been concerned with developing better and better heuristics and furthering our theoretical understanding of existing heuristics. This has led to increasingly more sophisticated approaches. A large
amount of human ingenuity has gone into devising today's advanced approaches and developing the underlying theory, especially in the case of optimal planning, where heuristics must satisfy a lower-bound property (be admissible) in order to be safe to use.

The central idea of this project is to shift this burden of sophistication and ingenuity away from the human heuristic designer and onto the machines that perform the heuristic search. Equipped with appropriate reasoning algorithms and representations, computers can derive knowledge about planning tasks more quickly, more reliably and in more complex settings than we humans are capable of. A planning researcher or practitioner should be able to focus on which information a planning algorithm ought to exploit, without having to worry about how to exploit it in the best way. In other words, we are suggesting a declarative approach to heuristic search planning that enables planning algorithms to reason about plans and heuristics in powerful and general ways.

A key research challenge in this endeavour is identifying an appropriate level of representation at which this declarative information is specified. It should be general enough to capture the concepts that today's state-of-the-art planning algorithms rely on in order to obtain accurate heuristic estimates, yet limited enough to afford efficient reasoning algorithms. In this project, we explore this design space in depth, both theoretically and with an emphasis on efficient practical algorithms.