Alternation-Based Novelty Search

Augusto B. Corrêa, Jendrik SeippProceedings of the International Conference on Automated Planning and Scheduling 2025 · DOI

TL;DR

This paper tackles the challenge of balancing exploration and exploitation in automated planning by combining two leading approaches: LAMA's heuristic alternation and BFWS's novelty search. Surprisingly, a direct combination proved detrimental, but a carefully simplified approach, dubbed NOLAN, emerged as a new state-of-the-art agile planner, significantly outperforming existing methods.

What Problem Does This Paper Address?

Automated planning aims to find a sequence of actions to reach a goal state from an initial state. A crucial aspect of planning algorithms, especially for "agile planning" (where speed is paramount), is how to effectively explore the vast search space while also exploiting promising paths. Two dominant strategies have emerged: LAMA's approach of alternating between different heuristic functions to guide the search, and Best-First Width Search (BFWS), which prioritizes states based on their novelty (i.e., containing unseen combinations of atomic facts). While both are powerful, combining them has been challenging, with previous attempts failing to yield significant improvements. This paper investigates how to effectively merge these two paradigms to create a more efficient agile planner.

Methods

The core of this work lies in exploring different ways to integrate BFWS's novelty search into LAMA's architecture.

  • LAMA: This planner uses multiple "open-lists" (data structures holding states to be explored), each ordered by a different heuristic. It cycles through these open-lists in a round-robin fashion.
  • BFWS: This approach prioritizes states based on their "novelty," measured by the smallest set of atomic facts not seen in previously explored states. More advanced versions (BFWS(f)) use "partition functions" and tie-breakers to refine this novelty measure.
  • Initial Combination (LAMA-W(f6)): The authors first attempt a direct integration by adding the most sophisticated BFWS novelty measure (BFWS(f6)) as an additional open-list to LAMA.
  • Ablation Study: Recognizing the initial combination's failure, they systematically simplify the BFWS component. This involves removing parts of the BFWS novelty measure, such as partition functions and tie-breakers, to understand which elements are beneficial.
  • Dynamic Width Selection: For BFWS, the novelty calculation involves a parameter 'k' (width). The paper introduces a dynamic approach to select 'k' based on the number of variables in a planning task, aiming to improve performance across different problem types.
  • NOLAN: The most successful combination, named NOLAN (Novelty, Landmarks, and AlternatioN), emerges from this simplification process. It uses a specific set of alternated open-lists, including a simplified novelty measure.

Datasets

The experiments were conducted on two benchmark sets:

  • Old IPC Tasks: A large set of 2502 tasks from 51 domains, used for developing and tuning the proposed planner.
  • New IPC Tasks: A more recent set of 360 tasks from 17 domains, used for evaluating the final planner against state-of-the-art competitors on unseen instances. The "Slitherlink" domain was excluded due to planner compatibility issues.

Key Insights and Ideas

  • Direct Combination is Not Always Better: The initial, seemingly straightforward, approach of adding the full BFWS novelty search to LAMA actually degraded performance. This highlights that simply merging complex components doesn't guarantee synergy.
  • Simplicity Wins: By systematically removing features from the BFWS novelty measure, the authors discovered that simpler novelty calculations, when integrated with LAMA's alternation, led to significant improvements. This suggests that the complexity of the novelty measure might be hindering performance in an alternated search.
  • hLM is Key for Novelty: The paper found that using the hLM heuristic within the novelty measure consistently outperformed using hFF, indicating its greater effectiveness in guiding novelty-based exploration in this context.
  • Dynamic Width is Crucial: Adapting the novelty width parameter 'k' based on task complexity (number of variables) proved more effective than using a fixed value, suggesting that the "granularity" of novelty detection should be task-dependent.

Key Results

  • NOLAN Achieves State-of-the-Art: The developed planner, NOLAN, significantly outperforms existing agile planners.
  • Improved Coverage and Speed: NOLAN achieved the highest coverage and agile score on the new IPC tasks, surpassing the winner of the IPC 2023 Agile Track by approximately 17% in agile score.
  • Dynamic Width Outperforms Fixed: The dynamic selection of the novelty width 'k' (specifically with a threshold of V=100 variables) consistently outperformed fixed-width BFWS(f6) across all metrics.
  • Ablation Study Success: Simplifications of the LAMA-W(f6) approach, particularly LAMA-W(fhLM), showed substantial improvements over the initial combination and even surpassed LAMA and BFWS(f6) individually.

Limitations and Future Work

  • Limitations of Novelty Measure: The paper notes that the direct combination of the strongest BFWS version with LAMA was detrimental, suggesting that the complexity of the novelty measure might need careful tuning or integration.
  • Future Work: The authors suggest further exploring how to dynamically select which parts of the BFWS novelty measure to use, potentially leading to even more efficient planners. They also hint at the possibility of further streamlining NOLAN's architecture. The dynamic width selection mechanism is also a promising avenue for future research.

Summary updated

Abstract

One key decision for heuristic search algorithms is how to balance exploration and exploitation. In classical planning, the two strongest approaches for this problem are to alternate between different heuristics and to enhance heuristics with novelty measures. The most well-known planner using alternation is LAMA, which cycles between different open-lists that are ordered using different heuristics. The strongest novelty-based algorithms use best-first width search (BFWS), which prefers states that contain previously unseen combinations of atoms. Considerable effort has been put into trying to combine these two approaches, but so far, no combination has been able to significantly improve over the individual planners. In this paper, we explore the simple idea of using BFWS as just another open-list for LAMA. Our results show that adding even the strongest BFWS version to LAMA is detrimental. However, combining only parts of each approach yields a new state-of-the-art agile planner.
BibTeX
@inproceedings{correa2025alternation,
  author = {Augusto B. Corrêa and Jendrik Seipp},
  title = {{Alternation-Based Novelty Search}},
  booktitle = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2025},
  doi = {10.1609/icaps.v35i1.36115},
}
Figure