Purely Declarative Action Descriptions are Overrated: Classical Planning with Simulators

Guillem Francès, Miquel Ramírez, Nir Lipovetzky, Hector GeffnerIJCAI 2017 · DOI

TL;DR

This paper argues that traditional AI planning's reliance on declarative action representations (like PDDL) is overly restrictive. They introduce "black-box" planning algorithms that work directly with simulators, achieving performance comparable to state-of-the-art PDDL planners on standard benchmarks, opening new avenues for modeling complex problems.

What Problem Does This Paper Address?

Classical AI planning typically relies on declarative languages like STRIPS or PDDL to represent problems. These languages define states, actions (with preconditions and effects), and goals. While this structured representation allows planners to exploit problem structure for efficiency, it makes it difficult to plan in domains where dynamics are provided by simulators (e.g., video games like Atari, Minecraft) rather than explicit, declarative models. Many real-world problems are also hard to model declaratively. This paper investigates whether planning algorithms can achieve competitive performance by working directly with simulators, effectively treating action dynamics as black boxes, without access to their internal structure.

Methods

The core contribution is the development of domain-independent, "black-box" planning algorithms that operate on factored state models and simulators. These algorithms, collectively termed BFWS(R), are based on width-based search (BFWS). Unlike traditional planners that exploit action preconditions and effects, BFWS(R) only uses state and goal information. The key innovation is how they define "novelty" in a state, which guides the search. This novelty measure is adapted to work with simulators by using a fixed set of "potential subgoals" (R) derived from the initial state. Different choices for R are explored, including empty sets, all atoms, and sets derived from plans for individual goals. The algorithm BFWS(f5) is a state-of-the-art PDDL planner that uses a similar novelty measure but relies on delete-relaxation of the problem, which is unavailable from simulators. BFWS(R) aims to achieve similar performance without this reliance.

Datasets

The paper evaluates its algorithms on standard planning benchmarks, specifically all instances from the 2014 International Planning Competition (IPC) and instances from IPC 2011 domains not present in IPC 2014. Domains marked with '†' have fewer than three commonly-solved instances.

Key Insights and Ideas

  • Declarative Action Representations are Not Always Necessary: The paper demonstrates that competitive planning performance can be achieved without explicit knowledge of action preconditions and effects, challenging the long-held reliance on PDDL-like representations.
  • Simulators as First-Class Planning Targets: By developing algorithms that work directly with simulators, the paper significantly broadens the applicability of AI planning to a wider range of real-world problems and environments.
  • Width-Based Search Adaptability: The BFWS framework, originally designed for classical planning, proves to be surprisingly adaptable to black-box simulation environments by incorporating a notion of "potential subgoals" (R).
  • Modeling Flexibility: The ability to plan with simulators opens up new possibilities for modeling complex domains where declarative representations are cumbersome or impossible, such as those involving intricate physics or complex agent behaviors.

Key Results

The BFWS(R) algorithm, particularly with the R choice, achieved a coverage of 74.2% on the benchmarked problems, slightly outperforming the state-of-the-art PDDL planner LAMA (69.5%) and BFWS(f5) (74.5%). While not always achieving the highest coverage in every domain, BFWS(R) demonstrated competitive performance across a broad set of problems. In terms of average plan lengths, runtimes, and node expansions, BFWS(R) was comparable to LAMA and BFWS(f5), despite its "strong exploratory nature." The paper also shows that different choices for the set R can significantly impact performance, with some choices (like R0) being much weaker than others.

Limitations and Future Work

The authors acknowledge that while BFWS(R) performs well, it can struggle in domains with high "width" (many atomic goals) or tightly constrained plans. They also note that the computation of novelty measures in simulation mode can be more expensive than in propositional mode. Future work could explore more sophisticated ways to define and compute the set R, potentially inferring control knowledge from training data using machine learning algorithms. The paper also suggests that the flexibility offered by simulation-based planning could lead to radical changes in how planning problems are modeled and used.

Summary updated

BibTeX
@inproceedings{frances2017purely,
  author = {Guillem Francès and Miquel Ramírez and Nir Lipovetzky and Hector Geffner},
  title = {{Purely Declarative Action Descriptions are Overrated: Classical Planning with Simulators}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/600},
}

Loading related content...

Figure