Who Said We Need to Relax All Variables?

Abstract

Despite its success in both satisficing and optimal planning, thedelete relaxation has significant pitfalls in many important classesof planning domains, and it has been a challenge from the outset todevise heuristics that take some deletes into account. Weherein devise an elegant and simple method for doing just that. In thecontext of finite-domain state variables, we define red variables to take the relaxed semantics, in which they accumulate their values rather than switching between them, as opposed to black variables that take the regular semantics. Red-black planning then interpolates between relaxed planning and regular planning simply by allowing a subset of variables to be painted red. Of course, this relaxation is useful as a basis for devising heuristic functions only if the resulting red-black planning task is polynomial-time solvable. We herein investigate the tractability region of red-black planning, extending Chen and Gimenez' characterization theorems for regular planning to the more generalred-black setting. In particular, we identify significant islands of tractable red-black planning, opening the road to the efficient computation of very powerful heuristics.