Revision 32 as of 2018-12-13 19:05:56

Clear message

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, lazy_evaluator=<none>, pruning=null(), cost_type=NORMAL, bound=infinity, max_time=infinity)

lazy_evaluator: When a state s is taken out of the open list, the lazy evaluator h re-evaluates s. If h(s) changes (for example because h is path-dependent), s is not expanded, but instead reinserted into the open list. This option is currently only present for the A* algorithm.

--search astar(evaluator)

is equivalent to

--evaluator h=evaluator
--search eager(tiebreaking([sum([g(), h]), h], unsafe_pruning=false),
               reopen_closed=true, f_eval=sum([g(), h]))

eager(open, reopen_closed=false, f_eval=<none>, preferred=[], pruning=null(), cost_type=NORMAL, bound=infinity, max_time=infinity)

Greedy search (eager)

eager_greedy(evals, preferred=[], boost=0, pruning=null(), cost_type=NORMAL, bound=infinity, max_time=infinity)

Open list: In most cases, eager greedy best first search uses an alternation open list with one queue for each evaluator. If preferred operator evaluators 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 evaluator 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

--evaluator h2=eval2
--search eager_greedy([eval1, h2], preferred=h2, boost=100)

is equivalent to

--evaluator 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)]))


--evaluator h1=eval1
--search eager_greedy(h1, preferred=h1)

is equivalent to

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

eager_wastar(evals, preferred=[], reopen_closed=true, boost=0, w=1, pruning=null(), cost_type=NORMAL, bound=infinity, max_time=infinity)

Open lists and equivalent statements using general eager search: See corresponding notes for "(Weighted) A* search (lazy)"

Note: Eager weighted A* search uses an alternation open list while A* search uses a tie-breaking open list. Consequently,

--search eager_wastar([h()], w=1)

is not equivalent to

--search astar(h())

Lazy enforced hill-climbing

ehc(h, preferred_usage=PRUNE_BY_PREFERRED, preferred=[], cost_type=NORMAL, bound=infinity, max_time=infinity)

iterated(engine_configs, pass_bound=true, repeat_last=false, continue_on_fail=false, continue_on_solve=true, cost_type=NORMAL, bound=infinity, max_time=infinity)

Note 1: We don't cache heuristic values between search iterations at the moment. If you perform a LAMA-style iterative search, heuristic values will be computed multiple times.

Note 2: The configuration

--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:

--evaluator "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(open, reopen_closed=false, preferred=[], randomize_successors=false, preferred_successors_first=false, random_seed=-1, cost_type=NORMAL, bound=infinity, max_time=infinity)

Successor ordering: When using randomize_successors=true and preferred_successors_first=true, randomization happens before preferred operators are moved to the front.

Greedy search (lazy)

lazy_greedy(evals, preferred=[], reopen_closed=false, boost=1000, randomize_successors=false, preferred_successors_first=false, random_seed=-1, cost_type=NORMAL, bound=infinity, max_time=infinity)

Open lists: In most cases, lazy greedy best first search uses an alternation open list with one queue for each evaluator. If preferred operator evaluators 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 evaluator is used, the search does not use an alternation open list but a standard open list with only one queue.

--evaluator h2=eval2
--search lazy_greedy([eval1, h2], preferred=h2, boost=100)

is equivalent to

--evaluator h1=eval1 --heuristic h2=eval2
--search lazy(alt([single(h1), single(h1, pref_only=true), single(h2),
                  single(h2, pref_only=true)], boost=100),
              preferred=h2)


--search lazy_greedy([eval1, eval2], boost=100)

is equivalent to

--search lazy(alt([single(eval1), single(eval2)], boost=100))


--evaluator h1=eval1
--search lazy_greedy(h1, preferred=h1)

is equivalent to

--evaluator h1=eval1
--search lazy(alt([single(h1), single(h1, pref_only=true)], boost=1000),
              preferred=h1)


--search lazy_greedy(eval1)

is equivalent to

--search lazy(single(eval1))

Successor ordering: When using randomize_successors=true and preferred_successors_first=true, randomization happens before preferred operators are moved to the front.

(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, randomize_successors=false, preferred_successors_first=false, random_seed=-1, cost_type=NORMAL, bound=infinity, max_time=infinity)

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 evaluators 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 evaluators, it uses a single queue that is ranked by g + w * h.

Equivalent statements using general lazy search

--evaluator h1=eval1
--search lazy_wastar([h1, eval2], w=2, preferred=h1,
                     bound=100, boost=500)

is equivalent to

--evaluator 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, eval2], 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, eval2], bound=100, boost=0)

is equivalent to

--search lazy(alt([single(sum([g(), eval1])),
                   single(sum([g(), eval2]))])
              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)

Successor ordering: When using randomize_successors=true and preferred_successors_first=true, randomization happens before preferred operators are moved to the front.