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

Class IDAStar

java.lang.Object

burlap.behavior.singleagent.MDPSolver

burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

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

All Implemented Interfaces:

MDPSolverInterface, Planner

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.MDPSolver

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

Constructor Summary

Constructors

Constructor and Description
IDAStar(SADomain domain, StateConditionTest gc, HashableStateFactory hashingFactory, Heuristic heuristic) Initializes.

Method Summary

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.
SDPlannerPolicy	planFromState(State initialState) Plans and returns a SDPlannerPolicy.

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 to use

nodeComparator

protected PrioritizedSearchNode.PSNComparator nodeComparator

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

Constructor Detail

IDAStar

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

Initializes.

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

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.

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.