Heuristics for Cost-Optimal Classical Planning Based on Linear Programming

1 Introduction

The central problem when designing an autonomous agent is the problem of selecting the next action for the agent to execute. In a truly autonomous system, this selection is based only on the sequence of the actions performed and observations gathered, called execution, up to the time a new action is needed. This problem is known as the control problem.

There are three main approaches for dealing with the control problem. In the first approach, the programming approach, the controller that selects the actions is hardwired in the form of a program or circuit that is specific for the task. This approach is used in simple problems or for agents that implement simple control strategies, but it often falls short of selecting appropriate actions when the agent encounters executions that were not anticipated by the 'programmer'. In the second approach, the learning approach, the agent is embedded in the system and learns the controller as it tries the different actions and observes their outcomes. In practice, however, the agent needs to explore too many executions to learn a useful controller making it unfeasible except for small tasks. In the third approach, the model-based approach, the system is described using a model that specifies the possible states of the system, the effects and observations obtained after executing the actions, and the goals that the agent tries to achieve. This model is used to automatically synthetise a controller that maps executions to the next action to perform. The problem is thus cast as a synthesis problem from a given specification. Two obstacles for this approach are that a suitable model for the task is needed, and that the synthesis problem is intractable in general. But, this intractability does not preclude the approach from being effective in meaningful cases. Planning is the model-based approach to autonomous behaviour. For a general introduction to planning models and methods along these lines, see Geffner and Bonet [2012].

† This paper was invited for submission to the Best Papers From Sister Conferences Track, based on a paper that appeared in the International Conference on Automated Planning and Scheduling (ICAPS) 2014.

Classical planning is the simplest type of model in which the initial state is fully known, the actions behave deterministically, and agent tries to achieve one of possibly many goal states. The determinism implies that the agent is capable of predicting the outcomes of the actions and, together with the knowledge of the initial state, a controller is just a sequence of actions to execute from the initial state and that results in a goal state. On the other hand, the synthesis problem for classical planning is the problem of finding a path in an implicit graph of exponential size whose vertices stand for system states and edges stand for action applications. In this graph, we can look for satisficing or (cost-)optimal plans that correspond to arbitrary or optimal paths in the graph.

In this paper we focus on the problem of computing optimal plans. A common way to find optimal paths in an implicit graph is the standard best-first search with an admissible heuristic (i.e. A∗ ). Such a heuristic must map states to cost estimates that are less than or equal to the cost of the best path from the state to a goal [Russell and Norvig, 2003].

Several recent admissible heuristics [van den Briel et al., 2007; Karpas and Domshlak, 2009; Bonet, 2013; Pommerening et al., 2013] for cost-optimal planning show that it is feasible and beneficial to obtain estimates by solving a linear program for every state encountered during the search. The approaches differ in their formulation of the objective and constraints, which depend on the type of information and problem structure that is exploited for the computation of the heuristics. Karpas and Domshlak use landmarks, Pommerening et al. exploit information from abstraction heuristics, and van den Briel et al. and Bonet base their linear programs on network flows for the state variables.

We will show that all these approaches are covered by a single framework that fixes the optimization function of the linear program. The framework provides:

• a clear and crisp formulation that is able to capture many of the existing state-of-the-art heuristics for optimal planning,
• a simple way to combine different heuristics (and thus different types of information) into new heuristics that are more powerful than the isolated component heuristics,
• new methods of analysis that allow us to better understand the limitations of the current heuristics and to reveal deep connections between heuristics, and
• a practical way to define heuristics that currently set the state of the art in heuristics for optimal planning.

Helmert and Domshlak [2009] provide the following classification for most of the heuristics for optimal planning, including all the heuristics that are state of the art:

• the delete relaxation [Bonet and Geffner, 2001],
• critical paths: the hm family [Haslum and Geffner, 2000],
• abstractions like pattern databases [Edelkamp, 2001], merge-and-shrink abstractions [Helmert et al., 2014] and structural patterns [Katz and Domshlak, 2009], and
• landmarks, like the admissible landmark heuristics of Karpas and Domshlak [2009].

As we will see, many of these heuristics can be captured efficiently in our framework, while for others we still do not know. Characterizing known heuristics within the proposed framework is not only of theoretical interest. The information provided by one heuristic can be easily combined with the information provided by other heuristics to define novel heuristics that often exhibit a synergistic effect: the new estimates are often strictly more informed than the estimates provided by each component alone.

Recently, the LP-based framework was used to express even better heuristics either by extracting more useful information from the problem or by observing novel ways to optimally combine the estimates provided by different heuristics [Bonet and van den Briel, 2014; Pommerening et al., 2015].

We start by introducing SAS+ planning and our new framework, which is based on operator-counting constraints. Afterwards, we present a wide range of such constraints and explain how they are used to express existing and novel heuristics. We then present some experimental results and end with a discussion. The reader is referred to Pommerening et al. [2014] for a more complete exposition and results.

2 The SAS+ Model and Heuristics

A SAS+task is a tuple Π = 〈V, O, sI , sG, cost〉 where V is a finite set of variables. Each variable V ∈ V has a finite domain DV . A (partial) state s is a (partial) variable assignment over V. We write vars(s) for the domain of definition of s and s[V ] for the value of V in s. A partial state s is consistent with a partial state s′ if s[V ] = s′ [V ] for all V ∈ vars(s′ ). An atom V = v is true in state s iff s[V ] = v.

Each operator o in the finite set of operators O is associated with a precondition pre(o) and an effect eff(o), which are both partial variable assignments over V. We require that V = v cannot be both a precondition and an effect of o. This is not a real restriction because such effects would be redundant.

The (complete) state sI is the initial state of the task and the partial state sG describes its goal. The cost function cost : O→R+0 assigns a non-negative cost to each operator.

An operator o is applicable in a state s if s is consistent with pre(o). The resulting state of applying an applicable operator o in state s is the state res(o, s) with

A sequence of operators π = 〈o1, . . . , on〉 is applicable in state s0 if there are states s1, . . . , sn with si = res(oi, si-1) for 1 ≤ i ≤ n. The resulting state of this application is res(π, s0) = sn. The cost of π is the sum of its operator costs cost(π) = ∑ni=1 cost(oi).

For state s, an s-plan is an operator sequence π applicable in s such that res(π, s) is consistent with sG. An sI-plan is just called a plan. A plan with minimal cost is called optimal.

A function h that maps states to non-negative numbers (or ∞) is called a heuristic. A heuristic h is called admissible if h(s) ≤ h∗ (s) for all states s, where h∗ (s) is the cost of an optimal s-plan (or ∞ if no s-plan exists).

3 Operator-counting Constraints

Recently proposed heuristics [van den Briel et al., 2007; Bonet, 2013; Pommerening et al., 2013] are based on linear programs of similar form. They formalize constraints that must be satisfied by every plan π and use a variable Yo for each operator o such that setting Yo to the number of occurrences of o in π satisfies the constraints.

We will show that these heuristics (and some other ones) can be covered by a common framework based on the notion of operator-counting constraints:

Definition 1 (Operator-counting constraints) Let Π be a planning task with operator set O, and let s be one of its states. Let Y be a set of non-negative real-valued and integer variables, including an integer variable Yo for each operator o ∈ O along with any number of additional variables. The variables Yo are called operator-counting variables.

If π is an s-plan, we denote the number of occurrences of operator o ∈ O in π with Y π o . A set of linear inequalities over Y is called an operator-counting constraint for s if for every s-plan π, there exists a feasible solution with Yo = Y π o for all o ∈ O.

A constraint set for s is a set of operator-counting constraints for s where the only common variables between constraints are the operator-counting variables.

As an example, C1 = {Yo1 - 2Yo2 ≥ 0} is an operatorcounting constraint expressing that in every plan, o1 must occur at least twice as often as o2. The set of inequalities C2 = {Yo1 - Z ≥ 2, Yo2 + Z ≥ 1} with auxiliary integer variable Z is another constraint. The set {C1,C2} is a constraint set because C1 and C2 do not share auxiliary variables.

Definition 2 (Operator-counting programs) The operatorcounting integer program IPC for constraint set C is:

The operator-counting linear program LPC is the LPrelaxation of IPC.

FromDefinition 1, if π is a plan, then there exists a solution to both IPC and LPC where Yo = Y π o for all o ∈ O. The cost of the plan is cost(π) = ∑o∈O cost(o) · Y π o , and hence the optimal plan cost is an upper bound for the objective value of the IP/LP. This allows us to define admissible heuristics:

Definition 3 Let Π be a planning task, and let C be a function that maps states s of Π to constraint sets for s.

The IP heuristic hIP C (s) is the objective value of the integer program IPC(s). The LP heuristic hLP C (s) is the objective value of the linear program LPC(s). Infeasible IPs/LPs are treated as having an objective value of ∞.

Note that the requirement that an operator-counting constraint must have a feasible solution with Yo = Y π o for every plan π is stricter than necessary for admissibility. It is sufficient that whenever a solution exists, there is one optimal plan π∗ such that all operator-counting constraints have a feasible solution with Yo = Y π∗ o .

If all operator costs of a planning task are integer, we can obviously improve the LP heuristic estimate without losing admissibility by rounding up to the nearest integer.

4 Types of Operator-counting Constraints

In this section we describe four types of operator-counting constraints that capture different state-of-the-art heuristics.

Landmark Constraints

A (disjunctive) action landmark [Zhu and Givan, 2003; Helmert and Domshlak, 2009] for a state s is a set of operators of which at least one must be part of any s-plan.

Using linear programming to derive heuristic estimates from landmarks was introduced by Karpas and Domshlak [2009] for computing optimal cost partitionings for landmarks. The LP formulation was improved by Keyder et al. [2010]. Bonet and Helmert [2010] introduced an alternative formulation that directly fits into our framework and showed that it is the dual of the representation by Keyder et al.

Strengthening heuristics with landmarks is not a new idea: Domshlak et al. [2012] propose it for abstraction heuristics and Bonet [2013] for the LP-based state-equation heuristic. He uses the same constraints as Bonet and Helmert [2010]:

Definition 4 Let L ⊆ O be an action landmark for state s of task Π. The landmark constraint clm s,L for L is ∑o∈L Yo ≥ 1.

Since at least one action of the landmark occurs in every splan, landmark constraints are operator-counting constraints.

Post-Hoc Optimization Constraints

Post-hoc optimization heuristics [Pommerening et al., 2013] exploit knowledge on certain operators not being able to contribute to a heuristic estimate:

Definition 5 Let Π be a planning task with operator set O, let h be an admissible heuristic for Π, and let N ⊆ O be a set of operators that are noncontributing in the sense that the h-values are still admissible in a modified planning task where the cost of all operators in N is set to 0. The posthoc optimization constraint cPH s,h,N for h, N and state s of Π consists of the single inequality ∑o∈O\N cost(o)Yo ≥ h(s).

An important special case applies to pattern database (PDB) heuristics for planning [Edelkamp, 2001], which are based on projections of a planning task Π to a subset (called a pattern) of the state variables. Operators that do not modify any variable in the pattern are noncontributing. We denote with cpdb s,P the post-hoc optimization constraint for state s and the PDB heuristic hP for pattern P .

Net Change Constraints

Bonet [2013] introduces the state-equation heuristic hSEQ by relating planning tasks to Petri nets and deriving constraints based on the net change of the number of tokens in the Petri net locations caused by the firing of transitions. Here, we present the general ideas behind hSEQ but working on the planning task directly, leading us to a deeper understanding.

We say that an operator o applied in state s produces an atom V = v if s[V ] ̸= v and res(o, s)[V ] = v and that it consumes the atom if s[V ] = v and res(o, s)[V ] ̸= v. The net change of the atom from state s to the successor state res(o, s) is 1 if o produces the atom, -1 if it consumes it and 0 otherwise. This idea can be lifted to valid sequence of operators (plans). If π is an operator sequence that is applicable at state s, the net change that π induces over an atom is either 1, -1 or 0 whether π produces, consumes or leaves the atom unchanged. A necessary condition for π to be an s-plan is that π should produce every goal atom that does not hold at s and leave unchanged every goal atom that holds at s.

We want to use this necessary condition to derive operatorcounting constraints. Informally, the accumulated net change for an atom V = v of an operator sequence π adds up all operator applications that produce the atom and subtracts those that consume the atom. Without knowing the exact sequence π, one cannot predict the states are visited by the path π from s to the goal, and thus decide when and what atoms are produced or consumed. However, we can still obtain useful bounds on the induced net change for candidate plans on a given atom V = v. For this, let us consider four disjoint classes of operators for the atom V = v: the class APV=v of operators that always produce the atom, the class SPV=v of operators that sometimes produce the atom, the class ACV=v of operators that always consume the atom, and the class SCV=v of operators that sometimes consume the atom. Operators that do not fall into one of these classes never change the truth value of the atom. For example, if we are told that the plan π for state s contains exactly two operators in APV=v, one operator in ACV=v, and no operator in the other classes for the atom V = v, then we can be sure that the atom V = v will hold after executing π at s.

The net change on an atom V = v that a sequence π induces between a state s and the resulting state res(π, s) can only take a limited number of values if π is an s-plan:

These values and operator classes are combined as follows:

Definition 6 Let Π be a planning task with operator set O. The lower-bound net change constraint cncl s,V=v for atom V = v and state s is the constraint

the upper-bound net change constraint cncu s,V=v is

As before, it is not very difficult to show that the lower- and upper-bound net change constraints are operator-counting constraints. That is, if π is an s-plan for state s, the assignment Yo = Y π o for o ∈ O satisfies all such constraints.

Cost Partitioning Constraints for Abstractions

An abstraction heuristic maps each state s of a planning task Π through a homomorphic mapping α to an abstract state α(s). The heuristic estimate for s is the cost of the cheapest path from α(s) to an abstract goal state in the transition system T α induced by α on the planning task Π.

In general, the estimates of provided by a set A of abstraction heuristics can only be combined admissibly by taking their maximum. Action cost partitionings permit the estimates to be added up while retaining admissibility by distributing the costs of the actions across all the abstractions in A; i.e., if costα(o) ≥ 0 is the cost assigned to operator o in the abstraction α, an action cost partitioning sets the action costs such that ∑α∈A costα(o) ≤ cost(o) for each o ∈ O.

An optimal cost partitioning [Katz and Domshlak, 2010] computes the best estimate obtainable by any action cost partitioning for a given set A of abstractions. Unfortunately, the best partitioning is state-dependent and its computation at each state is often too expensive [Pommerening et al., 2013].

For a set A of abstraction mappings for task Π, let T α = 〈Sα, sαI ,Gα, T α〉 denote the transition system induced by α ∈ A, where Sα is the set of abstract states, sαI is the abstract initial state and Gα is the set of abstract goal states. Each transition 〈s, o, s′ 〉∈T α from state s to state s′ is labeled with the operator o that induces it. The subset SCTα ⊆ T α contains all state-changing transitions 〈s, o, s′ 〉 with s ̸= s′ .

The estimate of the optimal cost partitioning heuristic hOCP A for A in state s ∈ S is the objective value of the following LP or ∞ if the LP is not bounded feasible:

Maximize ∑α∈A Hα subject to

with all variables restricted to be non-negative.

Intuitively, variable Cαo describes the cost of operator o in T α. Given this cost partitioning, variable Dαs′ measures the cheapest cost to reach s′ from α(s) in the abstract system and Hα is the (additive) heuristic estimate for abstraction α.

At first glance, the cost partitioning LP seems unrelated to the operator-counting constraint framework. However, it turns out that the dual of the LP (which must have the same objective value) is a direct fit for our framework, offering a new perspective on optimal cost partitioning. This dual LP is to Minimize ∑o∈O cost(o)Yo subject to the constraints cOCP s,α (defined next) for all abstraction mappings α ∈ A.

Definition 7 Let α be an abstraction mapping for task Π and let T α = 〈Sα, sαI ,Gα, T α〉 be the induced abstract transition system with SCTα ⊆ T α being the set of state-changing transitions. For a state s of Π, the optimal cost partitioning constraint cOCP s,α is defined in terms of the following variables: operator-counting variables Yo for o ∈ O, goal-achievement indicator variables Gαs for s ∈ Gα, and transition-counting variables Tαt for t ∈ SCTα. The constraint cOCP s,α consists of:

1. a transition count inequality for each operator o ∈ O:

1. a goal inequality ∑s′∈Gα Gαs′ ≥ 1, and

3. a flow inequality for all abstract states s′ ̸= α(s) in Sα:

Given an s-plan π for state s, we can find an assignment to the variables in cOCP s,α that satisfies the constraint. Namely, we set Yo to Y π o , Gαs′ to 1 or 0 depending on whether executing π in T α ends in s′ or not, and Tαt to the number of times that the transition t is used when executing π in T α. Thus, the cOCP s,α constraints are operator-counting constraints.

A closer look at the proof of this claim shows that there is a solution of the LP that uses only integer values. This means that the constraints remain sound when interpreting cOCP s,α as an integer program. This results in a heuristic that dominates Katz and Domshlak's optimal cost partitioning, yet the new heuristic is not known to be efficiently computable.

Delete Relaxation Constraints

The delete-relaxation heuristic h+ is best outlined in planning tasks that are expressed with a propositional language like STRIPS [Fikes and Nilsson, 1971]. The estimate h+(s) for state s in a such task Π refers to the cost of an optimal s-plan in the task Π+ that results from removing the "delete effects" [Bonet and Geffner, 2001].

Imai and Fukunaga [2014] present an IP that exactly computes the estimate h+(s) for a given state s using a formulation that associates feasible solutions with s-plans in Π+, and every such plan with a feasible solution that encodes it.

Imai and Fukunaga use an encoding that uses indicator variables Uo ∈ {0, 1} for each o ∈ O, and with an objective that minimizes ∑o∈O cost(o)Uo. We can make the set of constraints into an operator-counting constraint by adding the operator-counting variables Yo with constraints Yo ≥ Uo, for every o ∈ O, and by changing the objective function to minimize ∑o∈O cost(o)Yo [R¨oger and Pommerening, 2015]. The resulting constraint for state s is denoted by cdr s .

5 Relationship to Existing Heuristics

We now sketch how several existing heuristics can be expressed within the operator-counting constraint framework.

Landmark Heuristic with Optimal Cost Partitioning

Optimal cost partitioning for landmarks [Karpas and Domshlak, 2009] can be expressed in our framework.

Theorem 1 For state s, let C(s) be a set of landmark constraints for s. Then hLP C (s) = hLM opt (s), where hLM opt is the landmark heuristic with optimal cost partitioning using the same landmarks as in C.

The LM-cut heuristic [Helmert and Domshlak, 2009] computes a cost partitioning for the set of action landmarks that it finds. Bonet [2013] proposed to use these landmarks for specifying constraints in the sense of this paper. Thus, any LP heuristic using these constraints dominates LM-cut.

Post-Hoc Optimization Heuristic

The definition of the post-hoc optimization heuristic hPhO H,N involves a variable merging step which speeds up its computation but has no influence on the heuristic estimate. If we omit this step, it is defined by an LP which minimizes the objective function ∑o∈O Co, where Co represents the total cost incurred by operator o in a plan. Replacing each occurrence of Co by cost(o)Yo brings the LP into the required form.

Theorem 2 Let hPhO H,N be the post-hoc optimization heuristic for a set of heuristics H where N(h) denotes the noncontributing operators of h ∈ H. For state s, let CH,N(s) = {cPH s,h,N(h) | h ∈ H}. Then hPhO H,N = hLP CH,N .

State-Equation Heuristic

The state-equation heuristic fits directly out framework.

Theorem 3 For state s, let C(s) denote the set of lowerbound net change constraints for s and all atoms. Then the state-equation heuristic hSEQ equals the LP heuristic hLP C .

Optimal Cost Partitioning for Abstractions

We derived the optimal cost partitioning constraints from the dual of the LP which defines the optimal cost partitioning heuristic. As a bounded feasible LP and its dual have the same optimal value, the heuristic fits our framework.

Theorem 4 Let A be a set of abstractions. For state s, let CA(s) be the constraints {cOCP s,α | α ∈ A}. Then hOCP A = hLP CA .

Delete-Relaxation Heuristic

As shown by Imai and Fukunaga [2014] (cf. R¨oger and Pommerening [2015]) the objective of the integer program IPcdr s equals the delete-relaxation estimate h+(s) for state s. The LP relaxation LPcdr s provides a lower bound to h+ that is accurate in several cases [Imai and Fukunaga, 2014].

Critical Path Heuristics

Among the four classes of heuristics identified by Helmert and Domshlak [2009], the class of critical path heuristics is the only that we do not know how to capture. This class only contains the heuristics hm [Haslum and Geffner, 2000] that are in some sense different from the others and that exploit a type of information that the other heuristics do not consider. It is an open and important question whether such heuristics can be efficiently captured with operator-counting constraints.

6 Experimental Evaluation

We implemented a general framework for LP heuristics in the Fast Downward planning system [Helmert, 2006], supporting net change, landmark, PDB and optimal cost partitioning constraints. The underlying LP solver is CPLEX v12.5.1. For our evaluation, we use all tasks for optimal planning from the IPC benchmark suite. All experiments were conducted on Intel Xeon E5-2660 processors (2.2 GHz) with a time limit of 30 minutes and a memory limit of 2 GB for each planner run.

For the different types of operator-counting constraints, we consider the following five groups of constraints:

• SEQ All lower-bound net change constraints, corresponding to the state-equation heuristic hSEQ .
• PhO-Sys1 All post-hoc optimization constraints for projections on goal variables.
• PhO-Sys2 All post-hoc optimization constraints for systematically generated projections on up to two variables.
• LMC All landmark constraints for the landmarks found by the LM-cut heuristic.
• OPT-Sys1 All optimal cost partitioning constraints for projections on goal variables.

Individual Constraint Groups

To get an idea of the quality of the different constraint groups, we ran experiments with A∗ , using one of the above configurations at a time. The resulting coverage is reported in the first block of Table 1.

Optimal cost partitioning on LM-cut landmarks leads to the highest coverage with a clear lead over the state-equation heuristic and the post-hoc optimization heuristic for Sys2 patterns, which are almost on par. Using only Sys1 patterns, the post-hoc optimization heuristic solves 44 fewer tasks and the optimal cost partitioning lags far behind with only 443 solved tasks, compared to 744 by the best LP configuration.

Comparing the coverage of the standard LM-cut heuristic and of the LMC configuration reveals that the additional effort of computing the optimal cost partitioning for the same landmarks does not pay off in terms of providing sufficiently better guidance. A possible reason for this is that the LMcut heuristic already approximates h+ very closely, and the corresponding LP heuristic is also bounded by h+.

For SEQ, we proved that that the upper bound net change constraints are implied by the lower bound net change constraints, so their addition to SEQ cannot increase the value of the resulting heuristic, and observed that the upper bound net change constraints are strictly weaker than the upper bound net change constraints [Pommerening et al., 2014].

Combinations of Constraint Groups

We showed that SEQ dominates OPT-Sys1 in terms of heuristic guidance [Pommerening et al., 2014]. Since OPT-Sys1 also requires much more time to compute the heuristic, we do not consider it in the combinations. Likewise, we also omit PhO-Sys1 as SEQ and PhO-Sys2 give better coverage. This leaves us with all combinations of SEQ, PhO-Sys2 , and LMC. The coverage results appear in Table 1.

A combination of SEQ and PhO-Sys2 looks promising because they have their strengths and weaknesses in different domains. For example, using PhO-Sys2 solves 14 tasks in the tidybot domain, while only 7 can be solved with SEQ. In parcprinter the picture is reversed: using SEQ, we solve 20 tasks in contrast to only 13 with PhO-Sys2 . Indeed, the combination solves 672 instances, a clear improvement on each individual heuristic solving 630 and 631 tasks, respectively.

The combination of PhO-Sys2 and LMC also pays off, solving 758 task instead of 631 and 744, respectively.

The best combination is SEQ and LMC: with 788 tasks, it solves 44 more tasks than its best component LMC and 25 more tasks than the standard LM-cut heuristic which is the state of the art for optimal planning.

However, adding more constraints does not always have a positive effect because the extra time needed to compute the resulting LP may be in excess of the resulting extra guidance.

Constraint Interactions

Can we explain the better performance of the combinations with the better guidance of more individual components, or is there an additional positive effect through interactions of the different constraints in the LP? The plots in Figure 1 show the number of expansions using one LP heuristic with two constraint groups against the expansions using the maximum of the two individual LP heuristics.

In all three cases, we see clear synergy effects: combining two sets of constraints in a single LP indeed leads to stronger heuristic estimates than maximizing the estimates from two separate LPs. These synergy effects are more pronounced in the combinations of SEQ and PhO-Sys2 and of SEQ and LMC than in the combination of PhO-Sys2 and LMC.

Considering coverage, however, the picture is somewhat more mixed: some tasks can only be solved by the approaches using a single large LP, others only by the maximum over two LP heuristics, and both approaches end up too close to tell apart in terms of overall coverage.

7 Discussion

We introduced a class of IP/LP heuristics based on operatorcounting constraints that subsumes many existing heuristics, including the state-equation, post-hoc optimization and admissible landmark heuristic as well as optimal cost partitioning of (explicit-state) abstraction heuristics. Our new LP for optimal cost partitioning of abstraction heuristics is based on a dualization of the originally suggested LP and suggests new ways to combine abstraction heuristics with other sources of knowledge, such as landmarks.

The framework is also effective for the theoretical analysis of heuristics. Indeed, using the framework and formulations presented here, we were able to show [Pommerening et al., 2014] that the state-equation heuristic dominates the optimal cost partitioning on single-variable abstractions and that the safety-based extension of the state-equation heuristic cannot improve heuristic accuracy.

More recently, Pommerening et al. [2015] show that solving the net change constraints alone is equivalent to computing an optimal general cost partitioning for the abstraction in Sys1 (all the projections of variables). This answers an open question on how the state-equation heuristic fits into the general classification of heuristics.

For the future, we look forward for using the framework to obtain new theoretical insight of existing heuristics, and to define new constraints leading to more powerful heuristics.

Acknowledgments

This work was supported by the Swiss National Science Foundation (SNSF) as part of the project "Abstraction Heuristics for Planning and Combinatorial Search" (AHPACS).