A reference for cost adapted task can be reviewed: https://github.com/aibasel/downward/pull/282
Since it does not look like someone will further work on this very soon, I archive our shared notes from the sprint here (repeating the todo-list now that the line break issues of the tracker are fixed):
Example of how a reference will look like when added to the code of a search plugin: https://www.fast-downward.org/latest/documentation/search/ConstraintGenerator/
TODO: We need to check all existing links. Ideally use DOIs
The "axioms={approximate_negative,approximate_negative_cycles}" options are used in many evaluators (add, cea, cg, ff, hmax; also landmark_sum, but see below). What it does is *not* described in the literature, and for all these heuristics how we deal with axioms or conditional effects is *not* described in the "regular" papers we cite for these heuristics. Instead, how we deal with conditional effects is described in the Fast Downward journal paper (Helmert, JAIR 2006), and how we deal with axioms with default parameters is also described there *for the case where there are no negative cycles in axioms*. The paper only discusses cg and ff, but what it says for cg also applies to cea, and what it says for ff also applies to add and hmax.
For landmark_sum, it's not so clear to me (Malte) what the axioms option affects, requires a closer look.
List of gathered references (the todo-list)
- https://www.fast-downward.org/latest/documentation/search/AbstractTask/#cost-adapted_task
- LAMA paper https://jair.org/index.php/jair/article/view/10667~~
- https://www.fast-downward.org/latest/documentation/search/ConstraintGenerator/#lm-cut_landmark_constraints
- remove Pommerening et al. ICAPS 2014
- remove Bonet IJCAI 2013
- add LM-CUT paper Helmert & Domshlak ICAPS 2009
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#additive_heuristic
- bonet-geffner-aij2001
- keyder-geffner-ecai2008
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#context-enhanced_additive_heuristic
- helmert-geffner-icaps2008
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#causal_graph_heuristic
- helmert-icaps2004
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#ff_heuristic
- hoffmann-nebel-jair2001 (the AI lecture references this for the original h^FF)
- keyder-geffner-ecai2008 (the AI lecture references this for FF / additive heuristic h^FF)
- fix "computedexactly"
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#hm_heuristic
- haslum-geffner-aips2000
- the implementation is very inefficient, though
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#max_heuristic
- bonet-geffner-aij2001
- keyder-geffner-ecai2008
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#landmark_cost_partitioning_heuristic
- for original heuristic: https://jair.org/index.php/jair/article/view/10667
- cost partitioning: karpas-domshlak-ijcai2009
- landmark progression: buechner-et-al-icaps2023 (already cited there)
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#landmark_sum_heuristic
- add as first reference for original heuristic: https://jair.org/index.php/jair/article/view/10667
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#landmark-cut_heuristic
- helmert-domshlak-icaps2009
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#merge-and-shrink_heuristic
- remove first reference (sievers-et-al-aaai2014), reformulate next sentence
- move sievers-et-al-icaps2016 to somewhere else (probably to MergeStrategy)
- replace JACM 2014 with JAIR 2021
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#preference_evaluator
- richter-helmert-icaps2009
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#canonical_pdb
- idea comes from: haslum-et-al-aaai2007
- discussed in context with other cost-partitioning methods: seipp-et-al-icaps2017
- implementation details: sievers-et-al-socs2017 (add as for iPDBs)
- https://www.fast-downward.org/latest/documentation/search/Evaluator/#zero-one_pdb
- idea from: haslum-et-al-aaai2005
- greedy zero-one cost partitioning: edelkamp-aips2002
- discussed in context with other cost-partitioning methods: seipp-et-al-icaps2017
- implementation details: sievers-et-al-socs2017 (add as for iPDBs)
- https://www.fast-downward.org/latest/documentation/search/LabelReduction/#exact_generalized_label_reduction
- sievers-helmert-jair2021
- https://www.fast-downward.org/latest/documentation/search/LandmarkFactory/#exhaustive_landmarks
- We should say something like "Tests for every atom if the relaxed planning
task where all achievers of this atom are removed is solvable. If yes, it
is a landmark. For the concept of delete relaxation, see:"
- hoffmann-nebel-jair2001 (the FF paper)
- https://www.fast-downward.org/latest/documentation/search/LandmarkFactory/#hm_landmarks
- paper is mentioned, add full reference (keyder-et-al-ecai2010)
- https://www.fast-downward.org/latest/documentation/search/LandmarkFactory/#rhw_landmarks
- comes from the paper already mentioned (richter-et-al-aaai2008)
- add LAMA paper richter-westphal-jair2010 (This is where the algorithm is described in more detail.)
- https://www.fast-downward.org/latest/documentation/search/LandmarkFactory/#zhugivan_landmarks
- paper is mentioned, add full reference (zhu-givan-icaps2003dc)
- https://www.fast-downward.org/latest/documentation/search/MergeScoringFunction/#dfp_scoring
- replace draeger-et-al-spin2006 by draeger-et-al-sttt2009
- https://www.fast-downward.org/latest/documentation/search/MergeScoringFunction/#miasm
- MIASM idea comes from: fan-et-al-socs2014
- dynMIASM: sievers-et-al-icaps2016 (already there)
- https://www.fast-downward.org/latest/documentation/search/MergeScoringFunction/#single_random
- sievers-et-al-icaps2016
- https://www.fast-downward.org/latest/documentation/search/MergeTree/#linear_merge_trees
- cg_goal_level, goal_cg_level: helmert-et-al-aaai2007 (already there)
- level: sievers-et-al-icaps2016
- reverse_level: nissim-et-al-ijcai2011
- no reference for cg_goal_random, random
- https://www.fast-downward.org/latest/documentation/search/OpenList/#alternation_open_list
- idea from: helmert-jair2006
- details: roeger-helmert-icaps2010
- https://www.fast-downward.org/latest/documentation/search/OpenList/#pareto_open_list
- roeger-helmert-icaps2010
- https://www.fast-downward.org/latest/documentation/search/OpenList/#tie-breaking_open_list
- roeger-helmert-icaps2010
- https://www.fast-downward.org/HEAD/documentation/search/PatternGenerator/#random_pattern
- fix "of the the paper"
- https://www.fast-downward.org/latest/documentation/search/PruningMethod/#limited_pruning
- alkhazraji-et-al-ipc2014
- https://www.fast-downward.org/latest/documentation/search/SearchAlgorithm/#lazy_enforced_hill-climbing
- enforced hillclimbing: hoffmann-nebel-jair2001
- but this is *not* what is implemented
- see summary of https://issues.fast-downward.org/issue1196
- https://www.fast-downward.org/latest/documentation/search/SearchAlgorithm/#iterated_search
- richter-westphal-jair2010
- https://www.fast-downward.org/latest/documentation/search/SearchAlgorithm/#lazy_best-first_search
- helmert-jair2006
- richter-helmert-icaps2009
- https://www.fast-downward.org/latest/documentation/search/SearchAlgorithm/#greedy_search_lazy
- helmert-jair2006
- richter-helmert-icaps2009
- https://www.fast-downward.org/latest/documentation/search/SearchAlgorithm/#weighted_a_search_lazy
- lazy aspect:
- helmert-jair2006
- richter-helmert-icaps2009
- weighted: richter-westphal-jair2010
- https://www.fast-downward.org/HEAD/documentation/search/SubtaskGenerator/#abstraction_by_goals
- seipp-helmert-icaps2014
- seipp-helmert-jair2018
- https://www.fast-downward.org/HEAD/documentation/search/SubtaskGenerator/#abstraction_by_landmarks
- seipp-helmert-icaps2014
- seipp-helmert-jair2018
- https://www.fast-downward.org/HEAD/documentation/search/SubtaskGenerator/#no_abstraction
- seipp-helmert-icaps2014
- seipp-helmert-jair2018
|