Beyond Red-Black Planning: Limited-Memory State Variables

Book One

Volume

Proceedings of the International Conference on Automated Planning and Scheduling, 27

Main Track

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.

10.1609/icaps.v27i1.13805