Novel Is Not Always Better: On the Relation between Novelty and Dominance Pruning

Joschka Groß, Álvaro Torralba, Maximilian FickertAAAI 2020 · DOI

Abstract

Novelty pruning has become a cornerstone of modern automated planning, yet its theoretical foundations and relationship to other pruning techniques remain under-explored. This work bridges the gap between novelty pruning and dominance pruning by formalizing novelty as an "unsafe" approximation of dominance. We introduce LD-novelty, which utilizes label-dominance relations to prune states more effectively, particularly in domains where standard novelty is misled by resource consumption. Our empirical evaluation on International Planning Competition (IPC) benchmarks demonstrates that our unified framework leads to significant improvements in search efficiency and task coverage, outperforming current state-of-the-art planners.

Introduction

In automated planning, the primary challenge is navigating an exponentially large search space to find a sequence of actions that reaches a goal state. Two prominent techniques have emerged to address this: novelty pruning and dominance pruning. Novelty pruning focuses on states containing "novel" facts (variable-value pairs) not previously encountered. While highly effective, it is often considered a "magic bullet" without a clear theoretical explanation for its success. Conversely, dominance pruning is theoretically "safe"—it only discards states that are provably worse than others—but it is often too computationally expensive to find significant pruning opportunities in practice.

This paper addresses the gap in understanding why novelty works and how to mitigate its weaknesses, such as the "fuel trap," where a planner explores useless states simply because they have a new (but worse) resource level.

A Unified Framework: Novelty as Unsafe Dominance

The core insight of this research is the formalization of novelty as an "unsafe" approximation of dominance. By viewing novelty through the lens of dominance, the authors create a unified framework that allows for the systematic derivation of new pruning algorithms.

Theoretical hierarchy connecting novelty and dominance pruning.

As shown in Figure 1, standard novelty can be seen as a special case of dominance. This perspective reveals that novelty pruning is essentially dominance pruning where different states are allowed to "dominate" different parts of a new state. While this makes the pruning "unsafe" (potentially pruning the only path to a goal), it is computationally efficient and empirically robust.

Methods: LD-Novelty and Advanced Projections

Building on this unified framework, the authors introduce several key innovations:

  • LD-Novelty ($N^{LD}$): Instead of checking for identical facts, this method uses Label-Dominance (LD). A state is only considered novel if no better state (one that enables more or better plans) has been seen. This directly solves the "fuel trap": a state with less fuel is no longer considered "novel" if the same state with more fuel has already been visited.
  • Advanced Projections ($Q^{pre}$): While standard novelty looks at atomic facts in isolation, the authors propose looking at related variable pairs, such as those appearing together in action preconditions.
  • New Priority Function ($N^-$): For states that are not novel, a new ranking system based on the number of dominating states provides a nuanced "confidence" score for the search process.

Experimental Evaluation

The proposed methods were implemented in the Fast Downward planning system and tested on STRIPS domains from the International Planning Competitions (IPC) up to 2018.

Comparison of task coverage across different novelty and projection configurations.

The results, summarized in Figure 6, demonstrate the effectiveness of the unified approach. The best configuration using advanced projections ($Q^{pre}$) achieved a total coverage of 1658 solved tasks, surpassing top-tier planners like Dual-BFWS (1628) and MERWIN (1637). Furthermore, LD-novelty was found to reduce state expansions by up to three orders of magnitude in certain domains without sacrificing the ability to find solutions.

Conclusion

By reframing novelty as an unsafe approximation of dominance, this work provides both a theoretical foundation for novelty pruning and a practical path toward more efficient planning algorithms. The introduction of LD-novelty and advanced projections significantly improves the state-of-the-art, demonstrating that a deeper understanding of the relationship between these two pruning techniques can lead to more robust and powerful automated planners.

Summary updated

BibTeX
@inproceedings{gro2020novel,
  author = {Joschka Groß and Álvaro Torralba and Maximilian Fickert},
  title = {{Novel Is Not Always Better: On the Relation between Novelty and Dominance Pruning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6541},
}
Figure