On Stubborn Sets and Planning with Resources

Authors

  • Anna Wilhelm Saarland University
  • Marcel Steinmetz Saarland University
  • Jörg Hoffmann Saarland University

DOI:

https://doi.org/10.1609/icaps.v28i1.13877

Keywords:

Planning with Resources, Partial-Order Reduction, Stubborn Sets

Abstract

Stubborn sets are a well-established technique to admissibly prune permutable parts of forward search in classical planning. But what about planning with resources? The identification of effective stubborn sets relies on non-interfering actions. Yet, a priori, all actions affecting the same resource interfere. We show how to exploit the fact that, nevertheless, with commutativity of addition and subtraction, many resource-affecting action sequences are permutable. We design suitable notions of stubborn sets for planning with resources, with and without resource production. We show empirically, on classical IPC benchmarks with discrete resource variables, that our new pruning methods are often, and sometimes dramatically, superior to previous ones. Together with a novel way of automatically identifying the resource variables, this result holds under IPC conditions.

Downloads

Published

2018-06-15

How to Cite

Wilhelm, A., Steinmetz, M., & Hoffmann, J. (2018). On Stubborn Sets and Planning with Resources. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 288-296. https://doi.org/10.1609/icaps.v28i1.13877