Class ExplanationFirstSearch

java.lang.Object
edu.uky.cs.nil.sabre.search.Search<CompiledAction>
edu.uky.cs.nil.sabre.prog.ProgressionSearch
edu.uky.cs.nil.sabre.prog.ExplanationFirstSearch
All Implemented Interfaces:
Worker.Getter<Result<CompiledAction>>
public class ExplanationFirstSearch extends ProgressionSearch
Explanation-first search is a type of progression search that requires every action in a plan to be explained before it will consider adding additional actions to the plan. Specifically, every action in a plan must be explained for every consenting character except the character associated with the plan before more actions can be added to a plan.

When an action is added to a plan expanded, branches are created for each of the action's consenting characters to explain why they would take that action. The search prioritizes branches with deeper epistemic depth, meaning that a node's branches will be visited before the node itself. By the time the trunk is visited, if it has not been explained for all characters except the node's character, then some attempt to explain the action for one of its characters must have failed, and the plan can be removed from consideration.

Author:
Stephen G. Ware

  • Constructor Details

    • ExplanationFirstSearch

      public ExplanationFirstSearch(CompiledProblem problem, ProgressionCost cost, ProgressionCost heuristic, EventTree<CompiledAction> actions, ProgressionSpace<?> space, long searchLimit, long spaceLimit, long timeLimit, int authorTemporalLimit, int characterTemporalLimit, int epistemicLimit, boolean explanationPruning)
      Constructs a new explanation-first progression search.
      Parameters:
      problem - the compiled problem to be solved
      cost - a function to measure the cost of a plan so far
      heuristic - a function to estimate the cost of making a plan into a solution
      actions - an event tree of all actions that can be taken during search
      space - the model of states that will be searched
      searchLimit - the max number of nodes that can be visited
      spaceLimit - the max number of nodes that can be generated
      timeLimit - the max number of milliseconds a search can take
      authorTemporalLimit - the max number of actions in the main plan
      characterTemporalLimit - the max number of actions a character can imagine when trying to explain its actions
      epistemicLimit - the max depth in a character's theory of mind to search
      explanationPruning - whether the search should stop exploring a branch once its root has been explained

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class ProgressionSearch

    • setStart

      public void setStart(State state)
      Description copied from class: Search
      Sets the initial state of the world from which a solution plan must be executable. This method resets this search object, meaning it should discard its internal state, should start over (from the newly set initial state) the next time Search.get(Status) is called, and may reset counters such as the number of nodes visited.
      Overrides:
      setStart in class ProgressionSearch
      Parameters:
      state - the new initial state of the world before planning begins

    • setStatus

      protected void setStatus(Worker.Status status, Progress<CompiledAction> progress)
      Description copied from class: ProgressionSearch
      Sets the message and parameters of the status that will be updated during the search. This method will be called once at the beginning of a new search, and the status will be periodically updated via ProgressionSearch.updateStatus(Status, Progress).
      Overrides:
      setStatus in class ProgressionSearch
      Parameters:
      status - the status object whose message and parameters will be set
      progress - the progress object for the search that is just starting

    • updateStatus

      protected void updateStatus(Worker.Status status, Progress<CompiledAction> progress)
      Description copied from class: ProgressionSearch
      Updates the status during a search. This method will be called after visiting each node during the search, but only after ProgressionSearch.setStatus(Status, Progress) has been called once for this search.
      Overrides:
      updateStatus in class ProgressionSearch
      Parameters:
      status - the status object to update
      progress - the progress object for the current search

    • prune

      protected <N> boolean prune(edu.uky.cs.nil.sabre.prog.SearchNode<N> node)
      Determines whether a search node should be pruned (that is, not visited). This method is called before ProgressionSearch.visit(SearchNode), and it it returns true, the node will not be visited.

      By default, this method returns true only when explanation pruning is on, the node's epistemic depth is greater than 0, and the given node's root is explained.

      During explanation-first search, any node which has not been explained for all of its consenting characters except for the node's character will be pruned. When a node is expanded, all of its branches are also added to the queue, and explanation-first search prioritizes nodes with higher epistemic depth. This means that all of a node's branches will be searched before the trunk, so before a node is visited, if any of its branches are not explained, it is because the search failed to find an explanation for the character of that branch and thus the action can never be explained.

      Overrides:
      prune in class ProgressionSearch
      Type Parameters:
      N - the type of object used to represent a node in the search space
      Parameters:
      node - the search node that is about to be visited if it is not pruned
      Returns:
      true if the search node should be pruned (that is, not visited), or false if the node should be visited

    • visit

      protected <N> boolean visit(edu.uky.cs.nil.sabre.prog.SearchNode<N> node)
      Description copied from class: ProgressionSearch
      Performs one iteration of the search on the given search node. One iteration usually means removing one node from the queue, visiting that node, and possibly adding more nodes to the queue. If this method returns true, the number of visited nodes will be incremented by one, otherwise it will not be incremented.

      By default, this method simply calls ProgressionSearch.expand(SearchNode) with the same node and returns true.

      Overrides:
      visit in class ProgressionSearch
      Type Parameters:
      N - the type of object used to represent a node in the search space
      Parameters:
      node - the search node to be visited
      Returns:
      true if the number of visited nodes should be incremented, false otherwise

    • compare

      protected <N> double compare(edu.uky.cs.nil.sabre.prog.SearchNode<N> node1, edu.uky.cs.nil.sabre.prog.SearchNode<N> node2)
      Defines the priority in which search nodes should be visited. This method follows the contract of Comparator.compare(Object, Object), except that it returns a double instead of an int. In other words, this method should return a negative number if the first node should be visited before the second node, a positive number if the second node should be visited before the first, or 0 if the order does not matter.

      By default, this method prioritizes nodes in this order:

      During explanation-first search, nodes with higher epistemic depth are visited first to ensure a node's branches are always searched before the node (the trunk) is searched.

      Overrides:
      compare in class ProgressionSearch
      Type Parameters:
      N - the type of object used to represent a node in the search space
      Parameters:
      node1 - the first node to be compared
      node2 - the second node to be compared
      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