Contents

    1. Additive heuristic
    2. Blind heuristic
    3. Context-enhanced additive heuristic
    4. Additive Cartesian CEGAR heuristic
    5. Causal graph heuristic
    6. FF heuristic
    7. Goal count heuristic
    8. h^m heuristic
    9. Max heuristic
    10. Landmark cost partitioning heuristic
    11. Landmark sum heuristic
    12. Landmark-cut heuristic
    13. Merge-and-shrink heuristic
    14. Operator-counting heuristic
  2. Basic Evaluators
    1. Constant evaluator
    2. g-value evaluator
    3. Max evaluator
    4. Preference evaluator
    5. Sum evaluator
    6. Weighted evaluator
  3. Pattern Database Heuristics
    1. Canonical PDB
    2. iPDB
      1. Implementation Notes
    3. Pattern database heuristic
    4. Zero-One PDB
  4. Potential Heuristics
    1. Potential heuristic optimized for all states
    2. Diverse potential heuristics
    3. Potential heuristic optimized for initial state
    4. Sample-based potential heuristics

An evaluator specification is either a newly created evaluator instance or an evaluator that has been defined previously. This page describes how one can specify a new evaluator instance. For re-using evaluators, see Evaluator Predefinitions.

If the evaluator is a heuristic, definitions of properties in the descriptions below:

This feature type can be bound to variables using let(variable_name, variable_definition, expression) where expression can use variable_name. Predefinitions using --evaluator, --heuristic, and --landmarks are automatically transformed into let-expressions but are deprecated.

Additive heuristic

add(axioms=approximate_negative_cycles, transform=no_transform(), cache_estimates=true, description="add", verbosity=normal)

Supported language features:

Properties:

Blind heuristic

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

blind(transform=no_transform(), cache_estimates=true, description="blind", verbosity=normal)

Supported language features:

Properties:

Context-enhanced additive heuristic

cea(axioms=approximate_negative_cycles, transform=no_transform(), cache_estimates=true, description="cea", verbosity=normal)

Supported language features:

Properties:

Additive Cartesian CEGAR heuristic

See the paper introducing counterexample-guided Cartesian abstraction refinement (CEGAR) for classical planning:

and the paper showing how to make the abstractions additive:

For more details on Cartesian CEGAR and saturated cost partitioning, see the journal paper 

cegar(subtasks=[landmarks(),goals()], max_states=infinity, max_transitions=1M, max_time=infinity, pick=max_refined, use_general_costs=true, random_seed=-1, transform=no_transform(), cache_estimates=true, description="cegar", verbosity=normal)

Supported language features:

Properties:

Causal graph heuristic

cg(max_cache_size=1000000, axioms=approximate_negative_cycles, transform=no_transform(), cache_estimates=true, description="cg", verbosity=normal)

Supported language features:

Properties:

FF heuristic

ff(axioms=approximate_negative_cycles, transform=no_transform(), cache_estimates=true, description="ff", verbosity=normal)

Supported language features:

Properties:

Goal count heuristic

goalcount(transform=no_transform(), cache_estimates=true, description="goalcount", verbosity=normal)

Supported language features:

Properties:

h^m heuristic

hm(m=2, transform=no_transform(), cache_estimates=true, description="hm", verbosity=normal)

Supported language features:

Properties:

Max heuristic

hmax(axioms=approximate_negative_cycles, transform=no_transform(), cache_estimates=true, description="hmax", verbosity=normal)

Supported language features:

Properties:

Landmark cost partitioning heuristic

Landmark progression is implemented according to the following paper: 

landmark_cost_partitioning(lm_factory, pref=false, prog_goal=true, prog_gn=true, prog_r=true, transform=no_transform(), cache_estimates=true, description="landmark_cost_partitioning", verbosity=normal, cost_partitioning=uniform, alm=true, lpsolver=cplex)

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

Usage with A*: We recommend to add this heuristic as lazy_evaluator when using it in the A* algorithm. This way, the heuristic is recomputed before a state is expanded, leading to improved estimates that incorporate all knowledge gained from paths that were found after the state was inserted into the open list.

Consistency: The heuristic is consistent along single paths if it is set as lazy_evaluator; i.e. when expanding s then we have h(s) <= h(s')+cost(a) for all successors s' of s reached with a. But newly found paths to s can increase h(s), at which point the above inequality might not hold anymore.

Optimal Cost Partitioning: To use cost_partitioning=optimal, you must build the planner with LP support. See build instructions.

Preferred operators: Preferred operators should not be used for optimal planning. See Landmark sum heuristic for more information on using preferred operators; the comments there also apply to this heuristic.

Supported language features:

Properties:

Landmark sum heuristic

Landmark progression is implemented according to the following paper: 

landmark_sum(lm_factory, pref=false, prog_goal=true, prog_gn=true, prog_r=true, transform=no_transform(), cache_estimates=true, description="landmark_sum_heuristic", verbosity=normal, axioms=approximate_negative_cycles)

Note on performance for satisficing planning: The cost of a landmark is based on the cost of the operators that achieve it. For satisficing search this can be counterproductive since it is often better to focus on distance from goal (i.e. length of the plan) rather than cost. In experiments we achieved the best performance using the option 'transform=adapt_costs(one)' to enforce unit costs.

Preferred operators: Computing preferred operators is *only enabled* when setting pref=true because it has a nontrivial runtime cost. Using the heuristic for preferred operators without setting pref=true has no effect. Our implementation to compute preferred operators based on landmarks differs from the description in the literature (see reference above).The original implementation computes two kinds of preferred operators:

  1. If there is an applicable operator that reaches a landmark, all such operators are preferred.
  2. If no such operators exist, perform an FF-style relaxed exploration towards the nearest landmarks (according to the landmark orderings) and use the preferred operators of this exploration.

Our implementation only considers preferred operators of the first type and does not include the second type. The rationale for this change is that it reduces code complexity and helps more cleanly separate landmark-based and FF-based computations in LAMA-like planner configurations. In our experiments, only considering preferred operators of the first type reduces performance when using the heuristic and its preferred operators in isolation but improves performance when using this heuristic in conjunction with the FF heuristic, as in LAMA-like planner configurations.

Supported language features:

Properties:

Landmark-cut heuristic

lmcut(transform=no_transform(), cache_estimates=true, description="lmcut", verbosity=normal)

Supported language features:

Properties:

Merge-and-shrink heuristic

This heuristic implements the algorithm described in the following paper:

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

The following paper describes how to improve the DFP merge strategy with tie-breaking, and presents two new merge strategies (dyn-MIASM and SCC-DFP):

Details of the algorithms and the implementation are described in the paper 

merge_and_shrink(merge_strategy, shrink_strategy, label_reduction=<none>, prune_unreachable_states=true, prune_irrelevant_states=true, max_states=-1, max_states_before_merge=-1, threshold_before_merge=-1, main_loop_max_time=infinity, transform=no_transform(), cache_estimates=true, description="merge_and_shrink", verbosity=normal)

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: When pruning unreachable states, admissibility and consistency is only guaranteed for reachable states and transitions between reachable states. While this does not impact regular A* search which will never encounter any unreachable state, it impacts techniques like symmetry-based pruning: a reachable state which is mapped to an unreachable symmetric state (which hence is pruned) would falsely be considered a dead-end and also be pruned, thus violating optimality of the search.

Note: When using a time limit on the main loop of the merge-and-shrink algorithm, the heuristic will compute the maximum over all heuristics induced by the remaining factors if terminating the merge-and-shrink algorithm early. Exception: if there is an unsolvable factor, it will be used as the exclusive heuristic since the problem is unsolvable.

Note: A currently recommended good configuration uses bisimulation based shrinking, the merge strategy SCC-DFP, and the appropriate label reduction setting (max_states has been altered to be between 10k and 200k in the literature). As merge-and-shrink heuristics can be expensive to compute, we also recommend limiting time by setting main_loop_max_time to a finite value. A sensible value would be half of the time allocated for the planner. 

merge_and_shrink(shrink_strategy=shrink_bisimulation(greedy=false),merge_strategy=merge_sccs(order_of_sccs=topological,merge_selector=score_based_filtering(scoring_functions=[goal_relevance(),dfp(),total_order()])),label_reduction=exact(before_shrinking=true,before_merging=false),max_states=50k,threshold_before_merge=1)

Supported language features:

Properties:

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 

operatorcounting(constraint_generators, use_integer_operator_counts=false, lpsolver=cplex, transform=no_transform(), cache_estimates=true, description="operatorcounting", verbosity=normal)

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

Supported language features:

Properties:

Basic Evaluators

Constant evaluator

Returns a constant value. 

const(value=1, description="const", verbosity=normal)

g-value evaluator

Returns the g-value (path cost) of the search node. 

g(description="g", verbosity=normal)

Max evaluator

Calculates the maximum of the sub-evaluators. 

max(evals, description="max", verbosity=normal)

Preference evaluator

Returns 0 if preferred is true and 1 otherwise. 

pref(description="pref", verbosity=normal)

Sum evaluator

Calculates the sum of the sub-evaluators. 

sum(evals, description="sum", verbosity=normal)

Weighted evaluator

Multiplies the value of the evaluator with the given weight. 

weight(eval, weight, description="weight", verbosity=normal)

Pattern Database Heuristics

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), max_time_dominance_pruning=infinity, transform=no_transform(), cache_estimates=true, description="cpdbs", verbosity=normal)

Supported language features:

Properties:

iPDB

This approach is a combination of using the Canonical PDB heuristic over patterns computed with the hillclimbing algorithm for pattern generation. It is a short-hand for the command-line option cpdbs(hillclimbing()). Both the heuristic and the pattern generation algorithm are described in the following paper:

For implementation notes, see:

See also Canonical PDB and Hill climbing for more details. 

ipdb(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, max_time=infinity, random_seed=-1, max_time_dominance_pruning=infinity, transform=no_transform(), cache_estimates=true, description="cpdbs", verbosity=normal)

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 generates patterns optimized for use with the canonical pattern database 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 as described in the section "pattern construction as search" in the paper, except for the corrected search neighbourhood discussed below. 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 relevant to the variables already included in the pattern by analyzing causal graphs. There is a mistake in the paper that leads to some relevant neighbouring patterns being ignored. See the errata for details. This mistake has been addressed in this implementation. 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.

Supported language features:

Properties:

Pattern database heuristic

Computes goal distance in state space abstractions based on projections. First used in domain-independent planning by:

For implementation notes, see: 

pdb(pattern=greedy(), transform=no_transform(), cache_estimates=true, description="pdb", verbosity=normal)

Supported language features:

Properties:

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), transform=no_transform(), cache_estimates=true, description="zopdbs", verbosity=normal)

Supported language features:

Properties:

Potential Heuristics

Potential heuristic optimized for all states

The algorithm is based on 

all_states_potential(max_potential=1e8, lpsolver=cplex, transform=no_transform(), cache_estimates=true, description="all_states_potential", verbosity=normal)

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

Supported language features:

Properties:

Diverse potential heuristics

The algorithm is based on 

diverse_potentials(num_samples=1000, max_num_heuristics=infinity, max_potential=1e8, lpsolver=cplex, transform=no_transform(), cache_estimates=true, description="diverse_potentials", verbosity=normal, random_seed=-1)

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

Supported language features:

Properties:

Potential heuristic optimized for initial state

The algorithm is based on 

initial_state_potential(max_potential=1e8, lpsolver=cplex, transform=no_transform(), cache_estimates=true, description="initial_state_potential", verbosity=normal)

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

Supported language features:

Properties:

Sample-based potential heuristics

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

sample_based_potentials(num_heuristics=1, num_samples=1000, max_potential=1e8, lpsolver=cplex, transform=no_transform(), cache_estimates=true, description="sample_based_potentials", verbosity=normal, random_seed=-1)

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

Supported language features:

Properties:

FastDownward: Doc/Evaluator (last edited 2024-10-07 13:03:56 by XmlRpcBot)