Some planners search by manipulating whole sets of world states at once. They store those sets as binary decision diagrams (BDDs): compressed graphs that represent a Boolean function by testing variables in one fixed order and merging identical sub-graphs. The order matters a great deal. A good one can keep a huge set down to a few thousand nodes, while a bad one can make the same set exponentially large. Hierarchical task network (HTN) planning is a different style of planning. The planner does not chain arbitrary actions. It repeatedly expands abstract tasks such as "deliver package" into subtasks, using a library of decomposition recipes called methods. The strongest cost-optimal planner for totally ordered HTNs, autoSym from Symbolic Search for Optimal Total-Order HTN Planning, combines the two ideas. It tracks the stack of pending tasks with finite automata and labels each automaton edge with a BDD holding the world states compatible with that stack. It solves 242 of 465 benchmark instances, against 174 for the best SAT-based planner. Its authors nevertheless say plainly that it uses basic variable orderings and that choosing good ones is still open.
This note proposes building the BDD variable order from the task hierarchy rather than from the flat action model alone. The intuition is simple. In hierarchical search, a world-state set is always paired with a specific pending task. A pending task such as "deliver p1 by truck t2" couples the variables touched by its whole decomposition subtree: truck location, package location, and the method's preconditions. These variables are correlated inside each edge BDD even when no single primitive action links them directly. An order that keeps each task's variables together should shrink the edge BDDs. The flat dependency graph that classical symbolic planners use cannot see this coupling.
Core Claim
In stack-based symbolic HTN search, the size of the BDDs is driven by correlations that the hierarchy creates between variables. Those correlations are invisible to the flat causal graph. The causal graph is the "which variable's change depends on which" graph over primitive actions. We claim that an ordering computed from a hierarchical interaction graph will reduce peak BDD size, and so increase coverage, in domains whose world-state structure is "counting-like" rather than "permutation-like." In this graph, two variables are linked in proportion to how tightly they are bound together under the same compound task. We also claim the method will give no gain in domains where the theory says no ordering can help, and that this pattern of gains and non-gains is itself a prediction we can check.
The flat counterpart is Improving Cost-Optimal Domain-Independent Symbolic Planning. That paper approximates an Optimal Linear Arrangement (OLA) of the causal graph, meaning a line ordering of the variables that keeps strongly linked ones close, and it raised GAMER from 135 to 156 of 240 IPC-2008 instances. It supplies our arrangement method. Its graph, however, is built only from primitive operators. We change the graph and keep the arrangement solver, so any gain can be attributed to the hierarchical edges. Limits and Possibilities of BDDs in State Space Search constrains what we can expect. It proves that permutation-style domains blow up under every ordering, while counting-style domains such as Gripper admit polynomial BDDs under dependency-respecting orders. We use this result to state in advance where gains should and should not appear.
Research Program
The first step is a sensitivity census, and it decides whether the project is worth pursuing. For every instance autoSym solves, and for those it fails on by memory, we rerun the planner under 20 random variable orders, the default order, and the flat causal-graph order. We then record the spread in peak edge-BDD nodes and in solve time. If the spread is small across most domains, ordering is not the bottleneck in hierarchical symbolic search, and the proposal ends there as a useful negative result. The census also separates two kinds of memory failure. One kind is BDD blowup, which ordering could fix. The other is automaton size, the "method explosion" the authors report for Barman, which no variable order can fix.
The second step builds the hierarchical interaction graph on autoSym's regularized model. In that model every method has at most two subtasks. For each compound task $t$, let $V_t$ be the variables appearing in the preconditions or effects of primitives reachable below $t$, together with the preconditions of $t$'s methods. Every pair $u,v \in V_t$ receives weight $1/|V_t|$. The point of this weighting is that small, tight tasks impose strong coupling, while near-root tasks that touch everything impose almost none. The final edge weight between two variables is
$$w(u,v) = \lambda \, c(u,v) + (1-\lambda) \sum_{t:\,u,v \in V_t} \frac{1}{|V_t|},$$
where $c(u,v)$ is the flat causal-graph weight and $\lambda \in [0,1]$ mixes the two sources. We then run the Kissmann–Edelkamp OLA approximation on $w$. Setting $\lambda = 1$ recovers their method exactly, which gives a clean ablation. Computing $w$ requires only reachability over the task hierarchy, which is already done during grounding. We expect it to take seconds, as the flat version does.
The third step is analysis. For each domain we ask whether the hierarchical term mainly reorders variables within causal-graph clusters or joins clusters that the flat graph keeps apart. We then check whether that predicts the observed node savings, and whether domains we would classify as permutation-like show no gain, as the theory predicts.
Baselines
The naive reference point is autoSym as published, with its default ordering. Its reported result is 242 of 465 instances on the 21-domain suite that includes the IPC 2020 total-order HTN benchmarks (Symbolic Search for Optimal Total-Order HTN Planning). We rerun it on our hardware rather than relying on the published number.
The strongest ordering competitor is the flat causal-graph OLA order of Kissmann and Edelkamp, computed on the grounded primitive actions. This is the obvious thing to try first, and nothing hierarchy-specific should be needed if it already works. It is also exactly our method with $\lambda = 1$, so comparing against it isolates the hierarchical term. We also run the purely hierarchical variant, $\lambda = 0$, and a small grid over $\lambda$. To rule out tuning bias, $\lambda$ is chosen on a held-out half of the domains and reported on the other half.
The third baseline is dynamic reordering by sifting in the BDD library, with its standard triggers. It reorders at run time with no domain knowledge at all.
The fourth baseline is a probe portfolio. It runs the first few cost layers under $k$ random orders, picks the order with the smallest BDDs, and continues with it. Its probing time comes out of the same total budget.
All configurations share the autoSym code base, BDD library, grounding, time limit, and memory limit. Ordering computation and probing count toward wall-clock time.
Beating the strongest baseline means two things. First, statistically higher coverage than the flat causal-graph order on the held-out domains. Second, a median reduction in peak edge-BDD nodes on commonly solved instances, without a loss in total runtime. For context, the cost-optimal SAT approach solved 174 instances on the same suite. Partial-order SAT-F reports 121 of 144 on a different benchmark set (Bringing Order to Chaos), which is not directly comparable to our suite.
Why not just…?
Why not just use the flat causal-graph ordering, since autoSym's actions are primitive anyway? This is the real threat. The flat graph is fully computable for autoSym, and it may capture most of the benefit. Our argument against it is mechanistic. Edge BDDs are conditioned on a pending task, so they carry correlations imposed by the hierarchy rather than by single actions. That is an argument, though, not evidence. The $\lambda$ ablation settles the question directly. If $\lambda = 1$ matches the best hierarchical setting on the held-out domains, we will report that hierarchy adds nothing and that the open problem named by Behnke and Speck is solved by transferring the flat method.
Why not just turn on dynamic sifting? Sifting needs no design effort. The file, however, reports severe runtime penalties for reordering during symbolic iterations, while static causal-graph orders take only seconds to compute (Improving Cost-Optimal Domain-Independent Symbolic Planning). In autoSym the problem is likely worse, because many edge BDDs are live at once. Our sifting baseline measures this directly. If sifting wins on coverage, that would show static structure is the wrong lever.
Why not just abandon BDDs for SAT-F or explicit heuristic search with relaxation heuristics? Both alternatives have been evaluated. On cost-optimal total-order HTN, the SAT approach trails autoSym, at 174 versus 242 instances. Explicit A* wins only on easy instances, and the integer-programming heuristic of Delete- and Ordering-Relaxation Heuristics for HTN Planning must be solved at every search node. Improving the strongest existing system is the more direct route. We do not claim ordering fixes Barman-style automaton blowup.
Why not just replace OBDDs with sentential decision diagrams whose variable tree mirrors the hierarchy? These diagrams, from Basing Decisions on Sentences in Decision Diagrams, can be exponentially smaller than BDDs under the same order. That makes them a natural next step, but they are a much larger engineering change, and choosing the variable tree is itself harder than choosing a linear order. If the census shows that linear ordering already leaves little room for improvement, the case for them weakens. If the hierarchical order helps, its interaction graph is a natural seed for building that tree.
Proposed Experiments
We run every configuration on the 465-instance total-order suite under identical limits. We report coverage per domain, peak and per-cost-layer edge-BDD node counts, ordering-computation time, and total time.
There are three decisive checks. The first is the census: is there meaningful variance across orders at all? The second is whether the hierarchical interaction graph beats flat OLA ($\lambda = 1$) on held-out domains, judged on both nodes and coverage. The third is whether the gains concentrate in counting-like domains and vanish in permutation-like and method-explosion domains, as the theory predicts. Barman is reported separately, with its failures classified as BDD failures or automaton failures. If the second check fails while the first succeeds, the conclusion is that flat orders suffice for hierarchical symbolic search. That would still close the question Behnke and Speck left open.
References
- Symbolic Search for Optimal Total-Order HTN Planning
- Improving Cost-Optimal Domain-Independent Symbolic Planning
- Limits and Possibilities of BDDs in State Space Search
- Bringing Order to Chaos - A Compact Representation of Partial Order in SAT-Based HTN Planning
- Delete- and Ordering-Relaxation Heuristics for HTN Planning
- Basing Decisions on Sentences in Decision Diagrams