13578
Comment:
|
15961
|
Deletions are marked like this. | Additions are marked like this. |
Line 25: | Line 25: |
Line 28: | Line 29: |
--search eager(tiebreaking([[h|sum([g(),]]), h], unsafe_pruning=false), reopen_closed=true, pathmax=false, progress_evaluator=sum([[h|g(),]])) }}} |
--search eager(tiebreaking([sum([g(), h]), h], unsafe_pruning=false), reopen_closed=true, pathmax=false, progress_evaluator=sum([g(), h])) }}} |
Line 66: | Line 68: |
=== Equivalent statements using general eager search === {{{ --heuristic h2=eval2 --search eager_greedy([eval1, h2], preferred=h2, boost=100) }}} is equivalent to {{{ --heuristic h1=eval1 --heuristic h2=eval2 --search eager(alt([single(h1), single(h1, pref_only=true), single(h2), single(h2, pref_only=true)], boost=100), preferred=h2) }}} ---- {{{ --search eager_greedy([eval1, eval2]) }}} is equivalent to {{{ --search eager(alt([single(eval1), single(eval2)])) }}} ---- {{{ --heuristic h1=eval1 --search eager_greedy(h1, preferred=h1) }}} is equivalent to {{{ --heuristic h1=eval1 --search eager(alt([single(h1), single(h1, pref_only=true)]), preferred=h1) }}} ---- {{{ --search eager_greedy(eval1) }}} is equivalent to {{{ --search eager(single(eval1)) }}} |
|
Line 67: | Line 123: |
Line 70: | Line 127: |
Line 104: | Line 160: |
Line 110: | Line 167: |
Line 163: | Line 221: |
'''Equivalent statements using general lazy search:''' ``` --heuristic h1=eval1 --search lazy_wastar([[eval2|h1,]], w=2, preferred=h1, bound=100, boost=500) {{{ is equivalent to }}} --heuristic h1=eval1 --heuristic h2=eval2 --search lazy(alt([single(sum([g(), weight(h1, 2)])), single(sum([g(), weight(h1, 2)]), pref_only=true), single(sum([g(), weight(h2, 2)])), single(sum([g(), weight(h2, 2)]), pref_only=true)], boost=500), preferred=h1, reopen_closed=true, bound=100) {{{ ------------------------------------------------------------ }}} --search lazy_wastar([[eval2|eval1,]], w=2, bound=100) {{{ is equivalent to }}} --search lazy(alt([single(sum([g(), weight(eval1, 2)])), single(sum([g(), weight(eval2, 2)]))], boost=1000), reopen_closed=true, bound=100) {{{ ------------------------------------------------------------ }}} --search lazy_wastar([[eval2|eval1,]], bound=100, boost=0) {{{ is equivalent to }}} --search lazy(alt([[eval1|single(sum([g(),]])), single(sum([[eval2|g(),]]))]) reopen_closed=true, bound=100) {{{ ------------------------------------------------------------ }}} --search lazy_wastar(eval1, w=2) {{{ is equivalent to }}} --search lazy(single(sum([g(), weight(eval1, 2)])), reopen_closed=true) {{{ }}} |
Contents
A* search (eager)
A* is a special case of eager best first search that uses g+h as f-function. We break ties using the evaluator. Closed nodes are re-opened.
astar(eval, pathmax=false, mpd=false, cost_type=NORMAL, bound=infinity)
eval (ScalarEvaluator): evaluator for h-value
pathmax (bool): use pathmax correction
mpd (bool): use multi-path dependence (LM-A*)
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.
bound (int): exclusive depth bound on g-values. Cutoffs are always performed according to the real cost, regardless of the cost_type parameter
mpd option: This option is currently only present for the A* algorithm and not for the more general eager search, because the current implementation of multi-path depedence does not support general open lists.
Equivalent statements using general eager search
--search astar(evaluator)
is equivalent to
--heuristic h=evaluator --search eager(tiebreaking([sum([g(), h]), h], unsafe_pruning=false), reopen_closed=true, pathmax=false, progress_evaluator=sum([g(), h]))
Eager best first search
eager(open, reopen_closed=false, pathmax=false, f_eval=None, preferred=[], cost_type=NORMAL, bound=infinity)
open (OpenList): open list
reopen_closed (bool): reopen closed nodes
pathmax (bool): use pathmax correction
f_eval (ScalarEvaluator): set evaluator for jump statistics. (Optional; if no evaluator is used, jump statistics will not be displayed.)
preferred (list of Heuristic): use preferred operators of these heuristics
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.
bound (int): exclusive depth bound on g-values. Cutoffs are always performed according to the real cost, regardless of the cost_type parameter
Greedy search (eager)
eager_greedy(evals, preferred=[], boost=0, cost_type=NORMAL, bound=infinity)
evals (list of ScalarEvaluator): scalar evaluators
preferred (list of Heuristic): use preferred operators of these heuristics
boost (int): boost value for preferred operator open lists
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.
bound (int): exclusive depth bound on g-values. Cutoffs are always performed according to the real cost, regardless of the cost_type parameter
Open list: In most cases, eager greedy best first search uses an alternation open list with one queue for each evaluator. If preferred operator heuristics are used, it adds an extra queue for each of these evaluators that includes only the nodes that are generated with a preferred operator. If only one evaluator and no preferred operator heuristic is used, the search does not use an alternation open list but a standard open list with only one queue.
Closed nodes: Closed node are not re-opened
Equivalent statements using general eager search
--heuristic h2=eval2 --search eager_greedy([eval1, h2], preferred=h2, boost=100)
is equivalent to
--heuristic h1=eval1 --heuristic h2=eval2 --search eager(alt([single(h1), single(h1, pref_only=true), single(h2), single(h2, pref_only=true)], boost=100), preferred=h2)
--search eager_greedy([eval1, eval2])
is equivalent to
--search eager(alt([single(eval1), single(eval2)]))
--heuristic h1=eval1 --search eager_greedy(h1, preferred=h1)
is equivalent to
--heuristic h1=eval1 --search eager(alt([single(h1), single(h1, pref_only=true)]), preferred=h1)
--search eager_greedy(eval1)
is equivalent to
--search eager(single(eval1))
Enforced hill-climbing
ehc(h, bfs_use_cost=false, preferred_usage=PRUNE_BY_PREFERRED, preferred=[], cost_type=NORMAL, bound=infinity)
h (Heuristic): heuristic
bfs_use_cost (bool): use cost for bfs
preferred_usage ({PRUNE_BY_PREFERRED, RANK_PREFERRED_FIRST}): preferred operator usage
preferred (list of Heuristic): use preferred operators of these heuristics
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.
bound (int): exclusive depth bound on g-values. Cutoffs are always performed according to the real cost, regardless of the cost_type parameter
Iterated search
iterated(engine_configs, pass_bound=true, repeat_last=false, continue_on_fail=false, continue_on_solve=true, plan_counter=0, cost_type=NORMAL, bound=infinity)
engine_configs (list of ParseTree (this just means the input is parsed at a later point. The real type is probably a search engine.)): list of search engines for each phase
pass_bound (bool): use bound from previous search. The bound is the real cost of the plan found before, regardless of the cost_type parameter.
repeat_last (bool): repeat last phase of search
continue_on_fail (bool): continue search after no solution found
continue_on_solve (bool): continue search after solution found
plan_counter (int): start enumerating plans with plan_counter + 1
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.
bound (int): exclusive depth bound on g-values. Cutoffs are always performed according to the real cost, regardless of the cost_type parameter
Note 1: We do no cache values between search iterations at the moment. If you perform a LAMA-style iterative search, heuristic values will be computed multiple times. Adding heuristic caching is issue108.
Note 2: Running this
./downward --search "iterated([lazy_wastar(merge_and_shrink(),w=10), lazy_wastar(merge_and_shrink(),w=5), lazy_wastar(merge_and_shrink(),w=3), lazy_wastar(merge_and_shrink(),w=2), lazy_wastar(merge_and_shrink(),w=1)])"
would perform the preprocessing phase of the merge and shrink heuristic 5 times (once before each iteration).
To avoid this, use heuristic predefinition, which avoids duplicate preprocessing, as follows:
./downward --heuristic "h=merge_and_shrink()" --search "iterated([lazy_wastar(h,w=10), lazy_wastar(h,w=5), lazy_wastar(h,w=3), lazy_wastar(h,w=2), lazy_wastar(h,w=1)])"
Note 3: If you reuse the same landmark count heuristic (using heuristic predefinition) between iterations, the path data (that is, landmark status for each visited state) will be saved between iterations.
Lazy best first search
lazy(open, reopen_closed=false, preferred=[], cost_type=NORMAL, bound=infinity)
open (OpenList): open list
reopen_closed (bool): reopen closed nodes
preferred (list of Heuristic): use preferred operators of these heuristics
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.
bound (int): exclusive depth bound on g-values. Cutoffs are always performed according to the real cost, regardless of the cost_type parameter
Greedy search (lazy)
lazy_greedy(evals, preferred=[], reopen_closed=false, boost=1000, cost_type=NORMAL, bound=infinity)
evals (list of ScalarEvaluator): scalar evaluators
preferred (list of Heuristic): use preferred operators of these heuristics
reopen_closed (bool): reopen closed nodes
boost (int): boost value for alternation queues that are restricted to preferred operator nodes
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.
bound (int): exclusive depth bound on g-values. Cutoffs are always performed according to the real cost, regardless of the cost_type parameter
Open lists: In most cases, lazy greedy best first search uses an alternation open list with one queue for each evaluator. If preferred operator heuristics are used, it adds an extra queue for each of these evaluators that includes only the nodes that are generated with a preferred operator. If only one evaluator and no preferred operator heuristic is used, the search does not use an alternation open list but a standard open list with only one queue.
(Weighted) A* search (lazy)
Weighted A* is a special case of lazy best first search.
lazy_wastar(evals, preferred=[], reopen_closed=true, boost=1000, w=1, cost_type=NORMAL, bound=infinity)
evals (list of ScalarEvaluator): scalar evaluators
preferred (list of Heuristic): use preferred operators of these heuristics
reopen_closed (bool): reopen closed nodes
boost (int): boost value for preferred operator open lists
w (int): heuristic weight
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.
bound (int): exclusive depth bound on g-values. Cutoffs are always performed according to the real cost, regardless of the cost_type parameter
Open lists: In the general case, it uses an alternation open list with one queue for each evaluator h that ranks the nodes by g + w * h. If preferred operator heuristics are used, it adds for each of the evaluators another such queue that only inserts nodes that are generated by preferred operators. In the special case with only one evaluator and no preferred operator heuristics, it uses a single queue that is ranked by g + w * h.
Equivalent statements using general lazy search: ` --heuristic h1=eval1 --search lazy_wastar(h1,, w=2, preferred=h1,
- bound=100, boost=500)
is equivalent to
--heuristic h1=eval1 --heuristic h2=eval2 --search lazy(alt([single(sum([g(), weight(h1, 2)])),
- single(sum([g(), weight(h1, 2)]), pref_only=true), single(sum([g(), weight(h2, 2)])), single(sum([g(), weight(h2, 2)]), pref_only=true)],
- boost=500),
- preferred=h1, reopen_closed=true, bound=100)
------------------------------------------------------------
--search lazy_wastar(eval1,, w=2, bound=100)
is equivalent to
--search lazy(alt([single(sum([g(), weight(eval1, 2)])),
- single(sum([g(), weight(eval2, 2)]))],
- boost=1000),
- reopen_closed=true, bound=100)
------------------------------------------------------------
--search lazy_wastar(eval1,, bound=100, boost=0)
is equivalent to
--search lazy(alt(single(sum([g(),)),
single(sum(g(),))])
- reopen_closed=true, bound=100)
------------------------------------------------------------
--search lazy_wastar(eval1, w=2)
is equivalent to
--search lazy(single(sum([g(), weight(eval1, 2)])), reopen_closed=true)