Loopless Top-K Planning

Authors

  • Julian von Tschammer University of Freiburg
  • Robert Mattmüller University of Freiburg
  • David Speck University of Freiburg Linköping University

DOI:

https://doi.org/10.1609/icaps.v32i1.19823

Keywords:

Planning, Top-k Planning, Symbolic Search

Abstract

In top-k planning, the objective is to determine a set of k cheapest plans that provide several good alternatives to choose from. Such a solution set often contains plans that visit at least one state more than once. Depending on the application, plans with such loops are of little importance because they are dominated by a loopless representative and can prevent more meaningful plans from being found. In this paper, we motivate and introduce loopless top-k planning. We show how to enhance the state-of-the-art symbolic top-k planner, symK, to obtain an efficient, sound and complete algorithm for loopless top-k planning. An empirical evaluation shows that our proposed approach has a higher k-coverage than a generate-and-test approach that uses an ordinary top-k planner, which we show to be incomplete in the presence of zero-cost loops.

Downloads

Published

2022-06-13

How to Cite

von Tschammer, J., Mattmüller, R., & Speck, D. (2022). Loopless Top-K Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 380-384. https://doi.org/10.1609/icaps.v32i1.19823