K∗ and Partial Order Reduction for Top-Quality Planning

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.