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.