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

Class IDAStar

java.lang.Object

burlap.behavior.singleagent.planning.OOMDPPlanner

burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

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

public class IDAStar
extends DeterministicPlanner

Iteratively deepening A* implementation.

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

Modifier and Type	Field and Description
protected Heuristic	heuristic The heuristic to use
protected PrioritizedSearchNode.PSNComparator	nodeComparator The comparator to use for checking which nodes to expand first.

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

gc, internalPolicy

Fields inherited from class burlap.behavior.singleagent.planning.OOMDPPlanner

actions, containsParameterizedActions, debugCode, domain, gamma, hashingFactory, mapToStateIndex, rf, tf

Constructor Summary

Constructors

Constructor and Description
IDAStar(Domain domain, RewardFunction rf, StateConditionTest gc, StateHashFactory hashingFactory, Heuristic heuristic) Initializes the planner.

Method Summary

Methods

Modifier and Type	Method and Description
protected PrioritizedSearchNode	FLimtedDFS(PrioritizedSearchNode lastNode, double minR, double cumulatedReward) Recursive method to perform A* up to a f-score depth
protected boolean	lastStateOnPathIsNew(PrioritizedSearchNode psn) Returns true if the search node has not be visited previously on the current search path.
protected boolean	planEndNode(SearchNode node) Returns true if the search node wraps a goal state.
void	planFromState(State initialState) This method will cause the planner to begin planning from the specified initial state

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

deterministicPlannerInit, encodePlanIntoPolicy, hasCachedPlanForState, planContainsOption, planHasDupilicateStates, querySelectedActionForState, resetPlannerResults

Methods inherited from class burlap.behavior.singleagent.planning.OOMDPPlanner

addNonDomainReferencedAction, getActions, getAllGroundedActions, getDebugCode, getDomain, getGamma, getHashingFactory, getRf, getRF, getTf, getTF, plannerInit, setActions, setDebugCode, setDomain, setGamma, setRf, setTf, stateHash, toggleDebugPrinting, translateAction

Methods inherited from class java.lang.Object

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

Field Detail

heuristic

protected Heuristic heuristic

The heuristic to use

nodeComparator

protected PrioritizedSearchNode.PSNComparator nodeComparator

The comparator to use for checking which nodes to expand first.

Constructor Detail

IDAStar

public IDAStar(Domain domain,
       RewardFunction rf,
       StateConditionTest gc,
       StateHashFactory hashingFactory,
       Heuristic heuristic)

Initializes the planner.

Parameters:

domain - the domain in which to plan

rf - the reward function that represents costs as negative reward

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

planFromState

public void planFromState(State initialState)

Description copied from class: OOMDPPlanner

This method will cause the planner to begin planning from the specified initial state

Specified by:

planFromState in class OOMDPPlanner

Parameters:

initialState - the initial state of the planning problem

FLimtedDFS

protected PrioritizedSearchNode FLimtedDFS(PrioritizedSearchNode lastNode,
                               double minR,
                               double cumulatedReward)

Recursive method to perform A* up to a f-score depth

Parameters:

lastNode - the node to expand

minR - the minimum cumulative reward at which to stop the search (in other terms the maximum cost)

cumulatedReward - the amount of reward accumulated at this node

Returns:

a search node with the goal state, or null if there is no path within the reward requirements from this node

planEndNode

protected boolean planEndNode(SearchNode node)

Returns true if the search node wraps a goal state.

Parameters:

node - the node to check

Returns:

true if the search node wraps a goal state; false otherwise.

lastStateOnPathIsNew

protected boolean lastStateOnPathIsNew(PrioritizedSearchNode psn)

Returns true if the search node has not be visited previously on the current search path.

Parameters:

psn - the search node to check.

Returns:

true if the search node has not be visited previously on the current search path; false otherwise.