Beyond Red-Black Planning: Limited-Memory State Variables

Authors

  • Patrick Speicher Saarland University
  • Marcel Steinmetz Saarland University
  • Daniel Gnad Saarland University
  • Jörg Hoffmann Saarland University
  • Alfonso Gerevini University of Brescia

DOI:

https://doi.org/10.1609/icaps.v27i1.13805

Abstract

Red-black planning delete-relaxes only some of the state variables. This is coarse-grained in that, for each variable, it either remembers all past values (red), or remembers only the most recent one (black). We herein introduce limited-memory state variables, that remember a subset of their most recent values. It turns out that planning is still PSPACE-complete even when the memory is large enough to store all but a single value. Nevertheless, limited memory can be used to substantially broaden a known tractable fragment of red-black planning, yielding better heuristic functions in some domains.

Downloads

Published

2017-06-05

How to Cite

Speicher, P., Steinmetz, M., Gnad, D., Hoffmann, J., & Gerevini, A. (2017). Beyond Red-Black Planning: Limited-Memory State Variables. Proceedings of the International Conference on Automated Planning and Scheduling, 27(1), 269-273. https://doi.org/10.1609/icaps.v27i1.13805