Differences between revisions 4 and 5
⇤ ← Revision 4 as of 2010-12-12 11:14:42 →
Size: 2146
Editor: ErezKarpas
Comment:
← Revision 5 as of 2011-01-18 15:28:54 → ⇥
Size: 2891
Editor: GabiRoeger
Comment:
Deletions are marked like this. Additions are marked like this.
Line 20: Line 20:

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

Back to the HomePage.

Open lists

Contents

  1. Alternation open list
  2. Pareto open list
  3. Standard open list
  4. Bucket-based open list
  5. Tie-breaking open list

1. Alternation open list

alt(open_list1, open_list2, ..., boost=0)

Alternates between several open lists.

  • open_list1, open_list2, ... (comma-separated 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(evaluator1, evaluator2, ..., pref_only=false, 
       state_uniform_selection=false)

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

  • evaluator1, evaluator2, ... (comma-separated 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(evaluator1, evaluator2, ..., pref_only=false, 
            unsafe_pruning=true)

  • evaluator1, evaluator2, ... (comma-separated 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