Orbital library

orbital.algorithm.template
Class OpenClosedGeneralSearchProblem

java.lang.Object
  extended by orbital.algorithm.template.OpenClosedGeneralSearchProblem
All Implemented Interfaces:
java.io.Serializable, AlgorithmicProblem, GeneralSearchProblem, MarkovDecisionProblem, TransitionModel

public class OpenClosedGeneralSearchProblem
extends java.lang.Object
implements GeneralSearchProblem, java.io.Serializable

GeneralSearchProblem wrapper keeping track of open and closed sets.

This class extends a problem such that it keeps track of closed sets. And thus it optimizes search in search spaces that form graphs, as well as prevents circular expansions. However, this book-keeping will prove useless and time-consuming on search spaces that form real trees (without repetitive nodes and cross edges).

The closed set is the set of closed nodes that have already been expanded. Nodes in the search space that are not closed are called open.

Author:
André Platzer
See Also:
Decorator, Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from interface orbital.algorithm.template.GeneralSearchProblem
GeneralSearchProblem.Transition
 
Nested classes/interfaces inherited from interface orbital.algorithm.template.MarkovDecisionProblem
MarkovDecisionProblem.DefaultTransition
 
Constructor Summary
OpenClosedGeneralSearchProblem(GeneralSearchProblem problem)
          Create a GeneralSearchProblem keeping track of closed sets.
 
Method Summary
 java.util.Iterator actions(java.lang.Object s)
          Only returns actions leading to open nodes, and only if s is not closed itself.
 MutableFunction getAccumulatedCostFunction()
          Get the accumulated cost function.
 java.lang.Object getInitialState()
          Get the initial state of the problem.
 GeneralSearchProblem getProblem()
          Get the proper (inner) problem to solve which does not yet keep track of closed sets.
 boolean isSolution(java.lang.Object s)
          Check whether the given state is a goal state (a valid solution to the problem).
 java.util.Iterator states(java.lang.Object a, java.lang.Object s)
          Get all states reachable with any transitions from the state under a given action. Deterministic case (will only return one single transition per action).
 TransitionModel.Transition transition(java.lang.Object a, java.lang.Object s, java.lang.Object sp)
          Get (information about) the transition from a state to another state under a given action. Deterministic case.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

OpenClosedGeneralSearchProblem

public OpenClosedGeneralSearchProblem(GeneralSearchProblem problem)
Create a GeneralSearchProblem keeping track of closed sets.

Parameters:
problem - the proper problem to solve which does not yet keep track of closed sets.
Method Detail

getProblem

public GeneralSearchProblem getProblem()
Get the proper (inner) problem to solve which does not yet keep track of closed sets.


getInitialState

public java.lang.Object getInitialState()
Get the initial state of the problem. Clears the closed set.

Specified by:
getInitialState in interface GeneralSearchProblem
Returns:
s0 ∈ S.

actions

public java.util.Iterator actions(java.lang.Object s)
Only returns actions leading to open nodes, and only if s is not closed itself.

Specified by:
actions in interface GeneralSearchProblem
Specified by:
actions in interface TransitionModel
Parameters:
s - the state s∈S whose applicable actions to determine.
Returns:
A(s)⊆A, a list of alternative actions applicable in the state s∈S. The order of the list can be decisive because for actions with equal costs the first will be preferred.
See Also:
GreedyProblem.nextCandidates(java.util.List)

states

public java.util.Iterator states(java.lang.Object a,
                                 java.lang.Object s)
Description copied from interface: GeneralSearchProblem
Get all states reachable with any transitions from the state under a given action.

Intuitively, those are the only relevant states which can be reached by any transitions (from the given state under the given action) at all.

For performance reasons it is recommended that this method does only return those states sʹ∈S that can truely be reached (i.e. where P(sʹ|s,a) > 0, i.e. sʹ ∈ {s}∘τ(a) = {sʹ∈S ¦ τ(a)(s,sʹ)>0}). Although this is not strictly required if it would be too expensive to determine.

Note that the resulting iterator will never be empty since the transition probabilities sum up 1 (or integrate to 1 in the case of a continuous transition probability distribution), even though the next state may not differ from the previous state.

Deterministic case (will only return one single transition per action).

Specified by:
states in interface GeneralSearchProblem
Specified by:
states in interface TransitionModel
Parameters:
a - the action a∈A(s) that must be applicable in state s∈S.
s - the state s∈S.
Returns:
a list of states sʹ∈S that could be reached when performing the action a in the state s.

transition

public TransitionModel.Transition transition(java.lang.Object a,
                                             java.lang.Object s,
                                             java.lang.Object sp)
Description copied from interface: GeneralSearchProblem
Get (information about) the transition from a state to another state under a given action.

This central method specifies the central action-dependent (stochastic) transition relation

τ:A→(S×S→[0,1])
on S. With transitions specified by τ(a)(s,sʹ)

In usual cases, implementations can assume that action stems from some call to TransitionModel.actions(Object), and statep is obtained from TransitionModel.states(Object,Object).

Deterministic case. Will only return ≠0 for the unique sʹ = t(s,a). So the only true information obtained is the immediate action cost of the transition, plus any (optional) problem-specific additional information.

Specified by:
transition in interface GeneralSearchProblem
Specified by:
transition in interface TransitionModel
Parameters:
a - the action a∈A(s) that must be applicable in state s∈S.
s - the source state s∈S prior to the transition.
sp - the resulting state sʹ∈S after the transition took place.
Returns:
τ(a)(s,sʹ) which is the probability P(sʹ|s,a) of reaching state sʹ∈S when performing action a∈A(s) in the state s∈S. Usually represented as a transition which may contain additional information.
See Also:
Functions.diracDelta

isSolution

public boolean isSolution(java.lang.Object s)
Description copied from interface: MarkovDecisionProblem
Check whether the given state is a goal state (a valid solution to the problem).

Optional variation: Search algorithms generally seek out for one single solution. In order to find all solutions to a problem, simply let this method store solutions and return false instead, until enough solutions have occurred. However, expanding solution nodes should result in an empty list at some time to ensure termination, then.

Specified by:
isSolution in interface MarkovDecisionProblem
Parameters:
s - the state s∈S to check for being a goal state.
Returns:
G(s), resp. whether s∈G.

getAccumulatedCostFunction

public MutableFunction getAccumulatedCostFunction()
Description copied from interface: GeneralSearchProblem
Get the accumulated cost function.

This function encapsulates read write access to the accumulated cost values. Search algorithms can accumulate cost for states by setting g(s) to the accumulate cost value, and later query that accumulate cost value again, by applying g.

The most simple way of providing such an accumulated cost function g, is to enrich states with a (private) field for accumulated cost that is accessible via g. So you can simply use S×R as states instead of S for storing accumulated cost values.

Since search algorithms may invoke this method several times, it should not perform too slow. So consider returning a single pre-initialized instance of the accumulate cost function.

Note that accumulated cost functions usually do not need to be cloned.

Specified by:
getAccumulatedCostFunction in interface GeneralSearchProblem
Returns:
the accumulated cost function g:S→R, mapping states s to their accumulated cost g(s). That function must map S to accumulated cost values g(s) represented as Reals.

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.