Frontier Search and Plan Reconstruction in Oversubscription Planning

Daniel MullerAAAI 2019 · DOI

Abstract

Oversubscription planning (OSP) requires agents to maximize total utility within a fixed budget. While Best-First-Branch-and-Bound (BFBB) is a common approach, it often suffers from computational redundancy when incorporating new information, such as landmarks, which typically necessitates a search restart. This paper presents a progressive frontier search framework that utilizes a "frontier compilation" technique. By transforming the search frontier into a set of entry points for subsequent iterations, the algorithm avoids redundant node generation and maintains continuous progression. Furthermore, a plan reconstruction method using frontier snapshots ensures that optimal paths can be recovered despite memory-efficient state pruning.

Introduction

In Oversubscription Planning (OSP), the objective is to select a subset of goals that maximizes total reward while adhering to strict resource constraints, such as time or fuel. Unlike classical planning where all goals must be met, OSP focuses on utility maximization.

The state-of-the-art approach, Best-First-Branch-and-Bound (BFBB), has been enhanced recently by the use of value-driven landmarks. However, a significant bottleneck remains: when new landmarks are discovered during search, existing methods often restart the search from the initial state to integrate this new heuristic information. This leads to the repeated exploration of the same early search space, wasting valuable computational resources.

Methodology: Frontier Compilation and Reconstruction

The authors propose prog-inc-compile-and-BFBB, an algorithm designed to eliminate search redundancy through two primary mechanisms: Frontier Compilation and Plan Reconstruction.

Frontier Compilation

The core innovation is the treatment of the search frontier—the set of states at the boundary of the explored region—as a starting point for future search iterations. Instead of discarding progress or keeping the entire search tree in memory, the algorithm performs a "compilation" ($̄{\Pi}$). This process creates a dummy initial state and a set of dummy actions that allow the search to "jump" directly to any state on the previous frontier at its original cost. This effectively allows the search to "teleport" to the furthest point of progress while benefiting from updated global heuristics.

Plan Reconstruction via Cross-lines

To maintain memory efficiency, frontier search typically discards interior nodes. To recover the full sequence of actions once an optimal goal state is reached, the authors implement a reconstruction technique using "cross-lines." These are snapshots of previous frontiers. By storing pointers to ancestors on these cross-lines, the algorithm can backtrack through the snapshots to piece together the complete plan.

Visual representation of search frontiers and the reconstruction process across different stages of the algorithm.

Theoretical Soundness and Insights

The proposed framework is backed by formal proofs. Specifically, Theorem 1 demonstrates that the frontier compilation is "optimal-preserving." This ensures that any optimal plan in the original task has a corresponding optimal plan in the compiled task, and vice versa, maintaining the integrity of the BFBB approach.

Key insights from this work include:

  • Efficiency vs. Memory: The approach strikes a balance between the slow, memory-efficient method of restarting and the fast, memory-intensive method of keeping the entire tree.
  • Scalability: The description of the compiled task grows linearly with the memory consumed by the search, suggesting good scalability for complex planning problems.

Conclusion

This research introduces a robust framework for incremental search in OSP. By leveraging frontier compilation, the algorithm avoids the computational waste of search restarts. While it introduces some implementation complexity and memory overhead for storing snapshots, the theoretical guarantee of optimality and the elimination of redundant node generation represent a significant step forward in efficient oversubscription planning.

Summary updated

BibTeX
@inproceedings{muller2019frontier,
  author = {Daniel Muller},
  title = {{Frontier Search and Plan Reconstruction in Oversubscription Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019999},
}
Figure