AAAI Publications, Twenty-Eighth International Conference on Automated Planning and Scheduling

Font Size: 
A Novel Iterative Approach to Top-k Planning
Michael Katz, Shirin Sohrabi, Octavian Udrea, Dominik Winterer

Last modified: 2018-06-15


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.


Classical Planning; Top-k Planning; KSTAR; Plan Forbid Reformulation

Full Text: PDF