Certifying Downward Refinement with Hierarchy-Ordered Decision Diagrams

Hierarchical planners split a planning problem into layers. They first solve a coarse version that ignores low-level details, then fill in those details. This pays off only when every coarse plan can actually be completed. That guarantee is the downward refinement property (DRP): every valid abstract plan has a valid concrete refinement, so the planner never has to throw away low-level work and go back up the hierarchy. The classical tests for DRP are syntactic and were built for one narrow kind of abstraction, where some preconditions are simply dropped. For the multi-valued state variables used by modern planners, nobody can cheaply check whether a candidate hierarchy has the property. As a result, hierarchical planning has largely been replaced by flat search.

A separate line of work studies binary decision diagrams (BDDs), compressed graphs that represent huge sets of states. Their size depends heavily on the order in which variables are tested. Symbolic planners choose this order with flat graph heuristics that know nothing about hierarchies. This note argues that the two problems are one problem. If a BDD tests variables in hierarchy order, with the most important variables first, then each abstract state becomes a separate sub-diagram. The DRP connectivity condition then becomes an ordinary symbolic reachability computation inside each sub-diagram. That makes DRP mechanically checkable for arbitrary finite-domain hierarchies. The same computation also measures how long refinements can get, which targets the known failure mode where DRP holds but plans blow up exponentially.

Core Claim

Fix a hierarchy: a partition of the state variables into levels $L_1,\dots,L_k$, with $L_1$ the most important. At level $i$, define the restricted transition relation

$$T_i(s,s') = T(s,s') \wedge \big(s|_{L_1\cup\dots\cup L_i} = s'|_{L_1\cup\dots\cup L_i}\big).$$

Here $T$ is the concrete transition relation and $s|_{X}$ is the state $s$ restricted to the variables $X$. In words, $T_i$ allows only concrete moves that leave every level-$\le i$ variable unchanged. The relation is computed over a mutex-pruned over-approximation of the reachable states.

Bacchus and Yang's necessary connectivity condition is stated in The Downward Refinement Property for precondition-dropping abstractions. Generalized to this setting, it asks the following. For every pair of consecutive abstract operators $(o,o')$, every concrete state produced by $o$ must reach, via the transitive closure $T_i^*$, some state satisfying the concrete preconditions of $o'$ that agrees on all level-$\le i$ variables.

When the BDD places the level-$\le i$ variables above all others, the equality constraint in $T_i$ splits the relation into independent blocks, one per abstract state. The closure is then computed inside each block. Its size is governed by the width of the diagram at the level boundary, not by the full joint state space. Because connectivity is demanded from a superset of the reachable states, a positive answer is a sound certificate. A negative answer may reject some hierarchies that are actually valid.

The fixpoint also yields a second quantity for free. The number of image iterations $d_i$ needed to close $T_i^*$ is an exact bound on the longest refinement segment at level $i$. Bäckström and Jonsson show in Planning with Abstraction Hierarchies can be Exponentially Less Efficient that a hierarchy can satisfy DRP yet force exponentially long refinements, and that choosing a plan-length-optimal hierarchy is NP-hard even to approximate. Capping $d_i$ and rejecting hierarchies that exceed the cap does not solve that hard problem. It gives a cheap, instance-specific detector for exactly the pathology in their $\Sigma_n$ family.

What is new is the pairing of three things: hierarchy-aligned variable ordering as the enabling representation, symbolic DRP certification for multi-valued variables, and refinement-depth screening.

Relation to Prior Work

The motivating gap comes from two lines of work that never meet.

On the hierarchy side, Knoblock's ordered monotonicity in Search Reduction in Hierarchical Problem Solving builds hierarchies by forbidding lower levels from undoing higher-level literals. Bacchus and Yang's syntactic DRP checks do the same job, but both were designed for precondition elimination. Gregory et al. in Exploiting Path Refinement Abstraction in Domain Transition Graphs extend refinement to domain transition graphs, the per-variable graphs of value changes. They prove DRP only under structural restrictions (unary effects, accessible causal chains). Their system is explicit and incomplete when those restrictions fail, for example under tight resources. This proposal reuses their abstract-and-conquer execution scheme, but replaces the structural restrictions with a check that runs directly on the actual transitions.

On the ordering side, Kissmann and Edelkamp in Improving Cost-Optimal Domain-Independent Symbolic Planning order BDD variables by approximating an optimal linear arrangement of the causal graph, which places causally linked variables next to each other. That arrangement is symmetric and flat. It cannot express that one variable must come before another for refinement to work. In Tower of Hanoi, for instance, ordering the big disk above the small disk is what makes the hierarchy valid.

Pipatsrisawat and Darwiche in New Compilation Languages Based on Structured Decomposability show that a variable tree (v-tree) controls compilation size. We take from them the idea that the shape of the variable structure should mirror the problem's decomposition. Here the decomposition is the hierarchy.

One prior result constrains the design. Cappart et al. in Improving Optimization Bounds Using Machine Learning: Decision Diagrams Meet Deep Reinforcement Learning show that the variable orders best for relaxed diagrams and those best for restricted diagrams diverge. This warns that a hierarchy-aligned order may be good for certification but bad for flat search. We therefore use a block-constrained order: levels are placed in hierarchy order, and the linear arrangement heuristic orders variables within each level. We then test whether the cross-level constraint costs anything.

Research Program

The work has three parts.

The first part is a certifier, built on the BDD and multi-valued diagram infrastructure of Symbolic Search for Cost-Optimal Planning with Expressive Model Extensions. It takes a task and a candidate hierarchy and returns three things: a DRP certificate per level (either complete or necessary connectivity), the depth profile $d_i$, and the BDD sizes at each level boundary.

The second part is a hierarchy search. It generates candidate hierarchies with two generators: Knoblock-style criticality layering, and domain-transition-graph clique grouping in the style of Gregory et al. It discards candidates that fail certification or exceed the depth cap. Among the survivors, it prefers hierarchies with small boundary width, because those have the fewest distinct low-level residual problems.

The third part is a planner. It commits to abstract plans only at certified levels, so refinement needs no backtracking there. It solves each refinement segment with symbolic search over the restricted relation $T_i$. At uncertified levels it falls back to flat symbolic bidirectional search.

The theory component is short. It states soundness of the certificate under over-approximated reachability. It also proves that with hierarchy-aligned ordering, the closure BDD is bounded by the sum over abstract states of their per-block closures. The proof is the cofactor decomposition induced by the equality constraint.

Baselines

The naive reference point is flat blind symbolic bidirectional search with the default static variable order. It shows whether any hierarchy machinery pays for itself.

The strongest existing symbolic competitor is SymBA* from Abstraction Heuristics for Symbolic Bidirectional Search. It uses abstractions only as heuristics, triggered lazily when the BDD exceeds 10 million nodes. It won the optimal track at IPC-2014 and solved 25 more problems than its blind baseline across 14 domains. It is the strongest competitor because it already rescues exploding BDD searches with abstraction, without any refinement guarantee.

The ordering baseline is GAMER's causal-graph linear arrangement. It reports 156 of 240 IPC 2008 sequential optimal instances solved, against 135 without its improvements (Improving Cost-Optimal Domain-Independent Symbolic Planning).

The hierarchical baseline is AR-FF from Gregory et al. On scaled Driverlog it solved tasks up to 400 locations where JavaFF failed beyond 150. Its plans were about 10% longer than optimal, and 50–100% longer on Goldminer.

All systems run on the same machines with the same time and memory limits, and certification time is charged to our planner. Each gets the same tuning budget: for SymBA*, the node threshold; for our planner, the depth cap and the hierarchy candidate count.

Since commit-to-abstract planning is not cost-optimal, the comparison is split by guarantee. Against AR-FF and flat satisficing search, beating the baseline means solving larger scaled instances with plan-length overhead below AR-FF's reported roughly 10%, and no Goldminer-style collapse. Against SymBA*, the claim is narrower and honest: matching its coverage where certification succeeds, while producing plans whose refinement never backtracks.

Two ablations isolate the key ingredient. The first runs the identical certifier under pure linear-arrangement ordering versus block-constrained ordering, and measures closure BDD size and certification time. The second drops the depth cap, to show its effect on $\Sigma_n$-like instances.

Why not just…?

Why not just use dynamic sifting, letting the BDD package reorder itself? Sifting repeatedly swaps adjacent variables to shrink the diagram. It optimizes size locally and is known to stall in poor local optima; BDD2Seq reports a 48.3× node-count gain over it in circuit synthesis. More importantly, sifting would freely move high-level variables below low-level ones and destroy the per-abstract-state blocks that make the certificate cheap. We include sifting as a separate run of the certifier. If it matches block-constrained ordering on closure size, the ordering half of the claim is wrong.

Why not just keep GAMER's flat linear arrangement, which already groups interacting variables? This is the real threat for flat search, which is why within-level order still uses it. The arrangement is symmetric, so it cannot encode the direction of refinement. The first ablation measures directly whether imposing the hierarchy across levels inflates diagrams. If certification is equally cheap under the flat order, alignment is unnecessary and the contribution reduces to the certifier alone.

Why not just refine lazily with counterexample-guided abstraction refinement (CEGAR)? CEGAR, in Counterexample-Guided Cartesian Abstraction Refinement, splits abstract states whenever an abstract plan proves spurious. It produces an admissible heuristic for full ground search, not a plan the planner can commit to. It reached 441 tasks against 450 for iPDB, a pattern-database heuristic, after tens of thousands of refinements. CEGAR answers a different question, though its Cartesian abstractions are a natural extra hierarchy generator, and we include them as such.

Why not just check DRP explicitly, as Gregory et al.'s structural conditions allow? Those conditions require unary effects. They fail on precisely the multi-variable, resource-coupled transitions where Gregory et al. report incompleteness. Explicit enumeration of low-level connectivity is exponential in the number of variables at each level. Symbolic closure is the only route we see that scales, and the scaled Driverlog experiment tests it.

Proposed Experiments

The decisive checks are four.

First, on the $\Sigma_n$ family from Bäckström and Jonsson and on Tower of Hanoi, the certifier must accept the good hierarchies and reject the exponential ones through the depth cap. It must also reproduce the direction-dependence of DRP that Bacchus and Yang found in Hanoi, where the good hierarchy gave a 10-fold time and memory gain in ABTWEAK.

Second, across the 1,667-task, 57-domain IPC set used in State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning, we report three things: the fraction of tasks with at least one certified non-trivial level, the certification time, and the closure BDD sizes under each ordering. This answers whether DRP is common enough in practice to matter.

Third, on scaled Driverlog/Roadlog up to and beyond 400 locations, we compare coverage, time, and plan length against AR-FF and flat symbolic search.

Fourth, on the IPC 2008 optimal track, we compare coverage against GAMER's 156/240, running blind bidirectional search and SymBA* on the same hardware.

The proposal fails if certification succeeds on almost no IPC domains. It also fails if block-constrained ordering inflates flat-search BDDs enough to erase the gains from committing to certified levels.