Differences between revisions 1 and 14 (spanning 13 versions)
Revision 1 as of 2014-01-27 10:59:03
Size: 2717
Editor: XmlRpcBot
Comment:
Revision 14 as of 2019-03-02 21:34:34
Size: 4270
Editor: XmlRpcBot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 11: Line 11:
 * ''sublists'' (list of [[Doc/OpenList|OpenList]]): sub 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.
 * ''sublists'' (list of [[Doc/OpenList|OpenList]]): open lists between which this one alternates
 * ''boost'' (int): boost value for contained open lists that are restricted to preferred successors
== Epsilon-greedy open list ==
Chooses an entry uniformly randomly with probability 'epsilon', otherwise it returns the minimum entry. The algorithm is based on
Line 15: Line 16:
'''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 it a dead end. A state is never inserted into a sub-open-list that considers it a dead end.  * Richard Valenzano, Nathan R. Sturtevant, Jonathan Schaeffer and Fan Xie.<<BR>>
 [[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7943/8066|A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration]].<<BR>>
 In ''Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014)'', pp. 375-379. AAAI Press 2014.
Line 17: Line 20:
'''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 [[Doc/Heuristic|Heuristic]] Estimators for Satisficing Planning (Extended Version)" (Department of Computer Science at Freiburg University, No. 258, 2010) {{{
epsilon_greedy(eval, pref_only=false, epsilon=0.2, random_seed=-1)
}}}
Line 19: Line 24:
 * ''eval'' ([[Doc/Evaluator|Evaluator]]): evaluator
 * ''pref_only'' (bool): insert only nodes generated by preferred operators
 * ''epsilon'' (double [0.0, 1.0]): probability for choosing the next entry randomly
 * ''random_seed'' (int [-1, infinity]): Set to -1 (default) to use the global random number generator. Set to any other value to use a local random number generator with the given seed.
Line 22: Line 31:
pareto(evals, pref_only=false, state_uniform_selection=false) pareto(evals, pref_only=false, state_uniform_selection=false, random_seed=-1)
Line 26: Line 35:
 * ''evals'' (list of [[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluators  * ''evals'' (list of [[Doc/Evaluator|Evaluator]]): evaluators
Line 28: Line 37:
 * ''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. 
== Standard open list ==
Standard open list that uses a single evaluator
 * ''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.
 * ''random_seed'' (int [-1, infinity]): Set to -1 (default) to use the global random number generator. Set to any other value to use a local random number generator with the given seed.

== Best-first open list ==
Open list that uses a single evaluator and FIFO tiebreaking.
Line 36: Line 46:
 * ''eval'' ([[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluator  * ''eval'' ([[Doc/Evaluator|Evaluator]]): evaluator
Line 38: Line 48:
== Bucket-based open list ==
Bucket-based open list implementation that uses a single evaluator
{{{
single_buckets(eval, pref_only=false)
}}}
'''Implementation Notes:''' Elements with the same evaluator value are stored in double-ended queues, called "buckets". The open list stores a map from evaluator values to buckets. Pushing and popping from a bucket runs in constant time. Therefore, inserting and removing an entry from the open list takes time O(log(n)), where n is the number of buckets.
Line 44: Line 50:

 * ''eval'' ([[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluator
 * ''pref_only'' (bool): insert only nodes generated by preferred operators
Line 53: Line 56:
 * ''evals'' (list of [[Doc/ScalarEvaluator|ScalarEvaluator]]): scalar evaluators  * ''evals'' (list of [[Doc/Evaluator|Evaluator]]): evaluators
Line 56: Line 59:
== Type-based open list ==
Uses multiple evaluators to assign entries to buckets. All entries in a bucket have the same evaluator values. When retrieving an entry, a bucket is chosen uniformly at random and one of the contained entries is selected uniformly randomly. The algorithm is based on

 * Fan Xie, Martin Mueller, Robert Holte and Tatsuya Imai.<<BR>>
 [[http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8472/8705|Type-Based Exploration with Multiple Search Queues for Satisficing Planning]].<<BR>>
 In ''Proceedings of the Twenty-Eigth AAAI Conference Conference on Artificial Intelligence (AAAI 2014)'', pp. 2395-2401. AAAI Press 2014.

{{{
type_based(evaluators, random_seed=-1)
}}}

 * ''evaluators'' (list of [[Doc/Evaluator|Evaluator]]): Evaluators used to determine the bucket for each entry.
 * ''random_seed'' (int [-1, infinity]): Set to -1 (default) to use the global random number generator. Set to any other value to use a local random number generator with the given seed.

Alternation open list

alternates between several open lists.

alt(sublists, boost=0)
  • sublists (list of OpenList): open lists between which this one alternates

  • boost (int): boost value for contained open lists that are restricted to preferred successors

Epsilon-greedy open list

Chooses an entry uniformly randomly with probability 'epsilon', otherwise it returns the minimum entry. The algorithm is based on

epsilon_greedy(eval, pref_only=false, epsilon=0.2, random_seed=-1)
  • eval (Evaluator): evaluator

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

  • epsilon (double [0.0, 1.0]): probability for choosing the next entry randomly

  • random_seed (int [-1, infinity]): Set to -1 (default) to use the global random number generator. Set to any other value to use a local random number generator with the given seed.

Pareto open list

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

pareto(evals, pref_only=false, state_uniform_selection=false, random_seed=-1)
  • evals (list of Evaluator): 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.

  • random_seed (int [-1, infinity]): Set to -1 (default) to use the global random number generator. Set to any other value to use a local random number generator with the given seed.

Best-first open list

Open list that uses a single evaluator and FIFO tiebreaking.

single(eval, pref_only=false)
  • eval (Evaluator): evaluator

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

Implementation Notes: Elements with the same evaluator value are stored in double-ended queues, called "buckets". The open list stores a map from evaluator values to buckets. Pushing and popping from a bucket runs in constant time. Therefore, inserting and removing an entry from the open list takes time O(log(n)), where n is the number of buckets.

Tie-breaking open list

tiebreaking(evals, pref_only=false, unsafe_pruning=true)
  • evals (list of Evaluator): 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

Type-based open list

Uses multiple evaluators to assign entries to buckets. All entries in a bucket have the same evaluator values. When retrieving an entry, a bucket is chosen uniformly at random and one of the contained entries is selected uniformly randomly. The algorithm is based on

type_based(evaluators, random_seed=-1)
  • evaluators (list of Evaluator): Evaluators used to determine the bucket for each entry.

  • random_seed (int [-1, infinity]): Set to -1 (default) to use the global random number generator. Set to any other value to use a local random number generator with the given seed.

FastDownward: Doc/OpenList (last edited 2024-01-11 22:26:38 by XmlRpcBot)