Differences between revisions 1 and 6 (spanning 5 versions)
Revision 1 as of 2010-08-02 10:56:34
Size: 2270
Editor: GabiRoeger
Comment:
Revision 6 as of 2011-04-08 10:09:34
Size: 2719
Comment: updated syntax
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
#pragma section-numbers 2
Line 7: Line 8:
 * [[#alt|alternation open list]]
 * [[#pareto|pareto open list]]
 * [[#single|standard open list]]
 * [[#single_buckets|bucket-based open list]]
 * [[#tiebreaking|tie-breaking open list]]
<<TableOfContents>>
Line 15: Line 11:
=== Alternation open list === == Alternation open list ==
Line 18: Line 14:
alt(open_list1, open_list2, ..., boost=1000) alt(openlists, boost=0)
Line 22: Line 18:
 * `open_list1, open_list2, ...` (comma-separated list of [[OpenList]]s): open lists
 * `boost` (int): boost value for successful sub-open-lists
 * `openlists` (list of [[OpenList]]s): open lists
 * `boost` (int): boost value for sub-open-lists that are restricted to preferred operator nodes

''Preferred operators:'' Preferred operators are only taken from sub-open-lists
that do not consider the evaluated state a dead end.

''Dead ends:'' A state is considered a dead end if either all alternated open
lists agree that it is a dead end or at least one reliable open list considers is a dead
end. A state is never inserted into a sub-open-list that considers it a dead end.

Note: The treatment of dead ends is different from the one described in the
[[http://tr.informatik.uni-freiburg.de/reports/report258/report00258.ps.gz|technical report]] "The More, the Merrier: Combining Heuristic Estimators for Satisficing Planning
(Extended Version)" (Department of Computer Science at Freiburg University, No. 258,
2010)

Line 26: Line 36:
=== Pareto open list === == Pareto open list ==
Line 29: Line 39:
pareto(evaluator1, evaluator2, ..., pref_only=false, pareto(evals, pref_only=false,
Line 34: Line 44:
 * `evaluator1, evaluator2, ...` (comma-separated list of [[ScalarEvaluator]]s): scalar evaluators  * `evals` (list of [[ScalarEvaluator]]s): scalar evaluators
Line 39: Line 49:
=== Standard open list === == Standard open list ==
Line 51: Line 61:
=== Bucket-based open list === == Bucket-based open list ==
Line 62: Line 72:
=== Tie-breaking open list === == Tie-breaking open list ==
Line 65: Line 75:
tiebreaking(evaluator1, evaluator2, ..., pref_only=false, tiebreaking(evals, pref_only=false,
Line 69: Line 79:
 * `evaluator1, evaluator2, ...` (comma-separated list of [[ScalarEvaluator]]s): scalar evaluators  * `evals` (list of [[ScalarEvaluator]]s): scalar evaluators

Back to the HomePage.

Open lists

1. Alternation open list

alt(openlists, boost=0)

Alternates between several open lists.

  • openlists (list of OpenLists): open lists

  • boost (int): boost value for sub-open-lists that are restricted to preferred operator nodes

Preferred operators: Preferred operators are only taken from sub-open-lists that do not consider the evaluated state a dead end.

Dead ends: A state is considered a dead end if either all alternated open lists agree that it is a dead end or at least one reliable open list considers is a dead end. A state is never inserted into a sub-open-list that considers it a dead end.

Note: The treatment of dead ends is different from the one described in the technical report "The More, the Merrier: Combining Heuristic Estimators for Satisficing Planning (Extended Version)" (Department of Computer Science at Freiburg University, No. 258, 2010)

2. Pareto open list

pareto(evals, pref_only=false, 
       state_uniform_selection=false)

Selects one of the Pareto-optimal (regarding the sub-evaluators) entry for removal.

  • evals (list of ScalarEvaluators): scalar evaluators

  • pref_only (bool): insert only nodes generated by preferred operators

  • state_uniform_selection (bool): When removing an entry, we select a non-dominated bucket and return its oldest entry. If this option is false, we select uniformly from the non-dominated buckets; if the option is true, we weight the buckets with the number of entries.

3. Standard open list

single(evaluator, pref_only=false)

Standard open list that uses a single evaluator.

  • evaluator (ScalarEvaluator): scalar evaluator

  • pref_only (bool): insert only nodes generated by preferred operators

4. Bucket-based open list

single_buckets(evaluator, pref_only=false)

Bucket-based open list implementation that uses a single evaluator.

  • evaluator (ScalarEvaluator): scalar evaluator

  • pref_only (bool): insert only nodes generated by preferred operators

5. Tie-breaking open list

tiebreaking(evals, pref_only=false, 
            unsafe_pruning=true)
  • evals (list of ScalarEvaluators): scalar evaluators

  • pref_only (bool): insert only nodes generated by preferred operators

  • unsafe_pruning (bool): allow unsafe pruning when the main evaluator regards a state a dead end

FastDownward: OpenList (last edited 2011-04-08 10:09:34 by MoritzGronbach)