Red-black relaxed plan heuristics reloaded

Despite its success, the delete relaxation has significant pit-falls. In an attempt to overcome these pitfalls, recent work has devised so-called red-black relaxed plan heuristics, where red variables take the relaxed semantics (accumulating their val-ues), while black variables take the regular semantics. These heuristics were shown to significantly improve over standard delete relaxation heuristics. However, the experiments also brought to light a major weakness: Being based on repair-ing fully delete-relaxed plans, the returned estimates depend on arbitrary choices made in such plans. This can lead to huge over-estimation in arbitrary subsets of states. Here we devise a new red-black planning method not based on repair-ing relaxed plans, getting rid of much of this variance. Our experiments show a significant improvement over previous red-black relaxed plan heuristics, and other related methods