How Much Pruning Does Factoring a Plan Into Per-Variable Transitions Throw Away?

Constraint-based planners treat "find a plan of $T$ steps" as a large puzzle. A constraint solver searches over the value of every state variable at every time step and rules out impossible values as it goes; this ruling-out is called propagation. The strongest such planners describe the world with multi-valued variables. A truck's location is one variable that takes one of $\{A, B, C\}$, instead of three true/false facts. The puzzle is then cut into one small constraint per variable describing which value changes are legal, drawn from that variable's domain transition graph (a graph of which values can follow which). This factoring keeps models small. It may also be quietly costly. A single action usually needs several variables to change together: an elevator must be at floor 3 for a passenger to board there. If each variable's constraint is checked on its own, the solver cannot see that no joint move is consistent, even when every variable individually has a legal move. Constraint programming has a name for this loss, the pruning gap, and has measured it carefully for global constraints. Nobody has measured it for planning transitions.

We propose to measure that gap directly and then close it with the cheapest representation that does the job. For each time step, we compile the joint step relation over a cluster of variables that actions couple, meaning the set of value combinations at $t$ and $t+1$ that some set of non-conflicting parallel actions can produce. We store it as a multi-valued decision diagram, a compressed layered graph of allowed tuples. We then propagate it as a binary constraint tree. Because the step relation is the same at every time step, it is compiled once and copied across the horizon. Our working hypothesis is that the domains where factored planners fail, with Miconic the clearest case, are exactly the domains with a large pruning gap at the step level, and that clustering only the variables an action couples recovers most of the lost pruning at a bounded memory cost.

Core Claim

The claim has two parts, and only the first is the main bet. The first part is that the granularity of the transition constraint, per-variable versus coupled-cluster, explains a large share of the per-domain variance in constraint-based planning performance. This share should be visible as a measurable pruning gap. The second, subordinate part is that a tree-structured encoding is the right way to propagate the clustered relation once it exists, because it keeps full pruning without the auxiliary-variable blow-up that counter-style decompositions pay.

To make "pruning gap" a number rather than a slogan, write $D_t^{\text{fac}}$ for the variable domains after propagating the factored per-variable tables at search node $t$, and $D_t^{\text{joint}}$ for the domains after enforcing full consistency on the clustered step relations. The gap at a node is

$$ g = \frac{|D^{\text{fac}}| - |D^{\text{joint}}|}{|D^{\text{fac}}|}, $$

the fraction of values the factored model keeps but the joint model removes. We report $g$ at the root of each horizon and averaged along search paths. If $g$ is near zero on a domain, the proposal predicts no speedup there. This prediction is falsifiable before any solver comparison is run.

Relation to Prior Work

The proposal builds most directly on Transition Constraints for Parallel Planning. That planner (TCPP) extracts a domain transition graph for each SAS+ variable and encodes it as a wildcard table, so that one row covers many compatible states. It propagates each table with Minion's SHORTSTR2 algorithm, solving 165 of 213 IPC instances but degrading on Miconic. TCPP enforces full consistency per table and never across coupled tables. We keep its formulation as the factored end of our spectrum and vary only the coupling granularity. Loosely Coupled Formulations for Automated Planning models planning as linked network flows over the same multi-valued variables. It rescues Miconic by hand with PathSC, a model that lets a variable change several times per step, and it resolves cross-variable conflicts with lazily added cuts rather than propagation. That paper motivates our work, since it is evidence that Miconic needs cross-variable reasoning. We differ in deriving the coupling automatically from action structure instead of reformulating by hand. CPlan is the older state-based CSP planner. It recovered strength through hand-written distance and capacity constraints for each domain, which we treat as a competing way to close the same gap.

Three papers supply the method and constrain the design. Encoding Multi-Valued Decision Diagram Constraints as Binary Constraint Trees shows that a decision diagram can be rewritten as a tree of binary constraints with hidden variables, such that ordinary arc consistency on the tree equals full consistency on the diagram. It reports the approach fastest on 71% of XCSP table instances and up to 12x faster than Compact Table. That work treats single, static, ad-hoc constraints. We apply it to relations that are copied across a growing horizon and coupled through shared variables, which it does not study. Compiling Constraint Networks into Multivalued Decomposable Decision Graphs supplies the compiler idea and a variable-ordering heuristic based on betweenness centrality. It also gives evidence that native multi-valued compilation beats Boolean translation: 131 against 83 instances compiled. A Generic Global Constraint based on MDDs proves that full consistency on a decision diagram conjoined with ALL-DIFFERENT is NP-hard. We take this as a design constraint rather than a contradiction. Compiling the conjunction into one diagram moves the hardness into diagram size, so we bound that size explicitly instead of pretending it away.

From the decomposition literature, Decomposition of the NVALUE constraint frames the trade we expect. Decompositions that keep full pruning tend to pay in space, $O(nd^2)$ auxiliary variables for its Pyramid encoding, rather than in time. Work on Ranking Constraints, The AllDifferent Constraint with Precedences, and Parallel Batch Scheduling With Incompatible Job Families Via Constraint Programming shows the generic failure: separately propagated pieces rediscover the same contradiction many times. Going Beyond Primal Treewidth for (M)ILP warns that one variable linked to everything, such as an elevator, wrecks standard graph decompositions. That warning predicts our hardest case.

Research Program

The first component is a measurement study that needs no new solver. On small instances from each IPC domain, we enumerate the joint step relation for clusters of increasing size, enforce full consistency on it, and compare the surviving domains against TCPP-style per-variable propagation. This gives the gap $g$ by domain, horizon, and cluster size. The study answers whether the gap exists and where, and it alone would be a publishable negative result if the gap turns out small everywhere.

The second component is clustering. We build the causal coupling graph, whose nodes are SAS+ variables and whose edges join variables that appear together in some action's preconditions or effects. We then choose clusters greedily under a budget on compiled diagram size, preferring edges that the measurement study shows carry gap. Variables with very high degree, like the Miconic lift, are the central difficulty. For these we test a star decomposition: one cluster per passenger, each containing the lift and that passenger. Because these clusters overlap only on the lift, the cluster graph is a tree, which keeps tree-based consistency guarantees within reach.

The third component is compilation and propagation. Each cluster's step relation is compiled once into a decision diagram, ordered by the betweenness-centrality heuristic. It is reduced with the binary-constraint-tree rules and instantiated at every step, sharing structure across steps. The step relation is time-invariant, so compilation cost does not grow with the horizon; only the copies do. We record memory per step so that the space side of the trade is reported, not hidden.

Baselines

The naive reference point is TCPP's own factored model, re-run in our harness. That means per-variable wildcard tables propagated by SHORTSTR2 in Minion, with the same incremental horizon loop. TCPP reports 165 of 213 instances solved on its 12-domain IPC suite (Transition Constraints for Parallel Planning). We will first reproduce coverage close to that figure on identical instances and limits before claiming anything. Beating this baseline means higher coverage overall and, specifically, higher coverage on Miconic. No per-domain Miconic number is reported in the file, so we will establish it ourselves.

The strongest existing constraint-based competitor is again TCPP, since it outperformed PaP2 (131) and the Fast Downward heuristic planner FDLMC (158) on that suite. We include FDLMC as the strongest non-constraint competitor. It is the reviewer's default and does not pay any formulation cost. All systems get the same CPU and memory limits, matched to TCPP's protocol. Beating FDLMC on coverage is not required for the scientific claim. It is required for any claim of practical relevance, and we will state the outcome either way.

The key ablation separates granularity from propagator. The same clustered joint relation is propagated three ways: as a flat table with SHORTSTR2, as a single decision-diagram constraint in the style of A Generic Global Constraint based on MDDs, and as a binary constraint tree. If all three recover the same coverage, the contribution is the clustering and not the encoding, and we will say so. A second ablation varies cluster budget from per-variable up to the largest compilable size. This traces the full pruning-versus-memory curve, in the spirit of the space penalty documented for NVALUE.

Why not just…?

Why not just let clause learning recover the lost pruning? This is the most serious threat. A SAT planner over SAS+ encodings, as in SAS+ Planning as Satisfiability, can learn the same cross-variable nogoods that joint propagation would derive up front. If it learns them cheaply, the gap is irrelevant in practice. The file reports no coverage numbers for that encoding on these domains. We therefore run it as a baseline, and we also give it our cluster relations as extra clauses through a support-style encoding. If plain learning matches the clustered CSP on Miconic, the gap is real but already handled, and our conclusion narrows to non-learning solvers.

Why not just add hand-written implied constraints, as CPlan did? CPlan closed much of this gap with domain-specific distance and capacity constraints and was very efficient. The authors wrote those constraints per domain, however, and the open question is whether the gap can be closed automatically from SAS+ input. We include automatically derived invariants, such as mutex and reachability distance constraints, as a cheaper competitor. Their remaining gap, measured by $g$, tells us whether clusters add anything beyond them.

Why not just hand-reformulate the hard domains, as PathSC does? PathSC in Loosely Coupled Formulations shows that allowing several transitions per step shortens Miconic horizons. That changes the semantics of a step, which is orthogonal to how a step is propagated. We test whether the two combine by running clustered propagation on top of a multi-transition step definition. A reformulation that fixes one domain by hand is not an account of why factored models fail. The gap measurement is meant to provide that account.

Why not just use a flat joint table? Compact Table-style algorithms are fast and simple. The propagator ablation above answers this question directly. If large clusters make flat tables explode in memory, that explosion is the reason for the diagram or tree encoding, which the BCT paper found to be over 2,000 times smaller after reduction on its benchmarks.

Proposed Experiments

The benchmark is TCPP's 12-domain, 213-instance IPC suite, including Blocks, Depot, Logistics, Zenotravel, and Miconic. To test generality on newer structure, we add selected domains from the 2014 IPC, such as CityCar, under its 5-minute Agile and 30-minute limits. The metrics are coverage, time to first plan, makespan, search nodes, compiled size, and peak memory per time step, alongside the gap $g$.

The decisive check is a correlation test fixed in advance. Across domains, the root-level gap $g$ measured on small instances should predict the coverage gain of clustered over factored propagation on large instances. Miconic should show both the largest gap and the largest gain. If the gap is large but the gain is absent, propagation cost is eating the pruning benefit, and the propagator ablation will show where. If the gain appears where the gap is small, our explanation is wrong, and something else, such as the effect of horizon length or the choice of value ordering, is driving the result. A second check is the memory curve. Under the star clustering, the lift-centred domains should stay within memory at horizons where a single all-variable diagram does not. This would show that the NP-hardness boundary from Tiedemann et al. can be avoided in practice by choosing what to conjoin.