Red-Black Planning: A New Tractability Analysis and Heuristic Function

Authors

  • Daniel Gnad Saarland University
  • Joerg Hoffmann Saarland University

DOI:

https://doi.org/10.1609/socs.v6i1.18349

Keywords:

Heuristic search planning, Satisficing planning, Partial delete relaxation

Abstract

Red-black planning is a recent approach to partial delete relaxation, where red variables take the relaxed semantics (accumulating their values), while black variables take the regular semantics. Practical heuristic functions can be generated from tractable sub-classes of red-black planning. Prior work has identified such sub-classes based on the black causal graph, i.e., the projection of the causal graph onto the black variables. Here, we consider cross-dependencies between black and red variables instead. We show that, if no red variable relies on black preconditions, then red-black plan generation is tractable in the size of the black state space, i.e., the product of the black variables. We employ this insight to devise a new red-black plan heuristic in which variables are painted black starting from the causal graph leaves. We evaluate this heuristic on the planning competition benchmarks. Compared to a standard delete relaxation heuristic, while the increased runtime overhead often is detrimental, in some cases the search space reduction is strong enough to result in improved performance overall.

Downloads

Published

2021-09-01