A Novel Iterative Approach to Top-k Planning


  • Michael Katz IBM Research, USA
  • Shirin Sohrabi IBM Research, USA
  • Octavian Udrea IBM Research, USA
  • Dominik Winterer University of Freiburg




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


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.




How to Cite

Katz, M., Sohrabi, S., Udrea, O., & Winterer, D. (2018). A Novel Iterative Approach to Top-k Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 132-140. https://doi.org/10.1609/icaps.v28i1.13893