Package fr.uga.pddl4j.heuristics.state

Class Max

java.lang.Object
fr.uga.pddl4j.heuristics.AbstractHeuristic
fr.uga.pddl4j.heuristics.state.AbstractStateHeuristic
fr.uga.pddl4j.heuristics.state.RelaxedGraphHeuristic
fr.uga.pddl4j.heuristics.state.Max
All Implemented Interfaces:
Heuristic, PlanningGraphHeuristic, StateHeuristic, Serializable
public final class Max extends RelaxedGraphHeuristic
This class implements the MAX heuristic. (for more details on this heuristic see Blai Bonet and Hector Geffner, Planning as Heuristic Search, Artificial Intelligence 129, 2001, Elsevier)

The principle of this heuristics function h is to resolved a relaxed the planning problem P' in which all delete list are ignored. The cost of achieving an atom p form the state s is noted gs(p). These estimates can be defined recursively as:

  • gs(p) = 0, if p is in s,
  • gs(p) = min[1 + gs(Prec(op))] for each op in O(p), otherwise

where O(p) stands for the actions op that add p, i.e., with p in Add(op), and gs(Prec(op)), to be defined below, stands for the estimated cost of achieving the preconditions of action op from s. The cost gs(C) of a sets of atoms is defined as the max costs of individual atoms:

  • hmax(C) = max gs(r) for all r in C (max costs)

The max heuristic unlike the additive heuristic SUM_ID is admissible as the cost of achieving a set of atoms cannot be lower than the cost of achieving each of the atoms in the set. On the other hand, the max heuristic is often less informative. In fact, while the additive heuristic combines the costs of all subgoals, the max heuristic focuses only on the most difficult subgoals ignoring all others.

Warning: The max heuristic is admissible.
See Also:
RelaxedGraphHeuristic, Serialized Form

  • Constructor Details

    • Max

      public Max​(Problem problem)
      Creates a new MAX heuristic for a specified planning problem.
      Parameters:
      problem - the planning problem.
      Throws:
      NullPointerException - if problem == null.

  • Method Details

    • estimate

      public int estimate​(State state, Condition goal)
      Return the estimated distance to the goal to reach the specified state. If the return value is Integer.MAX_VALUE, it means that the goal is unreachable from the specified state.
      Parameters:
      state - the state from which the distance to the goal must be estimated.
      goal - the goal expression.
      Returns:
      the distance to the goal state from the specified state.
      Throws:
      NullPointerException - if state == null && goal == null.

    • estimate

      public double estimate​(Node node, Condition goal)
      Return the estimated distance to the goal to reach the specified state. If the return value is DOUBLE.MAX_VALUE, it means that the goal is unreachable from the specified state.
      Parameters:
      node - the state from which the distance to the goal must be estimated.
      goal - the goal expression.
      Returns:
      the distance to the goal state from the specified state.