Pricing Scarce Action Costs to Order Saturated Cost Partitioning

Optimal planners such as A* need a lower bound on the remaining cost to the goal, called an admissible heuristic. The strongest practical bounds come from adding up many small heuristics, each computed on a simplified version of the problem. Simply summing them can overcount, so the cost of each action is split among the heuristics. Saturated cost partitioning does this split one heuristic at a time. Each heuristic takes only the action costs it actually needs, and the remainder passes to the next heuristic. The method is fast, but its quality depends heavily on the order in which heuristics are served. A bad order lets an early, mediocre heuristic use up the costs that later heuristics needed. The current best ordering rule ranks each heuristic by its value divided by the total action cost it consumes. That rule treats every unit of cost as equally precious, which is the rule's weakness.

We propose to replace that uniform denominator with prices. The prices come from the linear-programming (LP) relaxation that defines the best possible cost partitioning. That LP has one capacity constraint per action, and its dual variable on that constraint says how much heuristic value one more unit of that action's cost would buy. Actions that no heuristic competes for have price zero, so consuming them should be free. Actions that many heuristics compete for are expensive. We compute these prices cheaply on a handful of states and use them to score heuristics during greedy order construction. The rule also handles negative cost assignments and breaks ties in a principled way, two problems that existing ratios leave open. We additionally use the measured gap between the greedy estimate and the LP bound to decide when an order is good enough.

Core Claim

Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning shows that, for a fixed set of abstractions, the order alone decides whether the saturated estimate is near zero or near optimal. That paper searches for good orders by hill climbing evaluated on sample states. Better Orders for Saturated Cost Partitioning in Optimal Classical Planning seeds that search with a greedy rule that ranks heuristics by value per unit of consumed positive cost. Its best variant, hybrid-opt, uses the slow dynamic version of the rule on the initial state and the fast static version (under 0.05 seconds) on sampled states. Neither paper looks at the structure of the relaxation that the greedy method approximates.

Our claim is that the optimal cost partitioning LP already tells us how scarce each action's cost is, and that scarcity is the missing ingredient in the ratio. Let $h_i(s, c)$ be heuristic $i$'s estimate for state $s$ under cost function $c$, and let $\mathrm{cost}(o)$ be the true cost of action $o$. The LP maximizes $\sum_i h_i(s, c_i)$ subject to $\sum_i c_i(o) \le \mathrm{cost}(o)$ for every action $o$. Write $y_o \ge 0$ for the dual price on action $o$'s constraint. The Lagrangian view of Lagrangian Decomposition for Classical Planning (Extended Abstract), which identifies these multipliers with cost partitions, then rewrites the problem as

$$ \max_{c_1,\dots,c_n} \; \sum_i \Big( h_i(s, c_i) - \sum_o y_o\, c_i(o) \Big) + \sum_o y_o\, \mathrm{cost}(o). $$

At the optimum, each heuristic's value exceeds the priced cost it uses. The quantity in parentheses is never negative, because giving the heuristic zero cost is always allowed and yields a nonnegative value. This suggests ranking heuristics by value per priced cost:

$$ r_y(h, c, s) = \frac{h(s, \mathrm{sat}_h(c))}{\epsilon + \sum_o y_o \, \mathrm{sat}_h(c)(o)}. $$

Here $\mathrm{sat}_h(c)$ is the saturated cost function heuristic $h$ consumes from the remaining costs $c$, and $\epsilon > 0$ avoids division by zero. Setting all $y_o = 1$ and dropping negative entries recovers the existing ratio. With prices, a heuristic that uses only uncontested actions ranks first, as it should. A heuristic that hands cost back through negative saturated costs is credited for doing so. Ties in raw cost are broken by which actions the cost comes from.

Research Program

The work has three parts.

Computing prices cheaply. Solving the optimal cost partitioning LP exactly is prohibitive: in Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning it solved only 531 tasks even with 24 hours. Two cheaper routes exist, and we treat both as sources of approximate prices. The first is subgradient optimization, which Lagrangian Decomposition for Classical Planning (Extended Abstract) reports reaches at least 90% of optimal quality within 200 iterations. Its multipliers are the prices directly. The second is the incremental column-generation scheme of Dantzig-Wolfe Decomposition for Cost Partitioning, whose master problem exposes dual prices and often reaches full quality in under a second. We compute prices on the initial state and a few sampled states, then average them or keep them per sample.

A known risk is that these LPs are highly degenerate, so the dual solution is not unique. We study how much this ambiguity changes the resulting orders. As a stabilization, we average prices across iterations or samples.

Using prices to order heuristics. We plug $r_y$ into both the static and dynamic greedy procedures of Better Orders for Saturated Cost Partitioning in Optimal Classical Planning. The scheme is unchanged; only the score differs. We then use the resulting orders as seeds for the existing hill-climbing and diversification machinery.

The hypothesis is that static greedy ordering with prices recovers most of what dynamic greedy ordering gains. Prices already encode the contention that dynamic recomputation discovers by repeatedly updating the remaining costs. If this holds, the expensive dynamic step that Better Orders for Saturated Cost Partitioning in Optimal Classical Planning needed for its best result would become unnecessary.

Using the gap as a stopping rule. On sample states where a price computation runs, we also obtain an approximate LP bound. The fraction $h^{SCP}(s)/h^{LP}(s)$ measures how much an order loses relative to the relaxation it approximates. We use this fraction to decide when diversification should stop adding orders. This is a secondary use, evaluated offline. The question is whether gap-based stopping matches the roughly 81 orders that Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning keeps while spending less time.

Relation to Prior Work

Several papers connect saturation and LPs but do not use LP duals to choose an order:

Online Saturated Cost Partitioning for Classical Planning generates orders during search. Our ordering rule can be dropped into its order generator unchanged.

Baselines

The naive reference point is saturated cost partitioning with a random order. Its estimates can collapse toward zero (Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning), so it anchors the scale. We also run the same paper's diversification over random orders, which reports 966.7 tasks on the IPC 1998–2014 suite.

The strongest existing competitor is hybrid-opt from Better Orders for Saturated Cost Partitioning in Optimal Classical Planning. It reports 1,048 solved tasks on the IPC 1998–2014 suite, ahead of the symbolic planner SymBA* at 1,008. It is the strongest competitor because it uses the same greedy skeleton we modify, differing only in the score. We rerun it in Fast Downward with identical abstraction collections, the same all saturator, the same 30-minute and memory limits, and the same diversification time budget.

The time spent computing prices is charged against our own diversification budget, not added on top. Beating hybrid-opt means solving more tasks under that matched budget. Alternatively, it means equal coverage with a pure static priced order, which would show the dynamic step is unnecessary.

For the online setting, the reference is Interval-10K from Online Saturated Cost Partitioning for Classical Planning, which reports 1,159 tasks on the IPC 1998–2018 suite. There we replace only its order generator.

The key ablation varies the source of the price vector $y$ while keeping everything else fixed, with five settings:

  • uniform $y$, which recovers the old ratio;
  • random positive $y$;
  • prices taken from an unrelated state;
  • prices from a truncated 20-iteration subgradient run;
  • prices from the Dantzig-Wolfe master problem.

If uniform and random prices perform as well as real ones, the duality story is wrong.

Why not just…?

Why not just keep more random orders and take the maximum? Random orders often yield near-zero estimates. The diversification results in Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning suggest that selected orders, about 81, beat a larger pool of random ones while costing less memory and evaluation time per node. We include random-order diversification as a baseline at matched order count and matched time.

Why not just use dynamic value-per-cost ordering everywhere? This is the real threat. Dynamic recomputation may capture contention just as well as prices do. Its known cost is speed: it repeatedly recomputes saturated costs, which is why Better Orders for Saturated Cost Partitioning in Optimal Classical Planning restricts it to the initial state. We compare four ordering variants (static unpriced, dynamic unpriced, static priced, dynamic priced) on initial-state estimates and on ordering time. If static priced ordering does not close most of the gap between the two unpriced variants, the proposal reduces to a tie-breaking improvement, and we will report it as such.

Why not just use the Lagrangian or LP cost partition directly as the heuristic? If a subgradient run reaches 90% of optimal quality, one might evaluate it per state and skip ordering altogether. Two pieces of evidence argue against this. First, per-state LP heuristics trail sequential saturation in coverage: 832 tasks for Versatile Cost Partitioning with Exact Sensitivity Analysis, against more than 1,000 for saturation methods on comparable suites. Second, an order transfers across states, whereas a cost partition computed for one state does not. We test this directly by including, in the maximum, the Lagrangian partitions computed at sample states. We measure whether they add value beyond the priced orders.

Why not just run hill climbing longer? Hill climbing from a good seed is already part of the pipeline. The question is whether priced seeds reach a given quality in less time. We plot the sample-state estimate quality reached against hill-climbing time for priced and unpriced seeds.

Proposed Experiments

We implement everything in Fast Downward, using Cartesian abstractions, pattern databases, and their combination, as in the cited saturation papers. We use two benchmark suites: IPC 1998–2014 (1,667 tasks) for comparison with hybrid-opt, and IPC 1998–2018 (1,827 tasks) for the online comparison.

Metrics are coverage, initial-state estimate $h(s_0)$, ordering time, and search expansions. On the subset of tasks where the Dantzig-Wolfe solver converges, we also measure the ratio of the saturated estimate to the LP bound on 1,000 sampled states.

Three outcomes would be decisive:

  1. With fixed abstractions and saturator, static priced ordering should give a higher $h(s_0)$ than static unpriced ordering on many more tasks than it loses, and it should come close to dynamic unpriced ordering.
  2. In the price ablation, real prices should clearly beat uniform and random prices.
  3. Coverage under the matched budget should match or exceed the reported 1,048 tasks.

A separate check targets negative costs. On configurations that allow negative saturated costs, priced ordering is defined, whereas the existing ratio must ignore those costs. We test whether that difference produces measurably better estimates.