Red–black planning: A new systematic approach to partial delete relaxation

To date, delete relaxation underlies some of the most effective heuristics for deterministic planning. Despite its success, however, delete relaxation has significant pitfalls in many important classes of planning domains, and it has been a challenge from the outset to devise heuristics that take some deletes into account. We herein devise an elegant and simple method for doing just that. In the context 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. We investigate the tractability region of red–black planning, extending Chen and Giménez' characterization theorems for regular planning to the more general red–black setting. In particular, we identify significant islands of tractable red–black planning, use them to design practical heuristic functions, and experiment with a range of “painting strategies” for automatically choosing the red variables. Our experiments show that these new heuristic functions can improve significantly on the state of the art in satisficing planning. 1