Handling Infinite Domain Parameters in Planning Through Best-First Search with Delayed Partial Expansions

Ángel Aso-Mollar, Diego Aineto, Enrico Scala, Eva OnaindiaIJCAI 2025 · DOI

TL;DR

This paper introduces a novel best-first search algorithm, S-BFS, designed to tackle automated planning problems with infinite-domain control parameters. By employing delayed partial expansions and a probabilistic sampling approach, S-BFS effectively navigates these complex search spaces, offering a competitive alternative to existing methods.

What Problem Does This Paper Address?

Automated planning typically deals with discrete states and actions. However, real-world scenarios often involve continuous numeric parameters that influence action effects, such as the amount of fuel used or the force applied. While PDDL2.1 introduced numeric fluents, it restricted numeric arguments in actions to maintain finite state spaces. More recent proposals allow for "control parameters" – continuous numeric variables that planners can choose to set to achieve desired outcomes. Existing approaches often treat these parameters as constraints to be satisfied, typically using optimization solvers or SAT-based methods. This paper argues that these parameters should be treated as explicit decision points within the search space itself, leading to a more systematic and potentially more efficient planning process. The challenge lies in handling the infinite decision space introduced by these continuous parameters, which makes standard search algorithms intractable.

Methods

The core of this paper is the Sampling Best-First Search (S-BFS) algorithm. It's a modification of the traditional Best-First Search (BFS) designed for infinite decision spaces. The key innovations are:

  • Delayed Partial Expansions: Instead of fully expanding a state (which is impossible with infinite successors), S-BFS incrementally expands a subset of its successors. This is achieved through a sampling function ($\phi$) that defines a probability distribution over possible actions and control parameter assignments for a given state.
  • Rectification Function ($r_h$): To prevent states from being perpetually re-expanded and to manage the search effectively, a rectification function is introduced. This function adjusts the heuristic value (NEC) of a state based on the number of times it has been partially expanded. This is crucial for ensuring progress and eventual completeness.
  • Probabilistic Completeness: The paper proves that S-BFS, under certain conditions on the sampling and rectification functions, is probabilistically complete. This means that for any solvable problem, the probability of finding a solution approaches 1 as the number of search steps increases.
  • S-BFS Variants: The paper defines specific instances of S-BFS, such as S-G (using only heuristic value) and S-A (using heuristic plus accumulated cost), and explores different rectification functions (linear, quadratic, logarithmic).

Datasets

The paper uses domains introduced in the POPCORN planner (CASHPOINT, PROCUREMENT, TERRARIA) and four domains that are extensions of numeric IPC benchmarks (COUNTERS, BLOCKS-GROUPING, DRONE, SAILING). These extensions were created to allow for continuous increments/decrements of numeric variables. The authors also mention that the code for these domains is available.

Key Insights and Ideas

  • Treating Control Parameters as Decisions: The fundamental insight is shifting from viewing control parameters as constraints to be satisfied to treating them as explicit decision variables within the search space. This opens up new avenues for systematic search.
  • The Power of Delayed Expansion: The concept of delayed partial expansion, guided by sampling, is key to making infinite search spaces manageable. It allows exploration without the need for full enumeration.
  • Rectification for Progress: The rectification function is a clever mechanism to ensure that states don't get stuck in the priority queue indefinitely, balancing exploration and exploitation.
  • Logarithmic Rectification is Effective: The experiments show that logarithmic rectification functions lead to significant improvements in coverage, suggesting that a gradual increase in penalty is more beneficial than aggressive ones.
  • Sampling Strategy Matters: Systematic and uniform sampling strategies outperformed heuristic-guided sampling in their experiments, possibly due to the nature of the heuristic or the computational cost of heuristic-guided sampling.

Key Results

  • S-BFS, particularly with logarithmic rectification, demonstrates strong performance in terms of coverage (solving a higher number of instances) compared to baselines like NextFLAP and MCTS.
  • While S-A variants (which include accumulated cost) generally achieve higher-quality solutions (fewer actions), they solve fewer instances than S-G variants.
  • The paper proves the probabilistic completeness of S-BFS, a crucial theoretical property for search algorithms in infinite spaces.
  • A theoretical property is established: for S-A algorithms, the f-value of any non-leaf node in a subtree is bounded by the f-value of its root, providing an optimality bound for found solutions.

Limitations and Future Work

  • No Optimality Guarantees: The paper acknowledges that S-BFS does not guarantee optimality, especially for S-G variants. The rectification functions are designed to increase without bound, controlling the rate of re-expansions rather than ensuring the absolute best solution.
  • Heuristic Design for Infinite Spaces: The current work uses a goal-counting heuristic (hgc) and notes that existing numeric planning heuristics (like hFF or hMRP) are designed for finite spaces and are not directly applicable. Developing effective heuristics for infinite decision spaces is a significant area for future work.
  • Temporal Planning Integration: The authors plan to integrate their framework into temporal planning and extend it to handle continuous-time actions, as described in PDDL+.
  • Hybrid Systems: The work focuses on handling continuous parameters efficiently, and future research could explore how this integrates with hybrid systems that involve both discrete and continuous dynamics.

Summary updated

BibTeX
@inproceedings{asomollar2025handling,
  author = {Ángel Aso-Mollar and Diego Aineto and Enrico Scala and Eva Onaindia},
  title = {{Handling Infinite Domain Parameters in Planning Through Best-First Search with Delayed Partial Expansions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/940},
}
Figure