Red-Black Heuristic for Planning Tasks with Conditional Effects

Red-black planning is the state-of-the-art approach to satisficing classical planning. A planner Mercury, empowered by the red-black planning heuristic, was the runner-up of the International Planning Competition (IPC) 2014. The exceptional performance of Mercury is amplified by the fact that conditional effects, a feature required to be supported in the competition, were handled by the planner in a trivial way, by simply compiling them away. Conditional effects, however, are important for classical planning, and many domains require them for efficient modeling.

Consequently, we herein investigate the possibility of handling conditional effects directly in the red-black planning heuristic function, extending the algorithm for computing red-black plans to the conditional effects setting. We show empirically that red-black planning heuristics that handle conditional effects natively favorably compete with the variant that compiles this feature away.