Abstract
Automated decision-making is a fundamental topic that spans multiple sub-disciplines in AI: reinforcement learning (RL), AI planning (AP), foundation models, and operations research, among others. Despite recent efforts to “bridge the gaps” between these communities, there remain many insights that have not yet transcended the boundaries. Our goal in this paper is to provide a brief and non-exhaustive primer on ideas well-known in AP, but less so in other sub-disciplines. We do so by introducing the classical AP problem and representation, and extensions that handle uncertainty and time through the Markov Decision Process formalism. Next, we survey state-of-the-art techniques and ideas for solving AP problems, focusing on their ability to exploit problem structure. Lastly, we cover subfields within AP for learning structure from unstructured inputs and learning to generalise to unseen scenarios and situations.
Introduction: Bridging the Insights Gap
In the quest for autonomous decision-making, two communities have historically worked in parallel: Reinforcement Learning (RL) and AI Planning (AP). RL agents typically learn by trial and error in "black-box" environments, which often struggles with sparse rewards and long-term goals. Conversely, AP agents reason over "white-box" structured models (like PDDL), which allows for powerful domain-independent algorithms but traditionally requires humans to manually design those models.
This paper serves as a bridge between these worlds, arguing that by leveraging structured, symbolic world models, agents can solve complex, long-horizon tasks with far greater efficiency and generalization than "black-box" RL approaches. A central challenge addressed is Generalization in Planning: how an agent can learn from a few small examples and then solve a test problem with an arbitrary number of objects (e.g., moving from a 3-block tower to a 100-block tower) without further training.
A Hierarchy of Access
The paper categorizes the field through a new Hierarchy of Access, describing the degree of environmental knowledge available to an agent:
- Continuing/Episodic: No model access (standard RL).
- Generative: Access to a simulator (sampling).
- Analytic: Access to exact transition and reward functions.
- Structured: Access to symbolic representations, considered the "gold standard" for AI Planning.
Core Pillars of AI Planning
Modern AP research is built upon three main pillars:
- Representations: Utilizing first-order logic and the "closed-world assumption" to compactly represent combinatorially large state spaces.
- Heuristic Search: Implementing techniques like "delete-relaxation" (ignoring negative effects of actions to estimate costs) and "abstractions" to guide search algorithms such as A* or Greedy Best-First Search.
- Learning in AP: This encompasses Learning Planning Models (LPM) (deriving PDDL from raw images or traces), Learning for Planning (L4P) (using GNNs to learn heuristics), and Generalized Planning (GP) (synthesizing programs that solve infinite sets of problems).
Generalization and Structural Priors
One of the most significant advantages of structured AP models is their "lifted" nature. Unlike standard neural networks that are often tied to a specific input size, a policy learned for a small problem can often be applied to a much larger version of the same problem without any retraining.
Key insights include:
- The "Attention" Analogy: Predicate logic in AP functions similarly to "attention" in Machine Learning. By using predicates, a planner can query a state like a database, focusing only on relevant facts and ignoring environmental noise.
- Upgrading Access Levels: Agents can be "upgraded" from black-box (RL) levels to structured (AP) levels by learning symbolic models from raw pixels or state-action traces.
- Zero-Shot Generalization: AP uses structural priors—such as the fact that actions have preconditions and effects—to achieve massive sample efficiency and zero-shot generalization to unseen scenarios.
Benchmarks and Quantitative Trends
The paper references several standard benchmarks:
- International Planning Competition (IPC): The primary source for classical and expressive planning benchmarks.
- PDDLGym: A toolkit converting PDDL domains into OpenAI Gym environments for RL comparison.
- ALFWorld & MiniGrid: Embodied AI benchmarks exhibiting planning characteristics like deterministic actions and sparse rewards.
While solving symbolic planning tasks is EXPSPACE-complete, modern planners exploit structure to solve them routinely. Recent L4P techniques can generate effective generalized heuristics using only a few dozen small training tasks with a median training time of just one second. Furthermore, classical machine learning using graph kernels can train models as expressive as Graph Neural Networks (GNNs) but several orders of magnitude faster.
Limitations and Future Frontiers
Despite its strengths, AP faces several challenges:
- The Knowledge Bottleneck: Many techniques still rely on human-authored PDDL files, which are difficult to write for complex, real-world domains.
- Decidability in GP: Finding generalized solutions is difficult; simple representations for generalized plans are Turing-equivalent, making termination or success guarantees hard to achieve.
- Continuous Spaces: Extending high-level reasoning to continuous, noisy, real-world robotics remains a major frontier, with PDDL+ and Hybrid Planning serving as initial steps.
Summary updated