AI Planning: A Primer and Survey (Preliminary Report)

Dillon Z. Chen, Pulkit Verma, Siddharth Srivastava, Michael Katz, Sylvie ThiébauxarXiv 2024 · OpenReview

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:

  1. Continuing/Episodic: No model access (standard RL).
  2. Generative: Access to a simulator (sampling).
  3. Analytic: Access to exact transition and reward functions.
  4. 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.

Levels of Generalization in AI Planning

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.

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

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.
BibTeX
@misc{chen2024ai,
  author = {Dillon Z. Chen and Pulkit Verma and Siddharth Srivastava and Michael Katz and Sylvie Thiébaux},
  title = {{AI Planning: A Primer and Survey (Preliminary Report)}},
  year = {2024},
  eprint = {2412.05528},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.05528},
}
Figure