On Partial Satisfaction Planning with Total-Order HTNs


  • Gregor Behnke Universiteit van Amsterdam
  • David Speck Linköping Universitet
  • Michael Katz IBM
  • Shirin Sohrabi IBM




Classical planning techniques and analysis, Knowledge representation for planning and scheduling, Theoretical foundations of planning and scheduling


Since its introduction, partial satisfaction planning (PSP), including both oversubscription (OSP) and net-benefit, has received significant attention in the classical planning community. However, hierarchical aspects have been mostly ignored in this context, although several problem domains that form the main motivation for PSP, such as the rover domain, have an inherent hierarchical structure. In this paper, we are taking the necessary steps for facilitating this research direction. First, we formally define hierarchical partial satisfaction planning problems and discuss the usefulness and necessity of this formalism. Second, we present a carefully structured set of benchmarks consisting of OSP and net-benefit problems with hierarchical structure. We describe and analyze the different domains of the benchmark set and the desiderata that are met to provide an interesting and challenging starting point for upcoming research. Third, we introduce various planning techniques that can solve hierarchical OSP problems and investigate their empirical behaviour on our proposed benchmark.




How to Cite

Behnke, G., Speck, D., Katz, M., & Sohrabi, S. (2023). On Partial Satisfaction Planning with Total-Order HTNs. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 42-51. https://doi.org/10.1609/icaps.v33i1.27177