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

Red-black planning is a recent approach to partial delete re-laxation, where red variables take the relaxed semantics (ac-cumulating their values), while black variables take the reg-ular semantics. Practical heuristic functions can be gener-ated 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 vari-able relies on black preconditions, then red-black plan gen-eration 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 bench-marks. 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 re-sult in improved performance overall