Loopless Top-K Planning
DOI:
https://doi.org/10.1609/icaps.v32i1.19823Keywords:
Planning, Top-k Planning, Symbolic SearchAbstract
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