Package fr.uga.pddl4j.heuristics.state

Class Sum

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.Sum
All Implemented Interfaces:
Heuristic, PlanningGraphHeuristic, StateHeuristic, Serializable
public final class Sum extends RelaxedGraphHeuristic
This class implements the SUM_ID 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 weighted sum of the costs of individual atoms:

  • hsum(C) = sum gs(r) for all r in C (additive costs)

The heuristic assumes that subgoals are independent. This is not true in general as the achievement of some subgoals can make the achievement of the other subgoals more or less difficult. For this reason, the additive heuristic is not admissible (i.e., it may overestimate the true costs).

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

  • Constructor Details

    • Sum

      public Sum​(Problem problem)
      Creates a new SUM_ID 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 distance to the goal state from the specified state. If the return value is Integer.MAX_VALUE, it means that the goal is unreachable from the specified state. More precisely, this method returns the level of the planning graph where all the propositions of the goal are reached without any mutex or Integer.MAX_VALUE otherwise.
      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 or Integer.MAX_VALUE if the goal is unreachable from the specified state.
      Throws:
      NullPointerException - if state == 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.