Unifying and Certifying Top-Quality Planning


  • Michael Katz IBM T.J. Watson Research Center, Yorktown Heights, USA
  • Junkyu Lee IBM T.J. Watson Research Center, Yorktown Heights, USA
  • Shirin Sohrabi IBM T.J. Watson Research Center, Yorktown Heights, USA




The growing utilization of planning tools in practical scenarios has sparked an interest in generating multiple high-quality plans. Consequently, a range of computational problems under the general umbrella of top-quality planning were introduced over a short time period, each with its own definition. In this work, we show that the existing definitions can be unified into one, based on a dominance relation. The different computational problems, therefore, simply correspond to different dominance relations. Given the unified definition, we can now certify the top-quality of the solutions, leveraging existing certification of unsolvability and optimality. We show that task transformations found in the existing literature can be employed for the efficient certification of various top-quality planning problems and propose a novel transformation to efficiently certify loopless top-quality planning.




How to Cite

Katz, M., Lee, J., & Sohrabi, S. (2024). Unifying and Certifying Top-Quality Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 319-323. https://doi.org/10.1609/icaps.v34i1.31490