Downward Refinement for Actions with Context-Dependent Effects

Hierarchical planners solve a problem twice. They first find a rough plan in a simplified model that ignores some details, then fill those details in. This only pays off if every rough plan can actually be filled in. When some cannot, the planner must back up to the rough level, and that cross-level backtracking can make hierarchical planning exponentially worse than ordinary search. The classical guarantee against this failure is the downward refinement property: every valid abstract plan has at least one valid refinement at the next level down. Every known test for it, however, assumes operators whose effects are fixed lists. Real domains are full of conditional effects, meaning effects that fire only if some condition holds when the action runs. Moving a briefcase moves exactly the objects that are inside it. A switch lights the bulb only if power is present. When the hierarchy hides the variable that decides whether an effect fires, the abstract model cannot know what the action does, and the existing guarantees say nothing.

We propose a polynomial-time sufficient test for downward refinement in planning tasks with conditional effects. The idea is simple. At an abstract level, any conditional effect whose triggering condition mentions a hidden variable becomes an optional effect: the abstract planner may choose whether it fires. The low level must then be able to make the planner's choice true. It must be able to switch the hidden condition on, and also switch it off, without disturbing anything the abstract plan already established. We pair the test with a repair loop that promotes offending variables up the hierarchy until the test passes. The result is a hierarchical planner that refines natively through conditional effects with no cross-level backtracking, and a measurable account of when such hierarchies exist.

Core Claim

Bacchus and Yang (The Downward Refinement Property) gave three polynomial checks that guarantee downward refinement for hierarchies built by dropping preconditions (ABSTRIPS-style). The checks are complete independence, complete low-level connectivity, and necessary connectivity. They also reported a tenfold time and memory gain in Towers of Hanoi when the property held. Our claim is that these checks extend to conditional effects once two things are added.

The first addition is an angelic reading of hidden-condition effects. Angelic here means the planner, not nature, resolves the choice. We borrow this idea from Metaphysics of Planning Domain Descriptions, which uses angelic non-determinism to keep robot-level plans refinable through external geometric solvers. We apply it symbolically inside the planning model instead.

The second addition is a two-sided connectivity requirement on condition variables. Pednault's split between conditions that cause an effect and conditions that preserve a variable unchanged (Generalizing Nonlinear Planning to Handle Complex Goals and Actions with Context-Dependent Effects) tells us both directions matter. An abstract plan that relies on an effect not firing is just as fragile as one that relies on it firing.

Concretely, call a variable hidden at level $i$ if the hierarchy assigns it below $i$. For each effect $c \rightarrow e$ (condition $c$ triggers effect $e$) where $c$ contains hidden variables, the check requires the following. From any concrete state matching an abstract state on the plan, a low-level path must exist that makes $c$ true. Another must exist that makes $c$ false. Neither path may touch any variable visible at level $i$.

One corollary falls out immediately for the factored tasks of Abstraction Heuristics for Factored Tasks. In those tasks, the effect on a variable $x$ may depend only on $x$ itself. A visible effect therefore never has a hidden condition, and the original Bacchus–Yang checks apply unchanged once each conditional effect is read as a set of transitions on $x$. We will prove this corollary and also use it as a sanity check on the implementation.

Relation to Prior Work

The closest existing work uses abstraction over conditional effects only for search guidance. Abstraction Heuristics for Classical Planning Tasks with Conditional Effects builds over-approximating abstractions. It refines them with counterexample-guided abstraction refinement (CEGAR), a loop that splits abstract states wherever an abstract plan fails concretely. The output is an estimate of distance to the goal for flat A* search. That work motivates ours in two ways. It shows that computing exact abstractions with conditional effects is NP-hard. Its over-approximations also deliberately admit spurious abstract paths, which is acceptable for a heuristic and fatal for a hierarchy. We reuse its idea of a refinement loop but change its target. Our loop repairs the hierarchy until abstract plans become refinable, rather than until distance estimates rise.

On the refinement side, Exploiting Path Refinement Abstraction in Domain Transition Graphs obtains refinability from abstractions over each variable's transition graph. It explicitly requires actions that change a single variable and excludes conditional effects, and it cannot backtrack when a bad abstract path is chosen. We generalize the class of tasks it covers.

Two further papers prove refinability guarantees but leave the computational question open. Abstraction in Situation Calculus Action Theories proves that sound abstractions admit backtrack-free refinement, but assumes deterministic high-level actions and gives no compiled test. Downward Path Preserving State Space Abstractions shows that exactly deciding refinability-style properties is PSPACE-hard. That result constrains us: we aim only for a sufficient, polynomial test, accepting that it will sometimes reject hierarchies that were in fact fine.

Two results explain why refinability matters so much. Planning with Abstraction Hierarchies can be Exponentially Less Efficient shows that badly structured hierarchies can be exponentially slower than flat search. The Expected Value of Hierarchical Problem-Solving models the cause. If a fraction $p$ of abstract plans refine and each abstract step has $B$ candidate refinements, then for $1/B < p < 1$ the work grows like $(pB)^n$, where $n$ is the number of levels. A hierarchy that silently ignores hidden conditions is a natural way to land in that bad middle range. The test we propose is meant to push $p$ to 1.

Research Program

The work has three parts.

The first part is theoretical. We will define the angelic abstract semantics for conditional effects. We will prove that the extended connectivity checks imply downward refinement. We will prove the factored-task corollary, and show by counterexample that one-sided (enable-only) connectivity is not sufficient. Every check reduces to reachability questions inside the projection onto the hidden variables, with the visible variables frozen. This keeps the checks polynomial in the size of those projections, by the same argument Bacchus and Yang use, and therefore practical whenever the projections are small.

The second part builds hierarchies automatically. We start from a variable ordering derived from a causal graph, a directed graph in which an edge links two variables when one influences the other. We add an edge from every condition variable to its effect variable, which mirrors Knoblock's ordered-monotonicity construction (Search Reduction in Hierarchical Problem Solving). The repair loop then runs the check. On failure, it returns the failing condition as a counterexample and promotes the responsible hidden variables one level. It stops when all levels pass or the hierarchy collapses to a single level. Collapse is itself a useful, reportable outcome.

The third part is the planner. At each level it uses native regression through conditional effects (Non-Deterministic Planning With Conditional Effects) to avoid compiling effects away, and it refines the abstract plan level by level. Every abstract choice of whether an optional effect fires becomes a subgoal at the level below.

Baselines

The naive reference point is flat search with no hierarchy. We will run it in two forms: the strongest optimal configuration and a satisficing flat search under identical limits.

The strongest existing method on this benchmark is the Cartesian-plus-pattern-database configuration with saturated cost partitioning, written $C^{fBS}_B$ in Abstraction Heuristics for Classical Planning Tasks with Conditional Effects. That paper reports that it solves 1,270 of 1,963 tasks, and 341 tasks on the general-conditional-effects subset. Symbolic bidirectional search solves 1,211 and 316 respectively, and LM-Cut solves 1,062 overall, in the same paper.

$C^{fBS}_B$ is optimal and our planner is not, so we will compare it on coverage at the same time and memory limits. We will report our plan costs as a ratio to the optimal costs it finds. Beating it means higher coverage on the subset of domains where the repair loop finds a nontrivial hierarchy, at a cost ratio comparable to the roughly 10% overhead reported by Gregory et al. It also means no loss of coverage elsewhere when we fall back to flat search.

The third baseline compiles conditional effects into ordinary operators and then applies the original Bacchus–Yang checks with ABSTRIPS refinement. On the compiled tasks we will also run Gregory et al.'s Abstract-and-Refine method. Both get the same hierarchy-construction time budget as our method.

The key ablation removes the two-sided check. In this naive hierarchy, abstract effects with hidden conditions are treated as always firing, and the planner backtracks across levels on failure. A second ablation keeps enable-side connectivity only. A third swaps our repair loop for skeletons taken from Pozo–Seipp-style over-approximating abstractions. These ablations isolate whether the angelic semantics and the off-side requirement are what deliver the gains.

Why not just…?

Why not just compile conditional effects away and use the classical checks? Compilation multiplies the number of operators exponentially in the number of conditions. That is exactly why permutation puzzles and Rubik's Cube are modeled with conditional effects in the first place (Solving the Rubik's Cube with a PDDL Planner). There is a subtler problem too. Splitting an action by context forces the abstract level to pick which split version it uses, which reintroduces the hidden-variable commitment in a different form. The compiled baseline will measure both the blowup and whether its checks pass less often than ours on the same domains.

Why not just use flat search with the best heuristic? This is a real threat. On permutation puzzles every variable interacts with every other, and we expect our repair loop to collapse the hierarchy to a single level there, leaving flat search the winner. The case for hierarchy rests on scaling families with weakly coupled structure. Gregory et al. report flat JavaFF failing beyond 150 Driverlog locations while their refinement planner reached 400. We will build analogous scaling families with conditional effects: Briefcase with growing object counts and Miconic with growing floors. We will report the crossover size honestly, including domains with no crossover.

Why not just hand-write hierarchical task networks or refinement mappings? Hand-authored hierarchies offer no guarantee. Under the branching-process analysis, an authored hierarchy with intermediate refinability can lose to flat search. Comparing against hand-authored hierarchies would also measure authoring effort rather than the method. We therefore limit ourselves to automatically built hierarchies, and we report the measured $p$ for the naive ablation, which stands in for a plausible-looking but unchecked hierarchy.

Why not just refine lazily and backtrack when an abstract plan fails? That is precisely the naive ablation. If its measured refinement rate is close to 1 on most domains, the two-sided check adds little, and we will say so.

Proposed Experiments

We use the 1,963-task conditional-effects suite and its 431-task factored subset from the two abstraction-heuristic papers. To these we add the six ADL domains from Safe Learning of PDDL Domains with Conditional Effects: Satellite, Miconic, Briefcase, Citycar, Maintenance and Nurikabe. We also use Towers of Hanoi as a replication of Bacchus and Yang. No reported result was found on Lacuna for hierarchical planners on any conditional-effects benchmark, so the hierarchical numbers will be new.

The metrics are coverage, node expansions, plan cost ratio, number of cross-level backtracks, and the empirical refinement rate $p$. We estimate $p$ by sampling abstract plans at each level and attempting refinement with unlimited backtracking.

Four checks decide the outcome. First, every hierarchy that passes the test must show zero cross-level backtracks on every task. A single counterexample falsifies the theorem or exposes an implementation bug. Second, the naive ablation's $p$ should fall inside the Bacchus–Yang intermediate range on domains with hidden conditions, and its node expansions should grow with the number of levels as their model predicts. Third, the enable-only ablation should fail on constructed tasks where an unwanted effect must be suppressed, for example a Briefcase task in which an object must stay behind. Fourth, we will report the fraction of domains where the repair loop yields at least two levels. If that fraction is small, the contribution narrows to a theory result plus the factored corollary. That would still answer an open question, though a smaller one.