burlap.behavior.singleagent.planning.deterministic.uninformed.dfs

Class LimitedMemoryDFS

java.lang.Object

burlap.behavior.singleagent.MDPSolver

burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

burlap.behavior.singleagent.planning.deterministic.uninformed.dfs.DFS

burlap.behavior.singleagent.planning.deterministic.uninformed.dfs.LimitedMemoryDFS

All Implemented Interfaces:

MDPSolverInterface, Planner

public class LimitedMemoryDFS
extends DFS

This is a modified version of DFS that maintains a memory of the last n states it has previously expanded. Any potential path that will lead to a state that is in its memory will be pruned from the search tree. This valueFunction gives some of the reduced searching power gained when using DFS with a closed with, but with a constant memory space cost that is traded for less pruning power. If there is an imposed search depth and a potential path will explore a state in the memory, but will explore it at an earlier depth, the valueFunction will explore it anyway, since it's possible it will lead to a goal given that it can expand further than the previous exploration.

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.LinkedList<HashableState>	memoryQueue A queue for storing the most recently expanded nodes.
protected int	memorySize the size of the memory; that is, the number of recently expanded search nodes the valueFunction will remember.
protected java.util.Map<HashableState,java.lang.Integer>	memoryStateDepth Stores the depth at which each state in the memory was explored.

Fields inherited from class burlap.behavior.singleagent.planning.deterministic.uninformed.dfs.DFS

maintainClosed, maxDepth, numVisted, optionsFirst, rand

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

gc, internalPolicy

Fields inherited from class burlap.behavior.singleagent.MDPSolver

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

Constructor Summary

Constructors

Constructor and Description
LimitedMemoryDFS(Domain domain, StateConditionTest gc, HashableStateFactory hashingFactory, int maxDepth, boolean maintainClosed, boolean optionsFirst, int memorySize) Constructor for memory limited DFS

Method Summary

Methods

Modifier and Type	Method and Description
protected SearchNode	dfs(SearchNode n, int depth, java.util.Set<HashableState> statesOnPath) Runs DFS from a given search node, keeping track of its current depth.
SDPlannerPolicy	planFromState(State initialState) Plans and returns a SDPlannerPolicy.

Methods inherited from class burlap.behavior.singleagent.planning.deterministic.uninformed.dfs.DFS

DFSInit, getNumVisited, numOptionsInGAs, resetSolver, setOptionsFirst, shuffleGroundedActions, sortActionsWithOptionsFirst

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

deterministicPlannerInit, encodePlanIntoPolicy, hasCachedPlanForState, planContainsOption, planHasDupilicateStates, querySelectedActionForState

Methods inherited from class burlap.behavior.singleagent.MDPSolver

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

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

addNonDomainReferencedAction, getActions, getDebugCode, getDomain, getGamma, getHashingFactory, getRf, getRF, getTf, getTF, setActions, setDebugCode, setDomain, setGamma, setHashingFactory, setRf, setTf, solverInit, toggleDebugPrinting

Field Detail

memorySize

protected int memorySize

the size of the memory; that is, the number of recently expanded search nodes the valueFunction will remember.

memoryQueue

protected java.util.LinkedList<HashableState> memoryQueue

A queue for storing the most recently expanded nodes.

memoryStateDepth

protected java.util.Map<HashableState,java.lang.Integer> memoryStateDepth

Stores the depth at which each state in the memory was explored.

Constructor Detail

LimitedMemoryDFS

public LimitedMemoryDFS(Domain domain,
                StateConditionTest gc,
                HashableStateFactory hashingFactory,
                int maxDepth,
                boolean maintainClosed,
                boolean optionsFirst,
                int memorySize)

Constructor for memory limited DFS

Parameters:

domain - the domain in which to plan

gc - indicates the goal states

hashingFactory - the state hashing factory to use

maxDepth - depth limit of DFS. -1 specifies no limit.

maintainClosed - whether to maintain a closed list or not

optionsFirst - whether to explore paths generated by options first.

memorySize - the number of most recently expanded nodes to remember.

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.

Specified by:

planFromState in interface Planner

Overrides:

planFromState in class DFS

Parameters:

initialState - the initial state of the planning problem

Returns:

a SDPlannerPolicy.

dfs

protected SearchNode dfs(SearchNode n,
             int depth,
             java.util.Set<HashableState> statesOnPath)

Runs DFS from a given search node, keeping track of its current depth. This method is recursive. The memory of the memorySize most recently expanded nodes will be stored.

Overrides:

dfs in class DFS

Parameters:

n - the current search node

depth - the current depth of the search

statesOnPath - the states that have bee explored on the current search path

Returns:

the SearchNode with a goal, or null if it cannot be found from this state.