Operator Counting and Potential Heuristics

Source slides: F8 Post-hoc Optimization, F9 Network Flow Heuristics, F10 Operator Counting, F11 Potential Heuristics

The previous chapter introduced a constraint view of heuristics: instead of constructing a plan, write down conditions that every plan must satisfy and minimize cost under those conditions. Operator counting makes this idea explicit. It introduces one variable for each operator, where that variable means “how many times this operator is used.”

Potential heuristics look very different at first. They assign numbers to facts and evaluate a state by summing the numbers for the facts that hold. The surprise at the end of the chapter is that these two views are closely connected. Operator counting gives a semantic, plan-summary view. Potentials give a fast state-evaluation view. Linear programming duality explains why they can express the same bounds.

The Question

This chapter answers a unifying question:

Can landmarks, flow constraints, abstraction combinations, and fast state potentials be understood as instances of one lower-bound framework?

The answer is yes. The ingredients are:

• variables $\text{Count}_o$ that summarize how often operators are used;
• linear constraints that every valid plan’s counts must satisfy;
• an LP objective that minimizes total operator cost;
• dual LP variables that can be read as potentials over facts.

The framework is useful because it separates correctness from strength. A constraint is allowed if every real plan satisfies it. The heuristic gets stronger when the constraint set captures more of what real plans must do.

Post-Hoc Optimization

Suppose we have several abstraction heuristics $h^1,\ldots,h^k$. Taking their maximum is always admissible, but it may leave useful information unused. Adding them directly is unsafe because two abstractions may charge the same operator cost.

Post-hoc optimization solves the cost split at evaluation time. Instead of choosing a fixed cost partition in advance, it asks for the best partition for the current state.

Definition: Post-hoc optimization

Given abstraction heuristics $h^1,\ldots,h^k$ and original cost function $c$, the post-hoc optimization heuristic is

$$h^{\text{pho}}(s) = \max \sum_{i=1}^{k} h_i^{Y_i}(s)$$

subject to

$$\sum_{i=1}^{k} Y_i(o) \le c(o) \quad\text{and}\quad Y_i(o) \ge 0$$

for every operator $o$ and every abstraction $i$.

Here $Y_i(o)$ is the amount of operator $o$‘s cost assigned to abstraction $i$. The constraint says that all abstractions together may not spend more than the real cost of any operator.

This dominates the simple maximum because the LP is free to put all cost on one abstraction if that is best. It may also split costs across several abstractions and obtain a larger admissible value. The price is computational: an LP may need to be solved for each evaluated state.

Network Flow as Operator Counts

Network flow heuristics are a first step toward operator counting. They treat a fact as something produced and consumed by operators.

For an FDR fact $\langle v,d\rangle$, an operator produces the fact if its effect makes $v=d$. It consumes the fact if it requires $v=d$ and changes $v$ to a different value. In any real plan, the total number of productions and consumptions must match the net change required between the current state and the goal.

A simplified balance equation is:

$$\text{produced}(\langle v,d\rangle) = \text{consumed}(\langle v,d\rangle) + \text{goal\_need}(\langle v,d\rangle) - \text{initial\_supply}(\langle v,d\rangle).$$

Each term can be expressed using operator-use counts. If $\text{Count}_o$ is the number of times operator $o$ is used, then productions of $\langle v,d\rangle$ are a sum over the counts of operators that make $v=d$ true. Consumptions are a sum over counts of operators that require $v=d$ and then change $v$ away from $d$.

The flow heuristic minimizes total cost subject to these balance constraints:

$$\min \sum_{o \in O} c(o)\cdot \text{Count}_o$$

with $\text{Count}_o \ge 0$ and the flow equations for all relevant facts.

The heuristic is admissible because the count vector of any real plan satisfies the equations. The LP may also allow fractional or otherwise plan-like-but-not-real count vectors, so its optimum can be optimistic. Optimism is exactly what admissibility permits.

Operator Counting Constraints

Operator counting abstracts the previous idea. We no longer require every constraint to be a flow equation. Any linear constraint over operator counts is allowed if every valid plan satisfies it.

Definition: Operator counting constraint

Let $\Pi$ be a planning task with operator set $O$. For a state $s$, an operator counting constraint is a linear constraint over variables $\text{Count}_o$ for $o \in O$ such that, for every valid plan $\pi$ from $s$, the assignment

$$\text{Count}_o = |\{i \mid \pi_i = o\}|$$

satisfies the constraint.

This definition deliberately says nothing about how the constraint is found. It only states the soundness requirement.

Important examples include:

• landmark constraints: if $L$ is a disjunctive action landmark, then $\sum_{o \in L} \text{Count}_o \ge 1$;
• flow constraints: production and consumption balance equations for facts;
• state equation constraints: linear equations describing the net change of variables through operator effects;
• abstraction-derived constraints: restrictions obtained from abstract transition systems.

The operator counting heuristic for a constraint set $\mathcal{C}$ is:

$$h^{\text{OC}}_{\mathcal{C}}(s) = \min \sum_{o \in O} c(o)\cdot \text{Count}_o$$

subject to all constraints in $\mathcal{C}$ and $\text{Count}_o \ge 0$.

Why Operator Counting Is Admissible

The admissibility proof is short but important.

Take any real plan $\pi$ from state $s$. Count how often each operator appears in it. By definition, those counts satisfy every constraint in $\mathcal{C}$. Therefore the LP has at least one feasible solution whose objective value is exactly the cost of $\pi$.

Since the LP minimizes over all feasible count vectors, its optimum cannot be larger than the cost of that plan. This is true for every valid plan, including an optimal one. Hence

$$h^{\text{OC}}_{\mathcal{C}}(s) \le h^*(s).$$

Adding constraints can only remove feasible LP solutions. Therefore it can only increase the optimum or leave it unchanged:

$$h^{\text{OC}}_{\mathcal{C}_1 \cup \mathcal{C}_2}(s) \ge \max\left( h^{\text{OC}}_{\mathcal{C}_1}(s), h^{\text{OC}}_{\mathcal{C}_2}(s) \right).$$

This is one of the main attractions of the framework. Landmark constraints and flow constraints do not have to compete; they can be placed in the same LP.

A Small Landmark Example

Suppose every plan must use at least one of two actions, $a$ or $b$, and their costs are $c(a)=3$ and $c(b)=5$. The disjunctive action landmark is

$$L = \{a,b\}.$$

The corresponding operator counting constraint is

$$\text{Count}_a + \text{Count}_b \ge 1.$$

If this were the only constraint, the LP would choose $\text{Count}_a=1$ and $\text{Count}_b=0$, giving lower bound $3$. This does not claim that action $a$ is actually sufficient to solve the task. It only says that any solution must pay at least the cheapest way to satisfy this necessary condition.

This example also shows why constraints must be interpreted carefully. Operator counting summaries are not plans. They are relaxed descriptions of unavoidable plan properties.

Potential Heuristics

Potential heuristics approach the same lower-bound problem from the state side. Instead of counting future operator uses, they give each fact a numeric weight and score a state by summing the weights of the facts that hold.

Definition: Potential heuristic

Let $\Pi$ be an FDR planning task with variables $\mathcal{V}$. A potential function assigns a real number $\text{pot}(v,d)$ to every variable-value pair $v=d$. The potential heuristic is

$$h^{\text{pot}}(s) = \sum_{v \in \mathcal{V}} \text{pot}(v,s(v)).$$

Evaluation is very fast. For each variable, look up the potential of its current value and add the numbers. This is $O(|\mathcal{V}|)$ once the potentials have been computed.

The hard part is choosing potentials that are admissible. Large positive potentials can make the heuristic informative, but if they are too large the estimate may exceed the true remaining cost.

Making Potentials Admissible

Potential heuristics are optimized under linear constraints. Three common types of admissibility constraints are used in the course.

First, a potential heuristic should be goal-aware:

$$h^{\text{pot}}(s) \le 0 \quad\text{for every goal state } s.$$

This prevents the heuristic from claiming positive remaining cost when the goal has already been reached.

Second, it may be constrained to be consistent. For every applicable operator $o$ taking $s$ to $s'$, require

$$h^{\text{pot}}(s) - h^{\text{pot}}(s') \le c(o).$$

This says that one transition cannot reduce the heuristic by more than the cost paid for that transition. Consistency implies admissibility for goal-aware heuristics.

Third, potentials may be constrained by delete-relaxation information, for example by requiring

$$h^{\text{pot}}(s) \le h^+(s)$$

for the relevant states or represented conditions. This ties the potential estimate to another known admissible bound.

In practice, the potentials are chosen by solving an LP. The constraints enforce admissibility, while the objective asks for high heuristic values on selected states or on the initial state.

Interpreting Potentials

A potential is not a reward and not a probability. It is a coefficient in a lower-bound function. Positive potential on a fact means that having that fact tends to increase the estimated remaining cost under the learned admissible bound. Negative potential can also occur, especially when a fact indicates progress or goal satisfaction.

For example, in a transportation task, a package being far from its destination might receive positive potential, while being at the destination might receive low or negative potential. The heuristic value is the sum across all variables, not an independent claim about each fact in isolation.

The common mistake is to read potentials causally: “this fact costs exactly this much.” That is too strong. Potentials are chosen jointly so that the whole sum respects the admissibility constraints.

Duality with Operator Counting

Operator counting and potentials seem to live on opposite sides:

• operator counting minimizes over future action counts;
• potential heuristics maximize over state-feature weights.

Linear programming duality connects them. Under the corresponding formulations, the potential LP is the dual of the operator counting LP. The constraints in one view become variables in the other, and the optimal objective values coincide when the LPs satisfy the usual duality conditions.

Theorem: Operator counting and potentials are dual views

The LP for an operator counting heuristic and the LP for the corresponding optimized potential heuristic are dual linear programs. Their optimal values are equal.

The practical interpretation is useful. Operator counting explains why a lower bound is valid: every plan must satisfy these count constraints. Potentials explain how to evaluate states quickly after optimization: sum the relevant fact weights.

Combining Constraint Sources

The operator counting framework can incorporate many earlier heuristics:

• landmark constraints capture disjunctive action landmarks, including those used by LM-Cut;
• flow constraints capture production-consumption balance;
• post-hoc optimization can be reformulated through cost-partitioning constraints;
• abstraction-derived information can add further restrictions on operator counts.

Combining them is straightforward in principle: put all valid constraints into one LP and minimize total operator cost. The combined heuristic dominates the versions that use only one constraint family, because the feasible region is smaller.

The limitation is runtime. Stronger LPs may be larger and more expensive to solve. Potential heuristics are one answer to this tension: spend more effort offline or during heuristic construction to obtain potentials, then evaluate states cheaply during search.

Chapter Summary

Operator counting heuristics introduce variables $\text{Count}_o$ for operator-use counts and minimize total action cost subject to linear constraints that every valid plan must satisfy. Landmark constraints, flow constraints, state equations, abstraction constraints, and post-hoc optimization all fit this view. The resulting LP optimum is admissible because every real plan’s count vector is feasible. Potential heuristics assign weights to variable-value pairs and evaluate a state by summing the weights of its current facts. Their admissibility is enforced through linear constraints such as goal-awareness and consistency. LP duality connects the two frameworks: operator counting gives the plan-count interpretation, while potentials give a fast state-evaluation form of the same kind of lower bound.

Check Your Understanding

1. Why does post-hoc optimization dominate taking the maximum of several abstraction heuristics?
2. What does $\text{Count}_o$ represent in an operator counting LP?
3. Give the operator counting constraint for a disjunctive action landmark $L$.
4. Why is the operator counting heuristic admissible even when LP variables are fractional?
5. How is a potential heuristic evaluated in a state?
6. What do goal-awareness and consistency prevent a potential heuristic from doing?
7. In plain words, what does LP duality say about operator counting and potential heuristics?