Heuristics

abstract type Heuristic

Abstract type for search heuristics, which estimate the distance from a State to a goal specified by a Specification. Once constructed, a heuristic can be called on a domain, state, and specification, returning a Real number (typically Float32 for reduced memory usage).

heuristic(domain, state, spec; precompute=true)

Heuristics may precompute and store information that will be used repeatedly during search via the precompute! method. Evaluation of the heuristic on a state is defined by compute.

If the precompute keyword argument is true when calling heuristic as a function, then precompute! will be called before compute is called to perform the heuristic evaluation.

compute(h, domain, state, spec)

Computes the heuristic value of state relative to a goal in a given domain.

precompute!(heuristic, domain, [state, spec])

Precomputes heuristic information given a domain, state, and specification. This function is typically called once during the initialization phase of a Planner's search algorithm.

Precomputation can optionally be made independent of the spec or initial state by defining specific precompute! methods.

is_precomputed(heuristic)

Returns whether heuristic has been precomputed.

ensure_precomputed!(heuristic, domain, [state, spec])

Precomputes a heuristic using the provided arguments if !is_precomputed(h).

filter_available(h, domain, state, spec)

Uses heuristic information to filter the set of available actions at a given state. Defaults to returning available(domain, state).

filter_relevant(h, domain, state, spec)

Uses heuristic information to filter the set of relevant actions at a given state. Defaults to returning relevant(domain, state).

NullHeuristic()

Null heuristic that always returns zero.

GoalCountHeuristic(dir=:forward)

Heuristic that counts the number of goals un/satisfied. Can be used in either the :forward or :backward direction. The latter should be used for search with BackwardPlanner.

ReachabilityHeuristic(max_steps::Int=100)

Heuristic which performs a reachability analysis for the goal via abstract interpretation, returning an optimistic estimate of the number or cost of the actions required to reach the goal, or Inf if the goal is not reached within max_steps of abstract action execution.

For propositional domains (i.e. domains with no non-Boolean fluents), this returns the same value as HMax. For domains with numeric fluents or other datatypes, this provides more informed estimates by performing abstract interpretation of operations on those datatypes (e.g. interval arithmetic).

MetricHeuristic(metric, fluents[, coeffs])

Heuristic that computes a metric distance between the current state and the goals for the specified numeric fluents, which are (optionally) multiplied by scalar coeffs before metric computation.

This heuristic can only be used with goal formulae that contain a list of equality constraints for the provided fluents.

Arguments

• metric

  Function that returns a scalar value given a vector of differences between the fluent values for the current state and the goal.

• fluents

  A list of Terms that refer to numeric fluents in the state.

• coeffs

  A list of scalar coefficients which each fluent value will be multiplied by before metric computation. Defaults to 1 for all fluents.

ManhattanHeuristic(fluents[, coeffs])

Computes Manhattan distance to the goal for the specified numeric fluents. An instance of MetricHeuristic which uses the L1 norm.

EuclideanHeuristic(fluents[, coeffs])

Computes Euclidean distance to the goal for the specified numeric fluents. An instance of MetricHeuristic which uses the L2 norm.

HSPHeuristic(op::Function)

A family of relaxed planning graph heuristics, introduced by the HSP planner [1]. The heuristic precomputes a graph that stores the dependencies between all ground actions and plan-relevant conditions. The cost of achieving each action (and also the goal) is then recursively estimated as the aggregated cost of achieving each (pre)condition the action or goal depends upon, where op is an aggregation function (e.g. max or +).

In turn, the cost of achieving each condition (a.k.a. "fact") is estimated as the minimum cost among all actions that achieve that condition. Once a condition is achieved by an action, it is considered to remain true through the rest of the process, hence the relaxed nature of the heuristic.

This implementation supports domains with negative preconditions, disjunctive preconditions (i.e., or, exists), and functional preconditions (e.g. numeric comparisons, or other Boolean-valued functions of non-Boolean fluents). Functional preconditions are handled by (optimistically) assuming they become true once a constituent fluent is modified by some action.

[1] B. Bonet and H. Geffner, "Planning as Heuristic Search," Artificial Intelligence, vol. 129, no. 1, pp. 5–33, Jun. 2001, https://doi.org/10.1016/S0004-3702(01)00108-4.

HMax()

HSPHeuristic where an action's cost is the max cost of the conditions it depends upon.

HAdd()

HSPHeuristic where an action's cost is the sum of costs of the conditions it depends upon.

FFHeuristic()

A relaxed planning graph heuristic introduced by the FastForward planner [1]. Similar to HSPHeuristic, this heuristic precomputes a graph that stores the dependencies between all ground actions and plan-relevant conditions.

To estimate the distance to the goal, a shortest-path search is performed in the graph, starting from the conditions that are true in the current state, and ending when all the goal conditions are reached. Once a condition is achieved by an action, it is considered to remain true through the rest of the search, hence the relaxed nature of the heuristic. A plan that achieves the goal conditions is reconstructed by following the action back-pointers for each achieved condition, and the cost of this plan is used as the heuristic estimate.

This implementation supports domains with negative preconditions, disjunctive preconditions (i.e., or, exists), and functional preconditions (e.g. numeric comparisons, or other Boolean-valued functions of non-Boolean fluents). Functional preconditions are handled by (optimistically) assuming they become true once a constituent fluent is modified by some action.

[1] J. Hoffmann, "FF: The Fast-Forward Planning System," AI Magazine, vol. 22, no. 3, pp. 57–57, Sep. 2001, https://doi.org/10.1609/aimag.v22i3.1572.

HSPRHeuristic(op::Function)

A family of relaxed planning graph heuristics for backward search, introduced by the HSPr planner ("r" stands for regression) [1]. The costs of achieving a condition are estimated in the same way as the forward variant, HSPHeuristic, but this estimation is performed only once during heuristic precomputation. During heuristic evaluation, the cost from the current partial state to the start state is estimated as the aggregated cost of each condition that is true in the partial state.

[1] B. Bonet and H. Geffner, "Planning as Heuristic Search," Artificial Intelligence, vol. 129, no. 1, pp. 5–33, Jun. 2001, https://doi.org/10.1016/S0004-3702(01)00108-4.

HMaxR()

HSPRHeuristic for backward search, where an action's cost is the max cost of its dependencies.

HAddR()

HSPRHeuristic for backward search, where an action's cost is the sum of costs of its dependencies.

PlannerHeuristic(planner, [d_transform, s_transform])

Computes distance to the goal based on the solution returned by planner.

If an OrderedSolution is returned, the cost of solution is used as the heuristic estimate, (plus the heuristic value of final state, if the planner is a ForwardPlanner.)

If a PolicySolution is returned, the negated value (returned by get_value) is used as the heuristic estimate.

If d_transform or s_transform are provided, this transforms the input domain or state it is passed to the planner. This can be used to relax the problem (e.g. by simplifying the domain, or adding / deleting predicates in the state).

PolicyValueHeuristic(policy::PolicySolution)

Wraps a policy, and returns the negated value estimate of a state (provided by get_value) as the heuristic goal-distance estimate.

GoalDependentPolicyHeuristic(policies::Dict, [default])

Wraps a dictionary mapping planning Specifications to PolicySolutions. Given a particular specification, the heuristic looks up the corresponding policy and returns its negated estimate of a state's value as the heuristic goal-distance estimate.

If a default is provided, then this is used to construct a new policy policy = default(domain, state, spec) for a specification spec that is not found in the dictionary. Otherwise, an error is thrown.

PruningHeuristic(heuristic::Heuristic, pruner)

Combines an existing heuristic with pruner, an action pruning method that defines the filter_available and filter_relevant functions. For example, pruner may be another heuristic that filters actions.

precomputed(h::Heuristic, domain::Domain, args...)

Precomputes a heuristic in advance, returning a PrecomputedHeuristic that prevents repeated pre-computation later.

PrecomputedHeuristic(heuristic::Heuristic, args...)

Wraps an existing heuristic and ensures that it is precomputed, preventing repeated pre-computation on subsequent calls to precompute!.

memoized(h::Heuristic)

Constructs a memoized version of h which caches outputs in a hash table after each evaluation of the heuristic on a new domain, state, or specification.

MemoizedHeuristic(heuristic::Heuristic)

Wraps an existing heuristic and memoizes heuristic evaluations in a hash table.