A Novel Iterative Approach to Top-k Planning

Abstract

While cost-optimal planning aims at finding one best quality plan, top-k planning deals with finding a set of solutions, such that no better quality solution exists outside that set. We propose a novel iterative approach to top-k planning, exploiting any cost-optimal planner and reformulating a planning task to forbid exactly the given set of solutions. In addition, to compare to existing approaches to finding top-k solutions, we implement the K∗ algorithm in an existing PDDL planner, creating the first K∗ based solver for PDDL planning tasks. We empirically show that the iterative approach performs better for up to a large required size solution sets (thousands), while K∗ based approach excels on extremely large ones.