Class ProgressionTreeSpace

java.lang.Object
edu.uky.cs.nil.sabre.ptree.ProgressionTreeSpace
All Implemented Interfaces:
ProgressionSpace<Long>
public class ProgressionTreeSpace extends Object implements ProgressionSpace<Long>
A progression state space modeled as a tree, meaning that the model makes no attempt to recognize when a duplicate state has been generated. Not detecting duplicate states may improve the speed of a search by saving the overhead requires to check for duplicates, but it may also reduce the speed of a search when many duplicate states are created and must then also be searched.

This state space uses the efficient progression tree data structure, which represents each node as a unique Java long.

Author:
Stephen G. Ware

  • Constructor Details

    • ProgressionTreeSpace

      public ProgressionTreeSpace(ProgressionTree tree)
      Constructs a new tree-based progression state space.
      Parameters:
      tree - the tree of states to use

    • ProgressionTreeSpace

      public ProgressionTreeSpace(CompiledProblem problem, Worker.Status status)
      Constructs a new tree-based progression state space and the underlying tree it will use.
      Parameters:
      problem - the problem whose states will be modeled
      status - a status to update while the tree is built

  • Method Details

    • size

      public long size()
      Description copied from interface: ProgressionSpace
      Returns the total number of states in the whole state space.
      Specified by:
      size in interface ProgressionSpace<Long>
      Returns:
      the number of states

    • initialize

      public Long initialize(State state)
      Description copied from interface: ProgressionSpace
      Reset and initializes the state space to begin at a given initial state. The nodes previously represented in this structure may become invalid after calling this method.
      Specified by:
      initialize in interface ProgressionSpace<Long>
      Parameters:
      state - the initial state where search will begin
      Returns:
      an object representing that initial state in this space

    • getNextSolution

      public Solution<CompiledAction> getNextSolution()
      Description copied from interface: ProgressionSpace
      Returns the next solution in the space that has not yet been returned. A solution is any plan which improves the author's utility where every action is explained.
      Specified by:
      getNextSolution in interface ProgressionSpace<Long>
      Returns:
      the next solution which has not yet been returned, or null if no new solutions have been discovered

    • compare

      public double compare(Long node1, Long node2)
      Description copied from interface: ProgressionSpace
      Compares two objects that represent nodes in this search space. This method follows the contract of Comparator.compare(Object, Object), except that it returns a double instead of an int.
      Specified by:
      compare in interface ProgressionSpace<Long>
      Parameters:
      node1 - the first node in the state space to compare
      node2 - the second node in the state space to compare
      Returns:
      a negative double, zero, or a positive double as the first node is higher priority, the same priority, or lower priority than the second node

    • isExplained

      public boolean isExplained(Long node)
      Description copied from interface: ProgressionSpace
      Indicates whether the action that led to the state for the given node is fully explained (that is, explained for all its consenting characters).
      Specified by:
      isExplained in interface ProgressionSpace<Long>
      Parameters:
      node - the node in the state space whose action may be explained
      Returns:
      true if the node's action is explained for all its consenting characters, false otherwise

    • isExplained

      public boolean isExplained(Long node, Character character)
      Description copied from interface: ProgressionSpace
      Indicates whether the action that led to the state for the given node is explained for a given character. Note that if the character is not a consenting character for the action, this method may return false even if the action does make sense for that character to want.
      Specified by:
      isExplained in interface ProgressionSpace<Long>
      Parameters:
      node - the node in the state space whose action may be explained
      character - the character for which it may be explained
      Returns:
      true if the action associated with the node is explained for that character

    • getAction

      public CompiledAction getAction(Long node)
      Description copied from interface: ProgressionSpace
      Returns the action associated with the given node in the state space. Recall that a node is an action/state pair where the action leads to the state. This method returns the action of that pair. If a node has no action because it represents an initial state, this method returns null.
      Specified by:
      getAction in interface ProgressionSpace<Long>
      Parameters:
      node - the node in the state space whose action is desired
      Returns:
      the action associated with the node, or null if the node represents an initial state

    • getValue

      public Value getValue(Long node, CompiledFluent fluent)
      Description copied from interface: ProgressionSpace
      Returns the value of a fluent in the state represented by a node in the state space. Recall that a node is an action/state pair where the action leads to the state. This method returns the value of a fluent in the state of that pair.
      Specified by:
      getValue in interface ProgressionSpace<Long>
      Parameters:
      node - the node in the state space to be treated as a state
      fluent - the fluent to be evaluated
      Returns:
      the value of the fluent in that node's state

    • getParents

      public Iterable<Long> getParents(Long node)
      Description copied from interface: ProgressionSpace
      Returns a collection of nodes from this state space that represent states that may have come before the given node. Recall that a node is an action/state pair where the action leads to the state. This means that, unless the action is null, a node also implicitly represents the state before taking the action that led to its state. This method returns a list of other action/state pairs that led to this before state. In other words, if we think of the given node as the second action in a plan leading to the third state in a plan, this method returns a collection of nodes that could be the first action in the plan leading to the second state in the plan. If the given node has no parents, for example because it is an initial state, this collection will be empty.
      Specified by:
      getParents in interface ProgressionSpace<Long>
      Parameters:
      node - a node in the state space
      Returns:
      a collection of nodes in the state space that represent action/state pairs before this node, or an empty collection is no such nodes exist

    • getChild

      public Long getChild(Long node, CompiledAction action)
      Description copied from interface: ProgressionSpace
      Returns the node that would result from taking the given action in the state represented by the given node. Recall that a node is an action/state pair where the action leads to the state. The node returned by this method will have the given action as its action, the state after that action as its state, and the given node will appear in the parents of the resulting node.
      Specified by:
      getChild in interface ProgressionSpace<Long>
      Parameters:
      node - a node in the state space
      action - the action to take in the state represented by the node
      Returns:
      the node that results from taking that action in that state

    • getBranch

      public Long getBranch(Long node, Character character)
      Description copied from interface: ProgressionSpace
      Returns the node that represents what a character believes will happen when taking an action. Recall that a node is an action/state pair where the action leads to the state. The branch returned will be for the action of that pair. A branch is used to explain why an action's consenting characters would want to take the action. This method will return if the branch does not exist. A branch does not exist if the given character does not believe the action is possible. In some implementations, branches may only exist for consenting characters.
      Specified by:
      getBranch in interface ProgressionSpace<Long>
      Parameters:
      node - the node in the state space whose action needs to be explained for some character
      character - the character for which the action needs to be explained
      Returns:
      a node in the state space which represents that character's beliefs about the state after taking the action, or null if such a branch does not exist

    • getPlan

      public Plan<CompiledAction> getPlan(long node)
      Returns all actions that have occurred between the the last dummy belief update action (or since the initial state if no dummy actions have occurred) and the given node.
      Parameters:
      node - the ID number of the node which represents the state at the end of the desired plan
      Returns:
      all actions that have occurred between the last belief update and and given node

    • getHistory

      public Plan<CompiledAction> getHistory(long node)
      Returns all actions that have occurred since the initial state, including any dummy belief update actions.
      Parameters:
      node - the ID number of the node whose full action history is desired
      Returns:
      all actions, including belief updates, that have occurred between the initial state and the given node