Anytime Admissible Heuristics from Interior-Point Cost Partitioning

Optimal classical planning searches a huge graph of world states with A, a best-first search that is guaranteed to return the cheapest plan only if its heuristic never overestimates the remaining cost. Such a heuristic is called admissible. One of the most informative admissible heuristics is optimal cost partitioning*. It splits each action's cost among several simplified models of the problem so that their estimates can be summed without overestimating, and it finds the best split by solving a linear program (LP) at every state. That per-state LP makes it far too slow to use. Search time is roughly the number of expanded states times the time spent per state, and the LP inflates the second factor much faster than it shrinks the first. On the International Planning Competition (IPC) benchmark, the LP-based heuristic solves 531 tasks in 24 hours, while a greedy approximation solves 966 in 30 minutes (Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning).

This note proposes changing what the LP solver hands back to the search. The constraints of the cost-partitioning LP do not depend on the state being evaluated; only the objective does. So every feasible point of the LP is a valid cost partition, and it gives an admissible estimate for every state at once. A logarithmic barrier method keeps its iterate strictly inside the feasible region at every step. It adds a $-\log(\text{slack})$ penalty that grows without bound as any constraint is approached. We therefore keep one strictly interior point shared across the whole search, and spend a small, adjustable number of barrier Newton steps tilting it toward each state's objective. Every intermediate iterate yields a provably admissible value, so the per-state LP becomes an anytime computation. The search can stop it after zero, one, or ten steps depending on whether the extra accuracy could change which state is expanded next.

Core Claim

Let $x$ collect the cost-partition variables and abstract goal distances, and let $P=\{x : Ax \le b\}$ be the cost-partitioning polytope encoding "the per-abstraction costs sum to at most the true cost" and "abstract distances satisfy shortest-path inequalities." For a search state $s$, let $w_s$ be the 0/1 vector that selects, in each abstraction, the distance variable of the abstract state $s$ maps to. Then for any $x \in P$, the value $h(s;x) = w_s^\top x$ never overestimates the true remaining cost, and optimal cost partitioning is $\max_{x\in P} w_s^\top x$. We instead approximately follow the barrier subproblem

$$x_s(\mu) = \arg\max_{x} \; w_s^\top x + \mu \sum_j \log\big(b_j - a_j^\top x\big),$$

where $a_j^\top x \le b_j$ is the $j$-th constraint and $\mu>0$ is the barrier weight. We warm-start from a shared interior point $\bar{x}$ or from the parent state's iterate, and take $k_s$ damped Newton steps. Each step is computed matrix-free with conjugate gradient (CG), an iterative linear solver that only needs matrix-vector products.

The claim is threefold. First, every iterate is admissible by construction. Second, a handful of steps from a good shared interior point recovers most of the gap between the greedy and the optimal heuristic. Third, deciding $k_s$ lazily is a principled version of the "dynamic heuristic effort" that the research file flags as missing. Lazily here means we refine a state only when it reaches the front of the queue, and only until its bound exceeds the next competitor's.

Prior work does not provide this construction. The cost-partitioning literature solves the per-state LP with simplex or column generation, as in Dantzig-Wolfe Decomposition for Cost Partitioning, and treats the LP as a black box returning an optimum. Dual Interior-Point Optimization Learning motivates our approach. It shows that interior-point ideas plus guaranteed feasibility turn approximate LP outputs into valid bounds, using a log-barrier training loss and closed-form dual completion on power-flow LPs. It never puts such bounds inside a search, and it relies on a learned network where we use an iterative solver whose admissibility is exact rather than learned.

Research Program

The first component is the shared-polytope solver. We will build it inside Fast Downward on the abstraction sets used by the cost-partitioning comparisons: projections to two variables (SYS2), projections to three variables (SYS3), and Cartesian abstractions. The method follows A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees, which minimizes a barrier objective using only Hessian-vector products, a capped CG inner solver, and a single fixed barrier weight. We borrow that "one-shot $\mu$" design and the slack-based scaling.

Two cautions apply. The paper's complexity guarantees cover only simple bounds $x\ge 0$, while our constraints are general linear inequalities, so we claim no complexity result. And because our barrier is linear-plus-log, the Hessian is $\mu A^\top D^{-2} A$, where $D$ is the diagonal matrix of constraint slacks. That makes Hessian-vector products two sparse multiplies.

Admissibility must survive floating point. Because iterates stay strictly interior, we will enforce a minimum slack margin and verify $Ax\le b$ in exact or directed-rounding arithmetic before reporting a value. If the check fails, we fall back to the previous verified iterate. As a separate check, we will compare the result against CPLEX/HiGHS-solved optima on sampled states.

The second component is the initial interior point $\bar x$. It is computed once before search, either as the barrier point for an averaged objective over sampled states or as a strictly interior shrinkage of a saturated cost partition. Both are cheap. Seeding from a saturated partition means the method can never start worse than the greedy baseline, modulo the shrinkage, which we will quantify.

The third component is lazy refinement inside A*. A newly generated state is inserted with the cheap value $w_s^\top x_{\text{parent}}$, which needs no LP work and is still admissible. When the state is popped, we take barrier steps until either its $f$-value exceeds the next queue key, in which case we reinsert it, or the CG-based estimate of the remaining gap becomes small. Here $f$ is the path cost so far plus the heuristic. This rule spends effort only where it can change what gets expanded, which directly targets the expansions-times-cost identity of Multi-Dimensional Heuristic Searching.

The fourth component is batching. Every state in the open list shares the same constraint matrix $A$, so barrier steps for many popped or near-front states can be batched as sparse matrix-matrix products on a GPU. Requiring one shared $A$ is a limitation for Batched First-Order Methods for Parallel LP Solving in MIP across heterogeneous branch-and-bound subproblems. Here it holds automatically. Batching is a secondary contribution; the core result must hold on CPU.

Two papers constrain the design. An NMPC Approach using Convex Inner Approximations for Online Motion Planning with Guaranteed Collision Avoidance reports that log-barrier solvers timed out in 11.3% of trajectory-planning scenarios because Newton systems become ill-conditioned near the boundary. Solving Constrained Variational Inequalities via a First-order Interior Point-based Method shows the complementary benefit: barrier paths move smoothly through the interior rather than oscillating. We deliberately never drive $\mu\to 0$. We accept a bounded suboptimality gap in exchange for well-conditioned systems, and we measure that gap explicitly. Driving $\mu$ to zero is what pushes iterates toward the boundary where the timeouts occur.

Baselines

The naive reference point is A with the canonical or blind heuristic, plus A with the barrier heuristic at $k_s=0$. The second evaluates every state with the fixed shared point $\bar x$ and does no per-state optimization. It is one cost partition used everywhere, and it shows what the shared interior point buys before any LP work is done.

The strongest existing competitor is diversified saturated cost partitioning, $h^{SCP}_{div}$, from Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning. It precomputes about 81 diverse greedy orders and takes the maximum over them per state, and it solved an average of 966.7 of 1,667 IPC tasks within 30 minutes. It is the method that actually wins the wall-clock contest that motivates this work, as confirmed by A Comparison of Cost Partitioning Algorithms for Optimal Classical Planning. We will run it from the authors' Fast Downward configuration with the same abstraction collections, the same 30-minute and memory limits, and the same preprocessing time accounting. That accounting charges both its order-optimization phase and our interior-point setup against the per-task budget. Beating it means higher coverage on the same 1,667 tasks. A tie in coverage with strictly fewer expansions on commonly solved tasks counts as a partial win, because it shows the bound is tighter at acceptable cost.

The exact-LP competitor is $DW_{incr}$ from Dantzig-Wolfe Decomposition for Cost Partitioning. It solves the optimal cost-partitioning LP by column generation and solved 305 more tasks than the monolithic LP solver for SYS2 and 87 more for SYS3. The file gives these gains only relative to the monolithic LP, not absolute coverage, so we will re-run it under our limits rather than quote a coverage figure. It represents "get the true optimum per state, but faster." We must beat it on coverage, and match its heuristic values within a reported gap.

The key ablation isolates feasibility-preserving warm-starts. We compare our barrier steps against an equal-budget anytime primal simplex. That variant starts from the previous optimal basis, which remains feasible because only the objective changes, and is capped at the same wall-clock per state as our $k_s$ steps. Both report admissible intermediate values, so this comparison tests whether interior iterates improve the bound more per unit time than vertex-to-vertex pivots. A second ablation replaces lazy refinement with a fixed $k$ per state. It tests whether the dynamic allocation, rather than the solver, produces the gain.

Why not just…?

Why not just add more orders to saturated cost partitioning? More orders do raise the maximum, but the cited work already found diminishing returns: diversification retained about 81 orders out of 200 while keeping accuracy. Each extra order also adds a full pass per state. SCP's values remain bounded by what greedy saturation can reach, and the remaining gap to the optimum is exactly what the "narrowing the gap" paper set out to close. Our experiment reports per-state heuristic values relative to the exact optimum, both for $h^{SCP}_{div}$ with 81 and 200 orders and for our method at matched time. If SCP with more orders closes the gap as fast as barrier steps do, the proposal fails, and we will say so.

Why not just warm-start a simplex solver from the parent's basis? This is the most serious threat. Because the polytope is state-independent, the previous optimal basis is primal-feasible for the new objective, and truncated primal simplex is also anytime admissible. Nothing in the file shows that it loses. The case for the barrier is that it improves the objective smoothly rather than in vertex jumps, and that it batches across states on a GPU without basis bookkeeping. Both are hypotheses. The matched-budget ablation above settles the question. If simplex wins, the useful finding is the shared-polytope lazy-refinement scheme itself, and we would report it with simplex as the inner solver.

Why not just batch PDHG on a GPU, as BATCHLP does? BATCHLP is the Primal-Dual Hybrid Gradient method, a first-order solver that alternates primal and dual updates. Batched First-Order Methods for Parallel LP Solving in MIP reports 12x to 488x speedups for strong branching. Its iterates are only approximately feasible, however, and need conservative safety margins to yield valid bounds. In A*, a bound that is invalid even by a rounding error breaks the optimality guarantee. We will run it as a batched competitor with a feasibility-restoring shrink toward $\bar x$ and measure how much bound is lost to the repair. If the repaired PDHG bounds match ours per unit time, the barrier's advantage reduces to convenience.

Proposed Experiments

All experiments use the 1,667 IPC tasks from the cost-partitioning comparisons in Fast Downward, with SYS2, SYS3, and Cartesian abstraction collections, 30-minute and fixed-memory limits, and setup time charged to each task. Metrics are coverage, expanded states on commonly solved tasks, total and per-state heuristic time, and heuristic quality as a percentage of the exact optimal value on sampled states.

The first decisive check is quality per unit time. For 10,000 sampled states per domain, we plot the admissible value achieved against time for barrier steps, warm-started simplex, $DW_{incr}$, repaired PDHG, and $h^{SCP}_{div}$. The proposal is supported only if the barrier curve dominates in the regime below roughly the per-state time that $h^{SCP}_{div}$ spends.

The second decisive check is end-to-end coverage against $h^{SCP}_{div}$'s reported 966.7 tasks and our re-run of $DW_{incr}$, with and without lazy refinement.

The third check is about robustness. We record admissibility violations caught by the exact feasibility check, which should be zero after fallback, and Newton or CG stalls as a function of $\mu$. This tests whether a fixed moderate barrier weight avoids the boundary slowdowns reported for trajectory optimization.

A final, secondary experiment runs batched GPU refinement of the top of the open list. It measures whether throughput gains appear once the frontier is large.