burlap.behavior.singleagent.planning.deterministic.informed

Class BestFirst

java.lang.Object

burlap.behavior.singleagent.MDPSolver

burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

burlap.behavior.singleagent.planning.deterministic.informed.BestFirst

All Implemented Interfaces:

MDPSolverInterface, Planner

Direct Known Subclasses:

AStar

public abstract class BestFirst
extends DeterministicPlanner

An abstract class for implementing Best-first search planning. Best-first search planning stores children node in a priority queue where the priority of nodes is indicated by an f-function. Different Best-first search planning algorithms are implemented by changing how the f-score is computed, which is an abstract method of this class that needs to be override. A*, for instance, is a Best-first valueFunction in which the f-score is g(s) + h(s), where g(s) is the cost to state s, and h(s) is the heuristic score for s. Best-first search requires checking if the open queue already has a search node stored in it and possibly modifying its priority and back pointers if a better path to it has been found. To efficiently provide that functionality, this class makes use of a custom hash-backed priority queue (heap) which performs contains tests using a hash map.

If a terminal function is provided to subclasses of BestFirst, then the BestFirst search algorithm will not expand any nodes that are terminal states, as if there were no actions that could be executed from that state. Note that terminal states are not necessarily the same as goal states, since there could be a fail condition from which the agent cannot act, but that is not explicitly represented in the transition dynamics.

Author:

James MacGlashan

Nested Class Summary

Nested classes/interfaces inherited from class burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

DeterministicPlanner.PlanningFailedException

Field Summary

Fields inherited from class burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

gc, internalPolicy

Fields inherited from class burlap.behavior.singleagent.MDPSolver

actionTypes, debugCode, domain, gamma, hashingFactory, model, usingOptionModel

Constructor Summary

Constructors

Constructor and Description
BestFirst()

Method Summary

Modifier and Type	Method and Description
abstract double	computeF(PrioritizedSearchNode parentNode, Action generatingAction, HashableState successorState, double r) This method returns the f-score for a state given the parent search node, the generating action, the state that was produced.
void	insertIntoOpen(HashIndexedHeap<PrioritizedSearchNode> openQueue, PrioritizedSearchNode psn) This method is used to insert a prioritized search node into the openQueue.
SDPlannerPolicy	planFromState(State initialState) Plans and returns a SDPlannerPolicy.
void	postPlanPrep() This method is called at the end of the planFromState(State) method and can be used clean up any special data structures needed by the subclass.
void	prePlanPrep() This method is called at the start of the planFromState(State) method and can be used initialize any special data structures needed by the subclass.
void	updateOpen(HashIndexedHeap<PrioritizedSearchNode> openQueue, PrioritizedSearchNode openPSN, PrioritizedSearchNode npsn) This method is called whenever a search node already in the openQueue needs to have its information or priority updated to reflect a new search node.

Methods inherited from class burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

deterministicPlannerInit, encodePlanIntoPolicy, hasCachedPlanForState, planContainsOption, planHasDupilicateStates, querySelectedActionForState, resetSolver

Methods inherited from class burlap.behavior.singleagent.MDPSolver

addActionType, applicableActions, getActionTypes, getDebugCode, getDomain, getGamma, getHashingFactory, getModel, setActionTypes, setDebugCode, setDomain, setGamma, setHashingFactory, setModel, solverInit, stateHash, toggleDebugPrinting

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface burlap.behavior.singleagent.MDPSolverInterface

addActionType, getActionTypes, getDebugCode, getDomain, getGamma, getHashingFactory, getModel, setActionTypes, setDebugCode, setDomain, setGamma, setHashingFactory, setModel, solverInit, toggleDebugPrinting

Constructor Detail

BestFirst

public BestFirst()

Method Detail

computeF

public abstract double computeF(PrioritizedSearchNode parentNode,
                                Action generatingAction,
                                HashableState successorState,
                                double r)

This method returns the f-score for a state given the parent search node, the generating action, the state that was produced.

Parameters:

parentNode - the parent search node (and its priority) that from which the next state was generated.

generatingAction - the action that was used to generate the next state.

successorState - the next state that was generated

r - the reward received for the transition

Returns:

the f-score for the next state.

prePlanPrep

public void prePlanPrep()

This method is called at the start of the planFromState(State) method and can be used initialize any special data structures needed by the subclass. By default it does nothing.

postPlanPrep

public void postPlanPrep()

This method is called at the end of the planFromState(State) method and can be used clean up any special data structures needed by the subclass. By default it does nothing.

insertIntoOpen

public void insertIntoOpen(HashIndexedHeap<PrioritizedSearchNode> openQueue,
                           PrioritizedSearchNode psn)

This method is used to insert a prioritized search node into the openQueue. If the subclass needs to do special procedures on his insert (such as using a subclass of PrioritizedSearchNode with more information), it can override it.

Parameters:

openQueue - the open queue in which the search node will be inserted.

psn - the search node to insert.

updateOpen

public void updateOpen(HashIndexedHeap<PrioritizedSearchNode> openQueue,
                       PrioritizedSearchNode openPSN,
                       PrioritizedSearchNode npsn)

This method is called whenever a search node already in the openQueue needs to have its information or priority updated to reflect a new search node. If a subclass needs to handle special procedures (such as using a subclass of PrioritizedSearchNode with more information), it can override this method.

Parameters:

openQueue - the open queue in which the search node exists.

openPSN - the search node indexed in the open queue that will be updated.

npsn - the new search node that contains the updated information.

planFromState

public SDPlannerPolicy planFromState(State initialState)

Plans and returns a SDPlannerPolicy. If a State is not in the solution path of this planner, then the SDPlannerPolicy will throw a runtime exception. If you want a policy that will dynamically replan for unknown states, you should create your own DDPlannerPolicy.

Parameters:

initialState - the initial state of the planning problem

Returns:

a SDPlannerPolicy.