A heuristic specification is either a newly created heuristic instance or a heuristic that has been defined previously. This page describes how one can specify a new heuristic instance. For re-using heuristics, see Heuristic Predefinitions.

Definitions of properties in the descriptions below:

• admissible: h(s) <= h*(s) for all states s

• consistent: h(s) <= c(s, s') + h(s') for all states s connected to states s' by an action with cost c(s, s')

• safe: h(s) = infinity is only true for states with h*(s) = infinity

• preferred operators: this heuristic identifies preferred operators

Additive heuristic

add(cost_type=NORMAL, transform=<none>, cache_estimates=true)

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: supported

• axioms: supported (in the sense that the planner won't complain -- handling of axioms might be very stupid and even render the heuristic unsafe)

Properties:

• admissible: no

• consistent: no

• safe: yes for tasks without axioms

• preferred operators: yes

Potential heuristic optimized for all states

The algorithm is based on

• Jendrik Seipp, Florian Pommerening and Malte Helmert.
  New Optimization Functions for Potential Heuristics.
  In Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), pp. 193-201. AAAI Press 2015.

all_states_potential(max_potential=1e8, lpsolver=CPLEX, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• max_potential (double [0.0, infinity]): Bound potentials by this number

• lpsolver ({CLP, CPLEX, GUROBI}): external solver that should be used to solve linear programs

  • CLP: default LP solver shipped with the COIN library

  • CPLEX: commercial solver by IBM

  • GUROBI: commercial solver

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Note: to use an LP solver, you must build the planner with LP support. See LPBuildInstructions.

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

Blind heuristic

Returns cost of cheapest action for non-goal states, 0 for goal states

blind(cost_type=NORMAL, transform=<none>, cache_estimates=true)

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: supported

• axioms: supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

Context-enhanced additive heuristic

cea(cost_type=NORMAL, transform=<none>, cache_estimates=true)

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: supported

• axioms: supported (in the sense that the planner won't complain -- handling of axioms might be very stupid and even render the heuristic unsafe)

Properties:

• admissible: no

• consistent: no

• safe: no

• preferred operators: yes

Causal graph heuristic

cg(cost_type=NORMAL, transform=<none>, cache_estimates=true)

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: supported

• axioms: supported (in the sense that the planner won't complain -- handling of axioms might be very stupid and even render the heuristic unsafe)

Properties:

• admissible: no

• consistent: no

• safe: no

• preferred operators: yes

Constant evaluator

Returns a constant value.

const(value=1, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• value (int [0, infinity]): the constant value

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Canonical PDB

The canonical pattern database heuristic is calculated as follows. For a given pattern collection C, the value of the canonical heuristic function is the maximum over all maximal additive subsets A in C, where the value for one subset S in A is the sum of the heuristic values for all patterns in S for a given state.

cpdbs(patterns=systematic(1), dominance_pruning=true, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• patterns (PatternCollectionGenerator): pattern generation method

• dominance_pruning (bool): Exclude patterns and pattern collections that will never contribute to the heuristic value because there are dominating patterns in the collection.

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

Diverse potential heuristics

The algorithm is based on

• Jendrik Seipp, Florian Pommerening and Malte Helmert.
  New Optimization Functions for Potential Heuristics.
  In Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), pp. 193-201. AAAI Press 2015.

diverse_potentials(num_samples=1000, max_num_heuristics=infinity, max_potential=1e8, lpsolver=CPLEX, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• num_samples (int [0, infinity]): Number of states to sample

• max_num_heuristics (int [0, infinity]): maximum number of potential heuristics

• max_potential (double [0.0, infinity]): Bound potentials by this number

• lpsolver ({CLP, CPLEX, GUROBI}): external solver that should be used to solve linear programs

  • CLP: default LP solver shipped with the COIN library

  • CPLEX: commercial solver by IBM

  • GUROBI: commercial solver

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Note: to use an LP solver, you must build the planner with LP support. See LPBuildInstructions.

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

FF heuristic

See also Synergy.

ff(cost_type=NORMAL, transform=<none>, cache_estimates=true)

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: supported

• axioms: supported (in the sense that the planner won't complain -- handling of axioms might be very stupid and even render the heuristic unsafe)

Properties:

• admissible: no

• consistent: no

• safe: yes for tasks without axioms

• preferred operators: yes

Goal count heuristic

goalcount(cost_type=NORMAL, transform=<none>, cache_estimates=true)

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: ignored by design

• conditional effects: supported

• axioms: supported

Properties:

• admissible: no

• consistent: no

• safe: yes

• preferred operators: no

h^m heuristic

hm(m=2, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• m (int [1, infinity]): subset size

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: ignored

• axioms: ignored

Properties:

• admissible: yes for tasks without conditional effects or axioms

• consistent: yes for tasks without conditional effects or axioms

• safe: yes for tasks without conditional effects or axioms

• preferred operators: no

Max heuristic

hmax(cost_type=NORMAL, transform=<none>, cache_estimates=true)

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: supported

• axioms: supported (in the sense that the planner won't complain -- handling of axioms might be very stupid and even render the heuristic unsafe)

Properties:

• admissible: yes for tasks without axioms

• consistent: yes for tasks without axioms

• safe: yes for tasks without axioms

• preferred operators: no

Potential heuristic optimized for initial state

The algorithm is based on

• Jendrik Seipp, Florian Pommerening and Malte Helmert.
  New Optimization Functions for Potential Heuristics.
  In Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), pp. 193-201. AAAI Press 2015.

initial_state_potential(max_potential=1e8, lpsolver=CPLEX, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• max_potential (double [0.0, infinity]): Bound potentials by this number

• lpsolver ({CLP, CPLEX, GUROBI}): external solver that should be used to solve linear programs

  • CLP: default LP solver shipped with the COIN library

  • CPLEX: commercial solver by IBM

  • GUROBI: commercial solver

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Note: to use an LP solver, you must build the planner with LP support. See LPBuildInstructions.

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

iPDB

This pattern generation method is an adaption of the algorithm described in the following paper:

• Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet and Sven Koenig.
  Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning.
  In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), pp. 1007-1012. AAAI Press 2007.

For implementation notes, see also this paper:

• Silvan Sievers, Manuela Ortlieb and Malte Helmert.
  Efficient Implementation of Pattern Database Heuristics for Classical Planning.
  In Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS 2012), pp. 105-111. AAAI Press 2012.

ipdb(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, max_time=infinity, dominance_pruning=true, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• pdb_max_size (int [1, infinity]): maximal number of states per pattern database

• collection_max_size (int [1, infinity]): maximal number of states in the pattern collection

• num_samples (int [1, infinity]): number of samples (random states) on which to evaluate each candidate pattern collection

• min_improvement (int [1, infinity]): minimum number of samples on which a candidate pattern collection must improve on the current one to be considered as the next pattern collection

• max_time (double [0.0, infinity]): maximum time in seconds for improving the initial pattern collection via hill climbing. If set to 0, no hill climbing is performed at all.

• dominance_pruning (bool): Exclude patterns and additive subsets that will never contribute to the heuristic value because there are dominating patterns in the collection.

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Note: The pattern collection created by the algorithm will always contain all patterns consisting of a single goal variable, even if this violates the pdb_max_size or collection_max_size limits.

Note: This pattern generation method uses the canonical pattern collection heuristic.

Implementation Notes

The following will very briefly describe the algorithm and explain the differences between the original implementation from 2007 and the new one in Fast Downward.

The aim of the algorithm is to output a pattern collection for which the Canonical PDB yields the best heuristic estimates.

The algorithm is basically a local search (hill climbing) which searches the "pattern neighbourhood" (starting initially with a pattern for each goal variable) for improving the pattern collection. This is done exactly as described in the section "pattern construction as search" in the paper. For evaluating the neighbourhood, the "counting approximation" as introduced in the paper was implemented. An important difference however consists in the fact that this implementation computes all pattern databases for each candidate pattern rather than using A* search to compute the heuristic values only for the sample states for each pattern.

Also the logic for sampling the search space differs a bit from the original implementation. The original implementation uses a random walk of a length which is binomially distributed with the mean at the estimated solution depth (estimation is done with the current pattern collection heuristic). In the Fast Downward implementation, also a random walk is used, where the length is the estimation of the number of solution steps, which is calculated by dividing the current heuristic estimate for the initial state by the average operator costs of the planning task (calculated only once and not updated during sampling!) to take non-unit cost problems into account. This yields a random walk of an expected lenght of np = 2 * estimated number of solution steps. If the random walk gets stuck, it is being restarted from the initial state, exactly as described in the original paper.

The section "avoiding redundant evaluations" describes how the search neighbourhood of patterns can be restricted to variables that are somewhat relevant to the variables already included in the pattern by analyzing causal graphs. This is also implemented in Fast Downward, but we only consider precondition-to-effect arcs of the causal graph, ignoring effect-to-effect arcs. The second approach described in the paper (statistical confidence interval) is not applicable to this implementation, as it doesn't use A* search but constructs the entire pattern databases for all candidate patterns anyway. The search is ended if there is no more improvement (or the improvement is smaller than the minimal improvement which can be set as an option), however there is no limit of iterations of the local search. This is similar to the techniques used in the original implementation as described in the paper.

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

Landmark-count heuristic

See also Synergy

lmcount(lm_graph, admissible=false, optimal=false, pref=false, alm=true, lpsolver=CPLEX, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• lm_graph (LandmarkGraph): the set of landmarks to use for this heuristic. The set of landmarks can be specified here, or predefined (see LandmarkGraph).

• admissible (bool): get admissible estimate

• optimal (bool): use optimal (LP-based) cost sharing (only makes sense with admissible=true)

• pref (bool): identify preferred operators (see Using preferred operators with the lmcount heuristic)

• alm (bool): use action landmarks

• lpsolver ({CLP, CPLEX, GUROBI}): external solver that should be used to solve linear programs

  • CLP: default LP solver shipped with the COIN library

  • CPLEX: commercial solver by IBM

  • GUROBI: commercial solver

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Note: to use optimal=true, you must build the planner with LP support. See LPBuildInstructions.

Optimal search: when using landmarks for optimal search (admissible=true), you probably also want to enable the mpd option of the A* algorithm to improve heuristic estimates

cost_type parameter: only used when admissible=true (see LandmarkGraph)

Note: to use an LP solver, you must build the planner with LP support. See LPBuildInstructions.

Language features supported:

• action costs: supported

• conditional_effects: supported if the LandmarkGraph supports them; otherwise ignored with admissible=false and not allowed with admissible=true

• axioms: ignored with admissible=false; not allowed with admissible=true

Properties:

• admissible: yes if admissible=true

• consistent: complicated; needs further thought

• safe: yes except on tasks with axioms or on tasks with conditional effects when using a LandmarkGraph not supporting them

• preferred operators: yes (if enabled; see pref option)

Landmark-cut heuristic

lmcut(cost_type=NORMAL, transform=<none>, cache_estimates=true)

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: no

• safe: yes

• preferred operators: no

Merge-and-shrink heuristic

This heuristic implements the algorithm described in the following paper:

• Silvan Sievers, Martin Wehrle, and Malte Helmert.
  Generalized Label Reduction for Merge-and-Shrink Heuristics.
  In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014), pp. 2358-2366. AAAI Press 2014.

For a more exhaustive description of merge-and-shrink, see the journal paper

• Malte Helmert, Patrik Haslum, Joerg Hoffmann, and Raz Nissim.
  Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces.
  Journal of the ACM 61 (3), pp. 16:1-63. 2014

Please note that the journal paper describes the "old" theory of label reduction, which has been superseded by the above conference paper and is no longer implemented in Fast Downward.

merge_and_shrink(merge_strategy, shrink_strategy, label_reduction, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• merge_strategy (MergeStrategy): See detailed documentation for merge strategies. We currently recommend merge_dfp.

• shrink_strategy (ShrinkStrategy): See detailed documentation for shrink strategies. We currently recommend shrink_bisimulation.

• label_reduction (Labels): See detailed documentation for labels. There is currently only one 'option' to use label_reduction. Also note the interaction with shrink strategies.

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Note: Conditional effects are supported directly. Note, however, that for tasks that are not factored (in the sense of the JACM 2014 merge-and-shrink paper), the atomic transition systems on which merge-and-shrink heuristics are based are nondeterministic, which can lead to poor heuristics even when only perfect shrinking is performed.

Note: A currently recommended good configuration uses bisimulation based shrinking (selecting max states from 50000 to 200000 is reasonable), DFP merging, and the appropriate label reduction setting: merge_and_shrink(shrink_strategy=shrink_bisimulation(max_states=100000,threshold=1,greedy=false),merge_strategy=merge_dfp(),label_reduction=label_reduction(before_shrinking=true, before_merging=false))

Language features supported:

• action costs: supported

• conditional effects: supported (but see note)

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

Operator counting heuristic

An operator counting heuristic computes a linear program (LP) in each state. The LP has one variable Count_o for each operator o that represents how often the operator is used in a plan. Operator counting constraints are linear constraints over these varaibles that are guaranteed to have a solution with Count_o = occurrences(o, pi) for every plan pi. Minimizing the total cost of operators subject to some operator counting constraints is an admissible heuristic. For details, see

• Florian Pommerening, Gabriele Roeger, Malte Helmert and Blai Bonet.
  LP-based Heuristics for Cost-optimal Planning.
  In Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014), pp. 226-234. AAAI Press 2014.

operatorcounting(constraint_generators, lpsolver=CPLEX, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• constraint_generators (list of ConstraintGenerator): methods that generate constraints over operator counting variables

• lpsolver ({CLP, CPLEX, GUROBI}): external solver that should be used to solve linear programs

  • CLP: default LP solver shipped with the COIN library

  • CPLEX: commercial solver by IBM

  • GUROBI: commercial solver

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Note: to use an LP solver, you must build the planner with LP support. See LPBuildInstructions.

Language features supported:

• action costs: supported

• conditional effects: not supported (the heuristic supports them in theory, but none of the currently implemented constraint generators do)

• axioms: not supported (the heuristic supports them in theory, but none of the currently implemented constraint generators do)

Properties:

• admissible: yes

• consistent: yes, if all constraint generators represent consistent heuristics

• safe: yes

• preferred operators: no

Pattern database heuristic

TODO

pdb(pattern=greedy(), cost_type=NORMAL, transform=<none>, cache_estimates=true)

• pattern (PatternGenerator): pattern generation method

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

Sample-based potential heuristics

Maximum over multiple potential heuristics optimized for samples. The algorithm is based on

• Jendrik Seipp, Florian Pommerening and Malte Helmert.
  New Optimization Functions for Potential Heuristics.
  In Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), pp. 193-201. AAAI Press 2015.

sample_based_potentials(num_heuristics=1, num_samples=1000, max_potential=1e8, lpsolver=CPLEX, cost_type=NORMAL, transform=<none>, cache_estimates=true)

• num_heuristics (int [0, infinity]): number of potential heuristics

• num_samples (int [0, infinity]): Number of states to sample

• max_potential (double [0.0, infinity]): Bound potentials by this number

• lpsolver ({CLP, CPLEX, GUROBI}): external solver that should be used to solve linear programs

  • CLP: default LP solver shipped with the COIN library

  • CPLEX: commercial solver by IBM

  • GUROBI: commercial solver

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Note: to use an LP solver, you must build the planner with LP support. See LPBuildInstructions.

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

Zero-One PDB

The zero/one pattern database heuristic is simply the sum of the heuristic values of all patterns in the pattern collection. In contrast to the canonical pattern database heuristic, there is no need to check for additive subsets, because the additivity of the patterns is guaranteed by action cost partitioning. This heuristic uses the most simple form of action cost partitioning, i.e. if an operator affects more than one pattern in the collection, its costs are entirely taken into account for one pattern (the first one which it affects) and set to zero for all other affected patterns.

zopdbs(patterns=systematic(1), cost_type=NORMAL, transform=<none>, cache_estimates=true)

• patterns (PatternCollectionGenerator): pattern generation method

• cost_type ({NORMAL, ONE, PLUSONE}): Operator cost adjustment type. No matter what this setting is, axioms will always be considered as actions of cost 0 by the heuristics that treat axioms as actions.

  • NORMAL: all actions are accounted for with their real cost

  • ONE: all actions are accounted for as unit cost

  • PLUSONE: all actions are accounted for as their real cost + 1 (except if all actions have original cost 1, in which case cost 1 is used). This is the behaviour known for the heuristics of the LAMA planner. This is intended to be used by the heuristics, not search engines, but is supported for both.

• transform (AbstractTask): Optional task transformation for the heuristic. Currently only adapt_costs is available.

• cache_estimates (bool): cache heuristic estimates

Language features supported:

• action costs: supported

• conditional effects: not supported

• axioms: not supported

Properties:

• admissible: yes

• consistent: yes

• safe: yes

• preferred operators: no

moin code generated by txt2tags 2.6b (http://txt2tags.sf.net) cmdline: txt2tags