burlap.behavior.singleagent.planning.deterministic.informed.astar

Class AStar

java.lang.Object

burlap.behavior.singleagent.MDPSolver

burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

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

burlap.behavior.singleagent.planning.deterministic.informed.astar.AStar

All Implemented Interfaces:

MDPSolverInterface, Planner

Direct Known Subclasses:

DynamicWeightedAStar, StaticWeightedAStar, WeightedGreedy

public class AStar
extends BestFirst

An implementation of A*. The typical "costs" of A* should be represented by negative reward returned by the reward function. Similarly, the heuristic function should return non-positive values and an admissible heuristic would be h(n) >= C(n) for all n. A* computes the f-score as g(n) + h(n) where g(n) is the cost so far to node n and h(n) is the admissible heuristic to estimate the remaining cost. Again, costs should be represented as negative reward.

If a terminal function is provided via the setter method defined for OO-MDPs, then the 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

Modifier and Type	Field and Description
protected java.util.Map<HashableState,java.lang.Double>	cumulatedRewardMap Data structure for maintaining g(n): the cost so far to node n
protected Heuristic	heuristic The heuristic function.
protected double	lastComputedCumR Store the most recent cumulative reward received to some node.

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
AStar(SADomain domain, StateConditionTest gc, HashableStateFactory hashingFactory, Heuristic heuristic) Initializes A*.

Method Summary

Modifier and Type	Method and Description
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.
void	postPlanPrep() This method is called at the end of the BestFirst.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 BestFirst.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.informed.BestFirst

planFromState

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

Field Detail

heuristic

protected Heuristic heuristic

The heuristic function.

cumulatedRewardMap

protected java.util.Map<HashableState,java.lang.Double> cumulatedRewardMap

Data structure for maintaining g(n): the cost so far to node n

lastComputedCumR

protected double lastComputedCumR

Store the most recent cumulative reward received to some node.

Constructor Detail

AStar

public AStar(SADomain domain,
             StateConditionTest gc,
             HashableStateFactory hashingFactory,
             Heuristic heuristic)

Initializes A*. Goal states are indicated by gc evaluating to true. The costs are stored as negative rewards in the reward function. By default there are no terminal states except teh goal states, so a terminal function is not taken.

Parameters:

domain - the domain in which to plan

gc - should evaluate to true for goal states; false otherwise

hashingFactory - the state hashing factory to use

heuristic - the planning heuristic. Should return non-positive values.

Method Detail

prePlanPrep

public void prePlanPrep()

Description copied from class: BestFirst

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

Overrides:

prePlanPrep in class BestFirst

postPlanPrep

public void postPlanPrep()

Description copied from class: BestFirst

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

Overrides:

postPlanPrep in class BestFirst

insertIntoOpen

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

Description copied from class: BestFirst

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.

Overrides:

insertIntoOpen in class BestFirst

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)

Description copied from class: BestFirst

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.

Overrides:

updateOpen in class BestFirst

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.

computeF

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

Description copied from class: BestFirst

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

Specified by:

computeF in class BestFirst

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.