orbital.algorithm.template
Class OpenClosedGeneralSearchProblem

java.lang.Object
  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:

s₀ ∈ 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.