Revision 84 as of 2018-01-17 13:18:33

Clear message

Contents

  1. Additive heuristic
  2. Potential heuristic optimized for all states
  3. Blind heuristic
  4. Context-enhanced additive heuristic
  5. Additive CEGAR heuristic
  6. Causal graph heuristic
  7. Constant evaluator
  8. Canonical PDB
  9. Diverse potential heuristics
  10. FF heuristic
  11. LAMA-FF synergy slave
  12. Goal count heuristic
  13. h^m heuristic
  14. Max heuristic
  15. Potential heuristic optimized for initial state
  16. iPDB
    1. Implementation Notes
  17. LAMA-FF synergy master
  18. Landmark-count heuristic
  19. Landmark-cut heuristic
  20. Merge-and-shrink heuristic
  21. Operator counting heuristic
  22. Pattern database heuristic
  23. Sample-based potential heuristics
  24. Zero-One PDB

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:

Additive heuristic

add(transform=no_transform(), cache_estimates=true)

Language features supported:

Properties:

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)

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

Language features supported:

Properties:

Blind heuristic

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

blind(transform=no_transform(), cache_estimates=true)

Language features supported:

Properties:

Context-enhanced additive heuristic

cea(transform=no_transform(), cache_estimates=true)

Language features supported:

Properties:

Additive CEGAR heuristic

See the paper introducing Counterexample-guided Abstraction Refinement (CEGAR) for classical planning:

and the paper showing how to make the abstractions additive: 

cegar(subtasks=[landmarks(),goals()], max_states=infinity, max_transitions=1000000, max_time=infinity, pick=MAX_REFINED, use_general_costs=true, transform=no_transform(), cache_estimates=true, random_seed=-1)

Language features supported:

Properties:

Causal graph heuristic

cg(transform=no_transform(), cache_estimates=true)

Language features supported:

Properties:

Constant evaluator

Returns a constant value. 

const(value=1, transform=no_transform(), cache_estimates=true)

Properties:

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, transform=no_transform(), cache_estimates=true)

Language features supported:

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, random_seed=-1)

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

Language features supported:

Properties:

FF heuristic

See also Synergy. 

ff(transform=no_transform(), cache_estimates=true)

Language features supported:

Properties:

LAMA-FF synergy slave

See documentation for LAMA-FF synergy master. 

ff_synergy(lama_synergy_heuristic)

Goal count heuristic

goalcount(transform=no_transform(), cache_estimates=true)

Language features supported:

Properties:

h^m heuristic

hm(m=2, transform=no_transform(), cache_estimates=true)

Language features supported:

Properties:

Max heuristic

hmax(transform=no_transform(), cache_estimates=true)

Language features supported:

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)

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

Language features supported:

Properties:

iPDB

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

For implementation notes, see: 

ipdb(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, max_time=infinity, random_seed=-1, dominance_pruning=true, transform=no_transform(), cache_estimates=true)

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:

Properties:

LAMA-FF synergy master

If the FF heuristic should be used (for its estimates or its preferred operators) and we want to use preferred operators of the landmark count heuristic, we can exploit synergy effects by using the LAMA-FF synergy. This synergy can be used via Predefinition (see Predefinitions), for example: `--heuristic "lama_master=lama_synergy(...)" --heuristic "lama_slave=ff_synergy(lama_master)"` 

lama_synergy(lm_factory, admissible=false, optimal=false, alm=true, lpsolver=CPLEX, transform=no_transform(), cache_estimates=true)

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

Landmark-count heuristic

See also Synergy 

lmcount(lm_factory, admissible=false, optimal=false, pref=false, alm=true, lpsolver=CPLEX, transform=no_transform(), cache_estimates=true)

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

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

Language features supported:

Properties:

Landmark-cut heuristic

lmcut(transform=no_transform(), cache_estimates=true)

Language features supported:

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

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.

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):

Note that dyn-MIASM has not been integrated into the official code base of Fast Downward and is available on request. 

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, transform=no_transform(), cache_estimates=true, verbosity=verbose)

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, the merge strategy SCC-DFP, and the appropriate label reduction setting (max_states has been altered to be between 10000 and 200000 in the literature): 

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=50000,threshold_before_merge=1)

Note that for versions of Fast Downward prior to 2016-08-19, the syntax differs. See the recommendation in the file merge_and_shrink_heuristic.cc for an example configuration.

Language features supported:

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, lpsolver=CPLEX, transform=no_transform(), cache_estimates=true)

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

Language features supported:

Properties:

Pattern database heuristic

TODO 

pdb(pattern=greedy(), transform=no_transform(), cache_estimates=true)

Language features supported:

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, random_seed=-1)

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

Language features supported:

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)

Language features supported:

Properties: