Classical planning is the problem of finding a sequence of actions transforming a given initial state into a state satisfying a given goal. Today’s state of the art in classical planning almost universally operates on factored representations inspired by propositional logic: for example, a state space with 2^100 states can be represented with 100 propositional state variables.
Recently, the limitations of such representations have become increasingly apparent, and there is rapidly growing interest in algorithms that directly operate on lifted representations based on first-order predicate logic or similar formalisms. Moreover, several recent works suggested lifted representations that distill information across multiple tasks in the same planning domain (infinite family of planning tasks) into a single generalized representation that applies to all tasks in the domain. A typical approach is to learn or synthesize generalized representations from small example tasks in the domain and then use them to solve more challenging tasks.
We believe that the time is right for lifted and generalized representations to challenge propositional representations as the leading representation paradigm in classical planning. We suggest two research directions in pursuit of this goal:
Lifted algorithms for classical planning: we conceive and implement planning algorithms completely based on lifted representations that outperform state-of-the-art algorithms (based on non-lifted representations). We consider both the setting of satisficing planning (finding plans with no optimality guarantees) and optimal planning (finding plans of minimum cost). This involves devising efficient lifted algorithms for all building blocks of a state-of-the-art planning system and combining them into a well-engineered whole. One major goal for this work package is a “Lifted LAMA” planner outperforming Richter and Westphal’s highly influential LAMA system on the standard benchmark suite in classical planning.
Generalized representations for classical planning: several innovative generalized representations for classical planning have been suggested in the past few years, including action schema networks, generalized potential heuristics, STRIPS hypergraph networks, and sketches. They all come with the hope of significantly improving scalability of classical planning, but so far very little is known about their strengths and weaknesses, both in absolute terms and in relation to each other. We develop an encompassing theory that provides the formal underpinnings to put these disjointed results into a coherent whole. We formally clarify the notion of “planning domain” to be able to express the problems that these approaches attempt to solve in a rigorous way. We analyze the decidability and complexity properties of these problems, and we provide expressivity and compilation results demonstrating the strengths, weaknesses and relationships of these approaches. This includes relating representations used in planning to ones developed in other areas of AI such as (hyper-) graph neural networks and neural logic machines.