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

Class DFS

java.lang.Object

burlap.behavior.singleagent.MDPSolver

burlap.behavior.singleagent.planning.deterministic.DeterministicPlanner

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

All Implemented Interfaces:

MDPSolverInterface, Planner

Direct Known Subclasses:

LimitedMemoryDFS

public class DFS
extends DeterministicPlanner

Implements depth-first search. A maxDepth may be specified will will stop descent if it is crossed, and cause the valueFunction to roll back. This implementation of DFS will not explore any path that yields a state that is already on the current path. Optionally, it can be set to maintain a closed which, which means it will not expand nodes that it has already visited in its search, even if they were explored outside of the current path. However, enabling the closed list removes the linear space complexity of DFS and makes it exponential like BFS. Finally, this implementation of DFS has some special support for options in which it can be set to always explore paths that are generated by options first; this heuristic is useful if it is expected that options are more likely to lead to the goal state.

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 boolean	maintainClosed Whether to keep track of a closed list to prevent exploring already seen nodes.
protected int	maxDepth The max depth of the search tree that will be explored.
protected int	numVisted Planning statistic for keeping track of how many nodes DFS expanded.
protected boolean	optionsFirst Whether to explore paths generated by options first
protected java.util.Random	rand A random object for random walks

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
DFS(SADomain domain, StateConditionTest gc, HashableStateFactory hashingFactory) Basic constructor for standard DFS without a depth limit
DFS(SADomain domain, StateConditionTest gc, HashableStateFactory hashingFactory, int maxDepth) Basic constructor for standard DFS with a depth limit
DFS(SADomain domain, StateConditionTest gc, HashableStateFactory hashingFactory, int maxDepth, boolean maintainClosed) Constructor of DFS with specification of depth limit and whether to maintain a closed list that affects exploration.
DFS(SADomain domain, StateConditionTest gc, HashableStateFactory hashingFactory, int maxDepth, boolean maintainClosed, boolean optionsFirst) Constructor of DFS with specification of depth limit, whether to maintain a closed list that affects exploration, and whether paths generated by options should be explored first.

Method Summary

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.
protected void	DFSInit(SADomain domain, StateConditionTest gc, HashableStateFactory hashingFactory, int maxDepth, boolean maintainClosed, boolean optionsFirst) Constructor of DFS with specification of depth limit, whether to maintain a closed list that affects exploration, and whether paths generated by options should be explored first.
int	getNumVisited() Returns the number of search nodes visited/expanded.
protected int	numOptionsInGAs(java.util.List<Action> gas) Returns the number of options present in a list of possible actions.
SDPlannerPolicy	planFromState(State initialState) Plans and returns a SDPlannerPolicy.
void	resetSolver() This method resets all solver results so that a solver can be restarted fresh as if had never solved the MDP.
void	setOptionsFirst() Sets the valueFunction to explore nodes generated by options first.
protected void	shuffleGroundedActions(java.util.List<Action> gas, int s, int e) Shuffles the order of actions on the index range [s, e)
protected void	sortActionsWithOptionsFirst() Reorders the planners action list so that options are in the front of the list.

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

deterministicPlannerInit, encodePlanIntoPolicy, hasCachedPlanForState, planContainsOption, planHasDupilicateStates, querySelectedActionForState

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

maxDepth

protected int maxDepth

The max depth of the search tree that will be explored. -1 indicates that there is no limit.

maintainClosed

protected boolean maintainClosed

Whether to keep track of a closed list to prevent exploring already seen nodes.

optionsFirst

protected boolean optionsFirst

Whether to explore paths generated by options first

rand

protected java.util.Random rand

A random object for random walks

numVisted

protected int numVisted

Planning statistic for keeping track of how many nodes DFS expanded. States that are visited multiple times will be counted each time they are visited.

Constructor Detail

DFS

public DFS(SADomain domain,
           StateConditionTest gc,
           HashableStateFactory hashingFactory)

Basic constructor for standard DFS without a depth limit

Parameters:

domain - the domain in which to plan

gc - indicates the goal states

hashingFactory - the state hashing factory to use

DFS

public DFS(SADomain domain,
           StateConditionTest gc,
           HashableStateFactory hashingFactory,
           int maxDepth)

Basic constructor for standard DFS with a depth limit

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.

DFS

public DFS(SADomain domain,
           StateConditionTest gc,
           HashableStateFactory hashingFactory,
           int maxDepth,
           boolean maintainClosed)

Constructor of DFS with specification of depth limit and whether to maintain a closed list that affects exploration.

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

DFS

public DFS(SADomain domain,
           StateConditionTest gc,
           HashableStateFactory hashingFactory,
           int maxDepth,
           boolean maintainClosed,
           boolean optionsFirst)

Constructor of DFS with specification of depth limit, whether to maintain a closed list that affects exploration, and whether paths generated by options should be explored first.

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.

Method Detail

DFSInit

protected void DFSInit(SADomain domain,
                       StateConditionTest gc,
                       HashableStateFactory hashingFactory,
                       int maxDepth,
                       boolean maintainClosed,
                       boolean optionsFirst)

Constructor of DFS with specification of depth limit, whether to maintain a closed list that affects exploration, and whether paths generated by options should be explored first.

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.

getNumVisited

public int getNumVisited()

Returns the number of search nodes visited/expanded. If a state was visited multiple times in a search, it will be counted multiple times.

Returns:

the number of search nodes visited/expanded

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.

resetSolver

public void resetSolver()

Description copied from interface: MDPSolverInterface

This method resets all solver results so that a solver can be restarted fresh as if had never solved the MDP.

Specified by:

resetSolver in interface MDPSolverInterface

Overrides:

resetSolver in class DeterministicPlanner

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.

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.

setOptionsFirst

public void setOptionsFirst()

Sets the valueFunction to explore nodes generated by options first.

numOptionsInGAs

protected int numOptionsInGAs(java.util.List<Action> gas)

Returns the number of options present in a list of possible actions.

Parameters:

gas - a list of possible actions

Returns:

the number of options present in a list of possible actions.

shuffleGroundedActions

protected void shuffleGroundedActions(java.util.List<Action> gas,
                                      int s,
                                      int e)

Shuffles the order of actions on the index range [s, e)

Parameters:

gas - a list of actions

s - the start index from which actions should be shuffled

e - the end index of actions that should be shuffled.

sortActionsWithOptionsFirst

protected void sortActionsWithOptionsFirst()

Reorders the planners action list so that options are in the front of the list.