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.