About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Artificial Intelligence
Paper
Red-black planning: A new systematic approach to partial delete relaxation
Abstract
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