public class DynamicWeightedAStar extends AStar
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. 1. Pohl, Ira (August, 1973). "The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving". Proceedings of the Third International Joint Conference on Artificial Intelligence (IJCAI-73) 3. California, USA. pp. 11-17.
DeterministicPlanner.PlanningFailedException| Modifier and Type | Field and Description |
|---|---|
protected java.util.Map<HashableState,java.lang.Integer> |
depthMap
Data structure for storing the depth of explored states
|
protected double |
epsilon
parameter > 1 indicating the maximum amount of greediness; the larger the more greedy.
|
protected int |
expectedDepth
The expected depth required for a plan
|
protected int |
lastComputedDepth
maintains the depth of the last explored node
|
cumulatedRewardMap, heuristic, lastComputedCumRgc, internalPolicyactionTypes, debugCode, domain, gamma, hashingFactory, model, usingOptionModel| Constructor and Description |
|---|
DynamicWeightedAStar(SADomain domain,
StateConditionTest gc,
HashableStateFactory hashingFactory,
Heuristic heuristic,
double epsilon,
int expectedDepth)
Initializes
|
| Modifier and Type | Method and Description |
|---|---|
double |
computeF(PrioritizedSearchNode parentNode,
Action generatingAction,
HashableState successorState,
EnvironmentOutcome eo) |
protected double |
epsilonWeight(int depth)
Returns the weighted epsilon value at the given search depth
|
void |
insertIntoOpen(HashIndexedHeap<PrioritizedSearchNode> openQueue,
PrioritizedSearchNode psn)
This method is used to insert a prioritized search node into the openQueue.
|
SDPlannerPolicy |
planFromState(State initialState)
Plans and returns a
SDPlannerPolicy. |
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.
|
computeFdeterministicPlannerInit, encodePlanIntoPolicy, hasCachedPlanForState, planContainsOption, planHasDupilicateStates, querySelectedActionForState, resetSolveraddActionType, applicableActions, getActionTypes, getDebugCode, getDomain, getGamma, getHashingFactory, getModel, setActionTypes, setDebugCode, setDomain, setGamma, setHashingFactory, setModel, solverInit, stateHash, toggleDebugPrintingclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitaddActionType, getActionTypes, getDebugCode, getDomain, getGamma, getHashingFactory, getModel, setActionTypes, setDebugCode, setDomain, setGamma, setHashingFactory, setModel, solverInit, toggleDebugPrintingprotected double epsilon
protected int expectedDepth
protected java.util.Map<HashableState,java.lang.Integer> depthMap
protected int lastComputedDepth
public DynamicWeightedAStar(SADomain domain, StateConditionTest gc, HashableStateFactory hashingFactory, Heuristic heuristic, double epsilon, int expectedDepth)
domain - the domain in which to plangc - should evaluate to true for goal states; false otherwisehashingFactory - the state hashing factory to useheuristic - the planning heuristic. Should return non-positive values.epsilon - parameter > 1 indicating greediness; the larger the value the more greedy.expectedDepth - the expected depth of the planpublic void prePlanPrep()
BestFirstBestFirst.planFromState(State) method and can be used initialize any special
data structures needed by the subclass. By default it does nothing.prePlanPrep in class AStarpublic void postPlanPrep()
BestFirstBestFirst.planFromState(State) method and can be used clean up any special
data structures needed by the subclass. By default it does nothing.postPlanPrep in class AStarpublic void insertIntoOpen(HashIndexedHeap<PrioritizedSearchNode> openQueue, PrioritizedSearchNode psn)
BestFirstPrioritizedSearchNode with more information),
it can override it.insertIntoOpen in class AStaropenQueue - the open queue in which the search node will be inserted.psn - the search node to insert.public void updateOpen(HashIndexedHeap<PrioritizedSearchNode> openQueue, PrioritizedSearchNode openPSN, PrioritizedSearchNode npsn)
BestFirstPrioritizedSearchNode with more information), it can override this method.updateOpen in class AStaropenQueue - 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.public SDPlannerPolicy planFromState(State initialState)
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.
This method overrides AStar's implementation so that it avoids reopening closed states that are not actually better due to the dynamic h weight, the reopen check needs to be based on the g score, note the f score
planFromState in interface PlannerplanFromState in class BestFirstinitialState - the initial state of the planning problemSDPlannerPolicy.public double computeF(PrioritizedSearchNode parentNode, Action generatingAction, HashableState successorState, EnvironmentOutcome eo)
protected double epsilonWeight(int depth)
depth - the search depth