Skip to content

SearchAlgorithm

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, verbosity=normal)
  • eval (Evaluator): evaluator for h-value
  • lazy_evaluator (Evaluator): An evaluator that re-evaluates a state before it is expanded.
  • pruning (PruningMethod): Pruning methods can prune or reorder the set of applicable operators in each state and thereby influence the number and order of successor states that are considered.
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

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

Breadth-first graph search.

brfs(single_plan=true, write_plan=true, pruning=null(), verbosity=normal)
  • single_plan (bool): Stop search after finding the first (shortest) plan.
  • write_plan (bool): Store the necessary information during search for writing plans once they're found.
  • pruning (PruningMethod): Pruning methods can prune or reorder the set of applicable operators in each state and thereby influence the number and order of successor states that are considered.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

This is a depth-first tree search that avoids running in cycles by skipping states s that are already visited earlier on the path to s. Doing so, the search becomes complete.

dfs(single_plan=false, cost_type=normal, bound=infinity, max_time=infinity, verbosity=normal)
  • single_plan (bool): stop after finding the first plan
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

Dump the reachable state space.

dump_reachable_search_space()

eager(open, reopen_closed=false, f_eval=<none>, preferred=[], pruning=null(), cost_type=normal, bound=infinity, max_time=infinity, verbosity=normal)
  • open (OpenList): open list
  • reopen_closed (bool): reopen closed nodes
  • f_eval (Evaluator): set evaluator for jump statistics. (Optional; if no evaluator is used, jump statistics will not be displayed.)
  • preferred (list of Evaluator): use preferred operators of these evaluators
  • pruning (PruningMethod): Pruning methods can prune or reorder the set of applicable operators in each state and thereby influence the number and order of successor states that are considered.
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

Greedy search (eager)#

eager_greedy(evals, preferred=[], boost=0, pruning=null(), cost_type=normal, bound=infinity, max_time=infinity, verbosity=normal)
  • evals (list of Evaluator): evaluators
  • preferred (list of Evaluator): use preferred operators of these evaluators
  • boost (int): boost value for preferred operator open lists
  • pruning (PruningMethod): Pruning methods can prune or reorder the set of applicable operators in each state and thereby influence the number and order of successor states that are considered.
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

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, verbosity=normal)
  • evals (list of Evaluator): evaluators
  • preferred (list of Evaluator): use preferred operators of these evaluators
  • reopen_closed (bool): reopen closed nodes
  • boost (int): boost value for preferred operator open lists
  • w (int): evaluator weight
  • pruning (PruningMethod): Pruning methods can prune or reorder the set of applicable operators in each state and thereby influence the number and order of successor states that are considered.
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

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, verbosity=normal)
  • h (Evaluator): heuristic
  • preferred_usage ({prune_by_preferred, rank_preferred_first}): preferred operator usage
    • prune_by_preferred: prune successors achieved by non-preferred operators
    • rank_preferred_first: first insert successors achieved by preferred operators, then those by non-preferred operators
  • preferred (list of Evaluator): use preferred operators of these evaluators
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

IDA* search with an optional g-value cache.

idastar(eval, initial_f_limit=0, cache_size=0, single_plan=true, cost_type=normal, bound=infinity, max_time=infinity, verbosity=normal)
  • eval (Evaluator): evaluator for h-value. Make sure to use cache_estimates=false.
  • initial_f_limit (int [0, infinity]): initial depth limit
  • cache_size (int [0, infinity]): maximum number of states to cache. For cache_size=infinity the cache fills up until approaching the memory limit, at which point the current number of states becomes the maximum cache size.
  • single_plan (bool): stop after finding the first plan
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output
ids(single_plan=true, cost_type=normal, bound=infinity, max_time=infinity, verbosity=normal)
  • single_plan (bool): stop after finding the first (shortest) plan
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output
iterated(algorithm_configs, pass_bound=true, repeat_last=false, continue_on_fail=false, continue_on_solve=true, cost_type=normal, bound=infinity, max_time=infinity, verbosity=normal)
  • algorithm_configs (list of SearchAlgorithm): list of search algorithms 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
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

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([ipdb()],w=10), lazy_wastar([ipdb()],w=5), lazy_wastar([ipdb()],w=3), lazy_wastar([ipdb()],w=2), lazy_wastar([ipdb()],w=1)])"

would perform the preprocessing phase of the ipdb heuristic 5 times (once before each iteration).

To avoid this, use heuristic predefinition, which avoids duplicate preprocessing, as follows:

--evaluator "h=ipdb()" --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.

iw(width=2, cost_type=normal, bound=infinity, max_time=infinity, verbosity=normal)
  • width (int [1, 2]): maximum conjunction size
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output
lazy(open, reopen_closed=false, preferred=[], randomize_successors=false, preferred_successors_first=false, random_seed=-1, cost_type=normal, bound=infinity, max_time=infinity, verbosity=normal)
  • open (OpenList): open list
  • reopen_closed (bool): reopen closed nodes
  • preferred (list of Evaluator): use preferred operators of these evaluators
  • randomize_successors (bool): randomize the order in which successors are generated
  • preferred_successors_first (bool): consider preferred operators first
  • 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.
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

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, verbosity=normal)
  • evals (list of Evaluator): evaluators
  • preferred (list of Evaluator): use preferred operators of these evaluators
  • reopen_closed (bool): reopen closed nodes
  • boost (int): boost value for alternation queues that are restricted to preferred operator nodes
  • randomize_successors (bool): randomize the order in which successors are generated
  • preferred_successors_first (bool): consider preferred operators first
  • 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.
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

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

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

(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, verbosity=normal)
  • evals (list of Evaluator): evaluators
  • preferred (list of Evaluator): use preferred operators of these evaluators
  • reopen_closed (bool): reopen closed nodes
  • boost (int): boost value for preferred operator open lists
  • w (int): evaluator weight
  • randomize_successors (bool): randomize the order in which successors are generated
  • preferred_successors_first (bool): consider preferred operators first
  • 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.
  • 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 algorithms, 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
  • max_time (double): maximum time in seconds the search is allowed to run for. The timeout is only checked after each complete search step (usually a node expansion), so the actual runtime can be arbitrarily longer. Therefore, this parameter should not be used for time-limiting experiments. Timed-out searches are treated as failed searches, just like incomplete search algorithms that exhaust their search space.
  • verbosity ({silent, normal, verbose, debug}): Option to specify the verbosity level.
    • silent: only the most basic output
    • normal: relevant information to monitor progress
    • verbose: full output
    • debug: like verbose with additional debug output

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

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)