Package fr.uga.pddl4j.heuristics.state

Class FastForward

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.FastForward
All Implemented Interfaces:
Heuristic, PlanningGraphHeuristic, StateHeuristic, Serializable
public final class FastForward extends RelaxedGraphHeuristic
This class implements the heuristics of the fast forward planner. For more about this heuristic see J. Hoffmann, A Heuristic for DOMAIN Independent Planning and its Use in an Enforced Hill-climbing Algorithm, in: Proceedings of the 12th International Symposium on Methodologies for Intelligent Systems, Charlotte, North Carolina, USA, October 2000.

The computation of the value returned by the heuristics is based on the extraction of a relaxed plan to the planning graph ignoring negative effects according to the difficulty heuristic. The heuristic value is the number of actions of the relaxed plan extracted. To select an effect according to the unconditional operators difficulty heuristic, the question is, which achiever should be choose when no NOOP is available ? It is certainly a good idea to select an achiever whose preconditions seems to be "easy". From the graph building_the_library.rst phase, we can obtain a simple measure for the operators_difficulty of an action's preconditions as follows: 

 difficulty(o) := SUM_ID(min { i | p is member of the fact layer at time i }) with p in pre(o)

The operators_difficulty of each action can be set when it is first inserted into the graph. During plan extraction, facing a fact for which no NOOP is available, we then simply selected an achieving action with minimal operators_difficulty. This heuristic works well in situation where there are severals ways to achieve one fact. but some ways need less effort than others.

Warning: The relaxed plan heuristic is not admissible.
See Also:
RelaxedGraphHeuristic, Serialized Form

  • Constructor Details

    • FastForward

      public FastForward​(Problem problem)
      Creates a new FF 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.