Symbolic Top-k Planning

David Speck, Robert Mattmüller, Bernhard NebelAAAI 2020 · DOI

Abstract

Classical planning typically focuses on finding a single optimal solution. However, real-world constraints often necessitate a set of high-quality alternatives. This paper presents SYM-K, a symbolic search algorithm designed to find the $k$ cheapest plans. By utilizing Binary Decision Diagrams (BDDs) and a modified Dijkstra search, SYM-K overcomes the scalability limitations of existing explicit search methods. Experimental results across 73 IPC domains demonstrate that SYM-K maintains high coverage even as $k$ increases to 10,000, significantly outperforming state-of-the-art iterative and explicit planners.

Introduction

In automated planning, the "optimal" plan is often defined by a single cost metric. Yet, human preferences and dynamic environments frequently require multiple options. Top-$k$ planning addresses this by generating the $k$ best plans in increasing order of cost. While conceptually simple, finding multiple plans is computationally demanding. Existing approaches like $K^*$ or FORBID-K (which iteratively modifies the task to exclude previously found plans) often suffer from a "replanning tax" or struggle with large state spaces.

Methodology: The SYM-K Algorithm

The authors propose SYM-K, which integrates symbolic search into the top-$k$ framework. Symbolic search represents sets of states using Binary Decision Diagrams (BDDs), allowing for efficient manipulation of massive state spaces.

Algorithmic Innovations

SYM-K adapts the symbolic Dijkstra search with three key changes:

  1. Relaxed Pruning: Unlike standard search, SYM-K does not prune paths to a state once the first path is found, as subsequent paths may contribute to the top-$k$ global solutions.
  2. Exhaustive Reconstruction: Upon reaching a goal, the algorithm performs a greedy backward search through stored "closed" sets to extract all valid plans at that cost level.
  3. Termination Criteria: Search continues until $k$ plans are extracted or the state space is exhausted.

The paper also establishes the theoretical complexity of top-$k$ planning as PSPACE-complete, matching standard planning, but identifies it as PP-hard for polynomial-length plans, indicating a higher practical difficulty than simple plan existence.

Experimental Evaluation

The performance of SYM-K was evaluated against $K^*$ and FORBID-K using 73 domains from the International Planning Competitions (IPC).

k-coverage vs. number of plans (k) for various algorithms.

As shown in the figure above, SYM-K (particularly the bidirectional variant) exhibits superior scaling. While iterative methods like FORBID-K see a sharp decline in coverage as $k$ grows, SYM-K's performance remains nearly constant. This is because SYM-K performs a single search that naturally discovers plans in order, avoiding the overhead of repeated searches.

Detailed coverage results across IPC domains for k=1, 100, and 10,000.

The comprehensive results in the table above highlight that at $k=10,000$, SYM-K solved instances in 60 domains where it was the leader, compared to only 5 for FORBID-K. In many instances, the primary bottleneck was not the search itself, but the I/O overhead of writing thousands of plan files to disk.

Conclusion and Future Work

SYM-K demonstrates that symbolic search is a powerful paradigm for top-$k$ planning. By "harvesting" the multiple paths naturally explored by BDDs, it provides a scalable solution for generating high-quality plan sets. Future research will focus on integrating diversity metrics to ensure the $k$ plans are structurally distinct and optimizing memory usage for even larger state spaces.

Summary updated

BibTeX
@inproceedings{speck2020symbolic,
  author = {David Speck and Robert Mattmüller and Bernhard Nebel},
  title = {{Symbolic Top-k Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6552},
}
Figure