Recent work on learning for classical planning has primarily focused on exclusively employing the learned heuristics or policies. However, no purely learning-based method has consistently outperformed state-of-the-art planners to date. To address this, we return to the research paradigm that integrates learned domain knowledge with traditional, non-learned planning techniques. We propose a novel and simple approach for learning transition classifiers, using tree-based statistical learning over description logic features. In experiments, we evaluate various strategies for integrating learned classifiers with the FF heuristic, a state-of-the-art non-learned heuristic. Our results demonstrate that augmenting classical heuristics with transition classifiers leads to substantial performance improvements. The strongest variant combines classifier-based lookahead search with learned knowledge to avoid transitions into unsolvable states, frequently outperforming state-of-the-art traditional and learning-based planners.

Classical planning aims to find a plan that is a sequence of actions allowing an intelligent agent to move from its current situation to one that satisfies the goal. Finding a plan is computationally challenging. Agents in the real world often encounter structurally similar problems with varying objects but the same predicates, actions, and related goals. Generalized planning aims to find a general plan that compactly encodes efficiently obtainable plans for each problem in an infinitely large class of structurally similar problems. Thus, we can query a general plan to efficiently obtain a plan for any problem in the class. A general plan may encode behavior on different levels of abstraction. High-level abstractions include subgoal structures that encode stepping stones towards the goal. Subgoal structures play a central role in human problem-solving, enabling reasoning at a higher level before working out the details of a plan. Learning simple, compact, meaningful, and efficient subgoal structures and their hierarchies without human intervention is an open challenge.

This thesis introduces a method for learning subgoal structures with a crisp characterization; they decompose problems into subproblems of controllable polynomial complexity. We represent subgoal structures using the recently introduced policy sketches language, whose simple syntax and semantics build the theoretical foundation of our work. We extend our method to address the long-standing problem of learning hierarchical policies. Our extended method iteratively decomposes classes of problems into classes of subproblems with strictly smaller polynomial complexity, resulting in effective hierarchical decompositions. Our methods learn from small example problems using combinatorial optimization. They seek the syntactically simplest solution, enabling interpretability and allowing us often to establish their correctness for an entire problem class. When learning methods fail, it often results from limited scalability or a lack of language expressivity. We develop two methods to address these limitations. First, we develop symmetry-based abstractions to reduce redundancy in training data and improve learning efficiency. Second, we develop a method for testing the language expressivity requirement of benchmark sets using first-order logic. Moreover, we take steps toward developing a scalable planning framework that avoids an exponential preprocessing step known as grounding, which is often unnecessary in generalized planning. Our framework supports expressive language features such as conditional effects and derived predicates that cannot concisely be compiled away, enabling researchers to model and address more complex planning problems.

Identifying state symmetries plays a crucial role in minimiz-ing the number of states explored during search, yet identify-ing precisely all symmetries is computationally hard. In thecontext of learning general policies that solve instances ofarbitrary size from small instances, however, this computa-tional bottleneck is not a problem. In this paper, we addressthe task of identifying all state symmetries through the lensof the graph isomorphism problem. To accomplish this, werepresent states as undirected, labeled graphs that reflect therelational structure of states and the goal. We then use off-the-shelf graph isomorphism algorithms to determine whethertwo states are isomorphic with respect to the goal. The iso-morphism relationship forms equivalent classes that result inan abstract state space that can be used instead of the origi-nal one to learn general policies more efficiently. While thisabstract state space can be used for many different learningtasks, we focus on learning symbolic general policies wherewe show that the proposed approach can lead to significantspeedups.

Recently,a simple but powerful language for expressing and learning general policies and problem decompositions (sketches) has been introduced in terms of rules defined over a set of Boolean and numerical features. In this work, we consider three extensions of this language aimed at making policies and sketches more flexible and reusable: internal memory states, as in finite state controllers; indexical features, whose values are a function of the state and a number of internal registers that can be loaded with objects; and modules that wrap up policies and sketches and allow them to call each other by passing parameters. In addition, unlike general policies that select state transitions rather than ground actions, the new language allows for the selection of such actions. The expressive power of the resulting language for policies and sketches is illustrated through a number of examples.

State symmetries play an important role in planning and generalized planning. In the first case, state symmetries can be used to reduce the size of the search; in the second, to reduce the size of the training set. In the case of general planning, however, it is also critical to distinguish non-symmetric states, i.e., states that represent non-isomorphic relational structures. However, while the language of first-order logic distinguishes non-symmetric states, the languages and architectures used to represent and learn general policies do not. In particular, recent approaches for learning general policies use state features derived from description logics or learned via graph neural networks (GNNs) that are known to be limited by the expressive power of C₂, first-order logic with two variables and counting. In this work, we address the problem of detecting symmetries in planning and generalized planning and use the results to assess the expressive requirements for learning general policies over various planning domains. For this, we map planning states to plain graphs, run off-the-shelf algorithms to determine whether two states are isomorphic with respect to the goal, and run coloring algorithms to determine if C₂ features computed logically or via GNNs distinguish non-isomorphic states. Symmetry detection results in more effective learning, while the failure to detect non-symmetries prevents general policies from being learned at all in certain domains.

Recently, a simple but powerful language for expressing and learning generalpolicies and problem decompositions (sketches) has been introduced, which isbased on collections of rules defined on a set of Boolean and numerical features.In this work, we consider extensions of this basic language aimed at makingpolicies and sketches more flexible and reusable. For this, three basic extensionsare considered: 1) internal memory states, as in finite state controllers, 2) indexicalfeatures, whose values are a function of the state and a number of internal registersthat can be loaded with objects, and 3) modules that wrap up policies and sketchesand allow them to call each other by passing parameters. In addition, unlikepreviously defined policies that select actions indirectly by the selection of statetransitions, the new language allows for the selection of actions directly. Theexpressive power of the resulting language for recombining policies and sketchesis illustrated through examples. The problem of learning policies and sketches inthe new language is left for future work.

Hierarchical policies are a key ingredient of intelligent behavior, expressing the different levels of abstraction involved in the solution of a problem. Learning hierarchical policies, however, remains a challenge, as no general learning principles have been identified for this purpose, despite the broad interest and vast literature in both model-free reinforcement learning and model-based planning. In this work, we introduce a principled method for learning hierarchical policies over classical planning domains, with no supervision from small instances. The method is based on learning to decompose problems into subproblems so that the subproblems have a lower complexity as measured by their width. Problems and subproblems are captured by means of sketch rules, and the scheme for reducing the width of sketch rules is applied iteratively until the final sketch rules have zero width and encode a general policy. We evaluate the learning method on a number of classical planning domains, analyze the resulting hierarchical policies, and prove their properties. We also show that learning hierarchical policies by learning and refining sketches iteratively is often more efficient than learning flat general policies in one shot.

Generalized planning aims to compute generalized plans that solve a whole class of problems from a given tractable planning domain.Recently, the D2L system showed how to learn generalized plans with the form of general policies in a self-supervised manner with a MaxSAT solver, where states and transitions are qualitatively abstracted by a set of description logics features.However, D2L requires to fully explore the state space of the input planning problems, which is a major bottleneck even for simple domains.Therefore, we propose the Incremental-D2L algorithm that only requires to explore small fragments of the input state spaces and show that it scales to harder training instances.For very hard domains, where we are unable to learn a general policy, Incremental-D2L yields a partial policy that we can use to enhance a greedy best-first search.Our experiments show that preferring learned {\em helpful actions}, i.e., actions compatible with the (partial) policy, significantly reduces the search effort for many of the considered domains.

Recently, sketches have been introduced as a general language for representing the subgoal structure of instances drawn from the same domain. Sketches are collections of rules of the form C -> E over a given set of features where C expresses Boolean conditions and E expresses qualitative changes. Each sketch rule defines a subproblem: going from a state that satisfies C to a state that achieves the change expressed by E or a goal state. Sketches can encode simple goal serializations, general policies, or decompositions of bounded width that can be solved greedily, in polynomial time, by the SIW_R variant of the SIW algorithm. Previous work has shown the computational value of sketches over benchmark domains that, while tractable, are challenging for domain-independent planners. In this work, we address the problem of learning sketches automatically given a planning domain, some instances of the target class of problems, and the desired bound on the sketch width. We present a logical formulation of the problem, an implementation using the ASP solver Clingo, and experimental results. The sketch learner and the SIW_R planner yield a domain-independent planner that learns and exploits domain structure in a crisp and explicit form.

Width-based planning methods deal with conjunctive goals by decomposing problems into subproblems of low width. Algorithms like SIW thus fail when the goal is not easily serializable in this way or when some of the subproblems have a high width. In this work, we address these limitations by using a simple but powerful language for expressing finer problem decompositions introduced recently by Bonet and Geffner, called policy sketches. A policy sketch R over a set of Boolean and numerical features is a set of sketch rules that express how the values of these features are supposed to change. Like general policies, policy sketches are domain general, but unlike policies, the changes captured by sketch rules do not need to be achieved in a single step. We show that many planning domains that cannot be solved by SIW are provably solvable in low polynomial time with the SIW_R algorithm, the version of SIW that employs user-provided policy sketches. Policy sketches are thus shown to be a powerful language for expressing domain-specific knowledge in a simple and compact way and a convenient alternative to languages such as HTNs or temporal logics. Furthermore, they make it easy to express general problem decompositions and prove key properties of them like their width and complexity.