Red-Black Heuristics for Planning Tasks with Conditional Effects

Michael KatzAAAI 2019 · OpenReview

Abstract

Red-black planning is a state-of-the-art approach to satisficing classical planning. Red-black planning heuristics are at the heart of the planner Mercury, the runner-up of a satisficing track in the International Planning Competition (IPC) 2014 and a major component of four additional planners in IPC 2018, including Saarplan, the runner-up in the agile track. Mercury’s exceptional performance is amplified by the fact that conditional effects were handled by the planner in a trivial way, simply by compiling them away. Conditional effects, however, are important for classical planning, and many domains require them for efficient modeling. Consequently, we 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 outperform the variants that compile this feature away, improving coverage on tasks where black variables exist by 19%.

Introduction: The Challenge of Conditional Effects

In classical AI planning, the goal is to find a sequence of actions that transitions a system from an initial state to a target goal. A common technique for estimating the distance to the goal is "delete relaxation," which optimistically assumes that once a fact becomes true, it never becomes false. While computationally efficient, this often leads to poor heuristics.

Red-black planning provides a more nuanced approach by partitioning state variables into "red" (relaxed/optimistic) and "black" (strict/realistic). This hybrid model yields more accurate heuristics. However, real-world problems often involve conditional effects—actions whose outcomes depend on the current state (e.g., "if the door is locked, the 'open' action fails; otherwise, it succeeds").

Historically, planners handled these by "compiling them away," multiplying out every possible condition into a separate action. This "compilation tax" often leads to an exponential explosion in the number of actions, causing planners to exhaust memory before the search even begins. This research introduces native support for conditional effects within the red-black heuristic, bypassing the need for pre-compilation.

Methodology: Native Support and RSE-Invertibility

The core of the proposed approach lies in extending the mathematical framework of red-black planning to handle "if-then" logic directly. This involves three primary technical shifts:

  1. Generalized Invertibility: For red-black planning to remain tractable, "black" variables must be "invertible"—meaning any change can be undone without violating other conditions. The authors introduced a generalized definition of RSE-invertibility that accounts for conditions that only trigger under specific circumstances.
  2. Algorithm Adaptation: The algorithm for computing red-black plans was modified. Instead of selecting a generic action to achieve a goal, the system now selects a specific effect of an action and recursively satisfies both the action's preconditions and the specific effect's conditions.
  3. Structural Integration: Conditional logic is integrated directly into Domain Transition Graphs (DTGs) and Causal Graphs.
Figure 2: Illustration of conditional effects in planning, showing (a) a task fragment, (b) a transition with conditional logic (oc), and (c) the resulting causal graph dependencies.

Empirical Evaluation

The authors tested their native support (NS) approach against the traditional "multiply out" (MO) compilation using a suite of 679 tasks across 32 domains, including standard International Planning Competition (IPC) benchmarks.

Key Findings

  • Overcoming the Compilation Tax: In 243 of the 679 tasks, the MO method failed entirely because the compiled task was too large for memory. The NS approach successfully handled these cases.
  • Increased Coverage: The NS approach solved 438 tasks, a significant improvement over the 314 tasks solved by the MO baseline.
  • Heuristic Accuracy: In 155 tasks, the heuristic was so precise that the very first "red-black plan" generated was a valid solution for the original problem, allowing for near-instantaneous solving.
  • Identifying Black Variables: By handling conditions natively, the planner could identify significantly more invertible variables, allowing more parts of the problem to be treated "strictly" (as black variables) rather than "optimistically" (as red variables).
Figure 6: Comparison of the number of invertible variables identified by native support vs. the 'multiply out' compilation method. Points above the diagonal indicate domains where native support found more black variables.

Conclusion and Future Directions

Native support for conditional effects represents a significant leap for red-black planning, offering a 19% increase in coverage and speedups of up to three orders of magnitude. By avoiding the memory-intensive compilation of effects, planners can maintain a more realistic model of the state space.

Future work will focus on handling "conflicting effects" (where two conditions attempt to set the same variable to different values) more strictly and extending support to "axioms" or derived predicates. Additionally, the authors suggest exploring automated "painting" strategies to optimally decide which variables should be red or black.

Summary updated

Abstract

Red-black planning is a state-of-the-art approach to satisficing classical planning. Red-black planning heuristics are at the heart of the planner Mercury, the runner-up of a satisficing track in the International Planning Competition (IPC) 2014 and a major component of four additional planners in IPC 2018, including Saarplan, the runner-up in the agile track. Mercury’s exceptional performance is amplified by the fact that conditional effects were handled by the planner in a trivial way, simply by compiling them away. Conditional effects, however, are important for classical planning, and many domains require them for efficient modeling.Consequently, we 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 outperform the variants that compile this feature away, improving coverage on tasks where black variables exist by 19%.
BibTeX
@inproceedings{katz2019red,
  author = {Michael Katz},
  title = {{Red-Black Heuristics for Planning Tasks with Conditional Effects}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=UrZOniWYSoo},
}

Loading related content...

Figure