|
Size: 20809
Comment:
|
← Revision 105 as of 2018-09-13 16:53:41 ⇥
Size: 0
Comment: superseded by Doc/Evaluator
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| <<TableOfContents>> 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 [[ReusingHeuristics|ReusingHeuristics]]. 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) }}} * ''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. 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 == Blind heuristic == Returns cost of cheapest action for non-goal states, 0 for goal states {{{ blind(cost_type=NORMAL) }}} * ''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. 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) }}} * ''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. 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) }}} * ''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. 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 == Canonical PDB == {{{ cpdbs(cost_type=NORMAL, patterns=None, combo=false, max_states=1000000) }}} * ''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. * ''patterns'' (list of list of int): the pattern collection * ''combo'' (bool): use the combo strategy * ''max_states'' (int): maximum abstraction size for combo strategy == FF heuristic == See also [[Doc/Synergy|Synergy]]. {{{ ff(cost_type=NORMAL) }}} * ''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. 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 == Genetic Algorithm PDB == {{{ gapdb(pdb_max_size=50000, num_collections=5, num_episodes=30, mutation_probability=0.01, disjoint=false, cost_type=NORMAL) }}} * ''pdb_max_size'' (int): max number of states per pdb * ''num_collections'' (int): number of pattern collections to maintain * ''num_episodes'' (int): number of episodes * ''mutation_probability'' (double): probability between 0 and 1 for flipping a bit * ''disjoint'' (bool): using disjoint variables in the patterns of a 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. == Goal count heuristic == {{{ goalcount(cost_type=NORMAL) }}} * ''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. 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) }}} * ''m'' (int): 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. 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) }}} * ''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. 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 == iPDB == the pattern selection procedure by Haslum et al. (AAAI 2007); see also Sievers et al. (SoCS 2012) for implementation notes {{{ ipdb(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, cost_type=NORMAL) }}} * ''pdb_max_size'' (int): max number of states per pdb * ''collection_max_size'' (int): max number of states for collection * ''num_samples'' (int): number of samples * ''min_improvement'' (int): minimum improvement while hill climbing * ''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. == Landmark-count heuristic == See also [[Doc/Synergy|Synergy]] {{{ lmcount(lm_graph, admissible=false, optimal=false, pref=false, alm=true, cost_type=NORMAL) }}} * ''lm_graph'' ([[Doc/LandmarkGraph|LandmarkGraph]]): the set of landmarks to use for this heuristic. The set of landmarks can be specified here, or predefined (see [[Doc/LandmarkGraph|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 * ''alm'' (bool): use action landmarks * ''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. '''Note:''' to use `optimal=true`, you must build the planner with USE_LP=1. See [[LPBuildInstructions|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 [[Doc/LandmarkGraph|LandmarkGraph]]) Language features supported: * '''action costs:''' supported * '''conditional_effects:''' supported if `admissible=false` * '''axioms:''' supported if `admissible=false` (but may behave stupidly and lead to an unsafe heuristic) Properties: * '''admissible:''' yes if `admissible=true` and there are neither conditional effects nor axioms * '''consistent:''' no * '''safe:''' yes (except maybe on tasks with axioms or when using `admissible=true` on tasks with conditional effects) * '''preferred operators:''' yes (if enabled; see `pref_ops` option) == Landmark-cut heuristic == {{{ lmcut(cost_type=NORMAL) }}} * ''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. 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 == Note: The parameter space and syntax for the merge-and-shrink heuristic has changed significantly in August 2011. {{{ merge_and_shrink(merge_strategy=MERGE_LINEAR_CG_GOAL_LEVEL, shrink_strategy=shrink_fh(max_states=50000, max_states_before_merge=50000, shrink_f=high, shrink_h=low), reduce_labels=true, expensive_statistics=false, cost_type=NORMAL) }}} * ''merge_strategy'' ({MERGE_LINEAR_CG_GOAL_LEVEL, MERGE_LINEAR_CG_GOAL_RANDOM, MERGE_LINEAR_GOAL_CG_LEVEL, MERGE_LINEAR_RANDOM, MERGE_DFP, MERGE_LINEAR_LEVEL, MERGE_LINEAR_REVERSE_LEVEL}): merge strategy * ''shrink_strategy'' ([[Doc/ShrinkStrategy|ShrinkStrategy]]): shrink strategy; these are not fully documented yet; try one of the following: {{{ shrink_fh(max_states=N)}}} f-preserving abstractions from the Helmert/Haslum/Hoffmann ICAPS 2007 paper (called HHH in the IJCAI 2011 paper by Nissim, Hoffmann and Helmert). Here, N is a numerical parameter for which sensible values include 1000, 10000, 50000, 100000 and 200000. Combine this with the default merge strategy MERGE_LINEAR_CG_GOAL_LEVEL to match the heuristic in the paper. {{{ shrink_bisimulation(max_states=infinity, threshold=1, greedy=true, initialize_by_h=false, group_by_h=false)}}} Greedy bisimulation without size bound (called M&S-gop in the IJCAI 2011 paper by Nissim, Hoffmann and Helmert). Combine this with the merge strategy MERGE_LINEAR_REVERSE_LEVEL to match the heuristic in the paper. {{{ shrink_bisimulation(max_states=N, greedy=false, initialize_by_h=true, group_by_h=true)}}} Exact bisimulation with a size limit (called DFP-bop in the IJCAI 2011 paper by Nissim, Hoffmann and Helmert), where N is a numerical parameter for which sensible values include 1000, 10000, 50000, 100000 and 200000. Combine this with the merge strategy MERGE_LINEAR_REVERSE_LEVEL to match the heuristic in the paper. * ''reduce_labels'' (bool): enable label reduction * ''expensive_statistics'' (bool): show statistics on "unique unlabeled edges" (WARNING: these are *very* slow -- check the warning in the output) * ''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. Language features supported: * '''action costs:''' supported * '''conditional_effects:''' not supported * '''axioms:''' not supported Properties: * '''admissible:''' yes * '''consistent:''' yes * '''safe:''' yes * '''preferred operators:''' no == PDB == Pattern database heuristic {{{ pdb(cost_type=NORMAL, max_states=1000000, pattern=None) }}} * ''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. * ''max_states'' (int): maximum abstraction size * ''pattern'' (list of int): the pattern == Zero-One PDB == {{{ zopdbs(cost_type=NORMAL, patterns=None, combo=false, max_states=1000000) }}} * ''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. * ''patterns'' (list of list of int): the pattern collection * ''combo'' (bool): use the combo strategy * ''max_states'' (int): maximum abstraction size for combo strategy /* moin code generated by txt2tags 2.6b (http://txt2tags.sf.net) */ /* cmdline: txt2tags */ |