K∗ and Partial Order Reduction for Top-Quality Planning

Michael Katz, Junkyu LeeSOCS 2023 · OpenReview

Abstract: Partial order reduction techniques are successfully used for various settings in planning, such as classical planning with A search or with decoupled search, fully-observable non-deterministic planning with LAO, planning with resources, or even goal recognition design. Here, we continue this trend and show that partial order reduction can be used for top-quality planning with K* search. We discuss the possible pitfalls of using stubborn sets for top-quality planning and the guarantees provided. We perform an empirical evaluation that shows the proposed approach to significantly improve over the current state of the art in unordered top-quality planning. The code is available at https://github.com/IBM/kstar.

Introduction

In many automated planning scenarios—ranging from malware detection to plan recognition—finding a single optimal path is insufficient. Instead, practitioners require top-quality planning: identifying all plans whose costs fall within a specific bound. However, a significant bottleneck in this process is the "redundancy of order." Many plans are functionally identical, differing only in the sequence of independent actions (e.g., "put on left shoe, then right shoe" vs. "put on right shoe, then left shoe").

In unordered top-quality planning, the objective is to find unique sets of actions that achieve the goal, ignoring these permutations. Existing planners like SymK and ForbidIterative often struggle with the exponential explosion of redundant orderings. This paper introduces $RK^*$, an algorithm that integrates Partial Order Reduction (POR) into the $K^*$ search framework to prune these redundancies efficiently.

The $RK^*$ Approach

The $RK^*$ algorithm builds upon the $K^*$ search algorithm, which combines $A^*$ search with Eppstein’s Algorithm to enumerate paths in a graph. To adapt it for unordered planning, the authors introduced two primary enhancements:

  1. Partial Order Reduction (POR) via Strong Stubborn Sets: POR identifies independent actions that do not interfere with one another. By using "strong stubborn sets," the search can explore only one specific ordering of independent actions. The authors rigorously prove that this technique is safe for unordered top-quality planning, ensuring no unique action sets are missed.
  2. Symmetry-Preserving Goal Transformation: $K^*$ search typically requires a single goal state. While a naive transformation (adding a dummy goal action) can break the pruning power of stubborn sets, the authors utilize a sophisticated transformation that preserves the original task's structure, maintaining the effectiveness of the POR.

Experimental Evaluation

The $RK^*$ approach was evaluated against a massive benchmark set consisting of 1,827 distinct planning tasks across 65 domains from the International Planning Competitions (IPC) between 1998 and 2018. The algorithm was tested with several standard heuristics, including LMcut, Merge-and-Shrink (M&S), CEGAR, and iPDB (interactive Pattern Databases).

Coverage over time for various planning configurations.

As shown in the performance curves, $RK^*$ consistently outperforms vanilla $K^*$ across various configurations. For short timeouts, $RK^*$ with LMcut performs best, while for longer runs, $RK^*$ with iPDB becomes the dominant choice, reaching near-maximal coverage well before the 30-minute limit.

Key Results

The empirical results establish $RK^*$ as the new state-of-the-art for unordered top-quality planning.

Overall coverage and pairwise comparison of planning algorithms.

As detailed in the coverage table, $RK^*$ using the iPDB heuristic achieved the highest overall coverage, solving 647 tasks. This is a substantial improvement over previous leading methods such as SymK (421) and ForbidIterative (341). The data also highlights that the standard strong stubborn set algorithms require no internal modifications to work in this context, provided the goal transformation is handled correctly.

Discussion and Future Work

While $RK^*$ represents a significant advancement, it is specifically tailored for unordered planning. If a user requires the $k$ best ordered plans, $RK^*$ is not directly applicable as it intentionally prunes those orderings. Additionally, while the search itself is faster, reconstructing the pruned orderings after the fact remains computationally expensive.

Future research will focus on reducing the pruning overhead in specific domains where the cost of calculating stubborn sets currently outweighs the search benefits, and exploring more efficient methods for plan reconstruction.

Summary updated

Abstract

Partial order reduction techniques are successfully used for various settings in planning, such as classical planning with A* search or with decoupled search, fully-observable non-deterministic planning with LAO*, planning with resources, or even goal recognition design. Here, we continue this trend and show that partial order reduction can be used for top-quality planning with K* search. We discuss the possible pitfalls of using stubborn sets for top-quality planning and the guarantees provided. We perform an empirical evaluation that shows the proposed approach to significantly improve over the current state of the art in unordered top-quality planning. The code is available at https://github.com/IBM/kstar.
BibTeX
@inproceedings{katz2023k,
  author = {Michael Katz and Junkyu Lee},
  title = {{K∗ and Partial Order Reduction for Top-Quality Planning}},
  booktitle = {SOCS},
  year = {2023},
  url = {https://openreview.net/forum?id=yhLND_D0vI},
}
Figure