Orbital library

Interface GeneralSearchProblem

Type Parameters:
A - the type of transition actions.
S - the type of transition states.
All Superinterfaces:
AlgorithmicProblem, MarkovDecisionProblem, TransitionModel
All Known Implementing Classes:
DelegateGeneralSearchProblem, OpenClosedGeneralSearchProblem

public interface GeneralSearchProblem
extends MarkovDecisionProblem

Hook class for GeneralSearch algorithm. Objects implementing this interface represent a state model.

A state model is a mathematical model for making sense of some classes of problems. Apart from action costs, it is essentially a deterministic (finite) automaton to control. A state model is characterized by

The applicable actions A(s) then span the search space as a graph G=⟨S,{⟨s,t(s,a)⟩ ¦ s∈S, a∈A(s)}⟩. Its solution is a sequence of applicable actions that leads from an initial state to a goal state. A solution is optimal if it has minimum cost.

Derived values

To be precise, most search algorithms even require locally finite graphs G (i.e. with finite branching factors) that have costs that "keep away from zero", i.e.

∃ε> 0 ∀s∈S∀a∈A(s) c(s,a) > ε
to achieve completeness.

Solving state models can produce an open-loop plan for control.

For defining a state model, several representation models may be of use, even including genetic data models.

André Platzer
See Also:
GeneralSearch, BacktrackingProblem, MarkovDecisionProblem

Nested Class Summary
static class GeneralSearchProblem.Transition
          Represents an option node during a search problem.
Nested classes/interfaces inherited from interface orbital.algorithm.template.MarkovDecisionProblem
Method Summary
 java.util.Iterator actions(java.lang.Object state)
          Get the applicable actions at a state.
 MutableFunction getAccumulatedCostFunction()
          Get the accumulated cost function.
 java.lang.Object getInitialState()
          Get the initial state of the problem.
 java.util.Iterator states(java.lang.Object action, java.lang.Object state)
          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 action, java.lang.Object state, java.lang.Object statep)
          Get (information about) the transition from a state to another state under a given action. Deterministic case.
Methods inherited from interface orbital.algorithm.template.MarkovDecisionProblem

Method Detail


java.lang.Object getInitialState()
Get the initial state of the problem.

Note that a single initial state is no restriction since one can always introduce 0-cost transitions from a single artificial initial state to a set of true initial states without affecting the search problem.

Make sure that this method consistently returns the initial state even for repeated invocations, since some iterative search algorithms may rely on this feature.

s0 ∈ S.
getAccumulatedCostFunction().apply(RES) = 0 ∧ (RES==OLD(RES) or problem changed)


MutableFunction getAccumulatedCostFunction()
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.

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.
secret storage of accumulated cost values of states


java.util.Iterator actions(java.lang.Object state)
Get the applicable actions at a state.

Intuitively, applicable actions are those that result in a valid transition. So for a state, the applicable actions are the only actions relevant for leaving that state with any transition (including transitions that lead back to the state the transition just started in).

For several reasons (including performance) it is widely recommended that

A(s) = {a∈A ¦ ∃sʹ∈S∖{⊥} P(sʹ|s,a)>0} = {a∈A ¦ τ(a)(s,⊥)≠1} = A∖τ-1({s}×{⊥}) = τ(a)(s,·) = (τ(a)(s,·))-1((0,1])
In fact, this is not a strict requirement, if the computation would be far too expensive. However, the TransitionModel implementation would then have to deal with cases where an action was chosen that has later been found out to be inapplicable, contrary to the initial guess of TransitionModel.actions(Object). Since this may result in rather messy implementations, relieving this requirement should generally be limited to very specific and well documented cases.

Searching often does not explicitly refer to the actions taken, but they usually form the relevant part of a solution.

Note: the return-type is Iterator in order to increase space efficiency for problems with a good expand-on-demand behaviour. Additionally, this enables implementations to use do/undo for expanding states. Implementations can either

Also note that if an implementation of states(Object,Object) wants to optimize memory performance for the cost of limiting it to search algorithms based on depth-first search, then it can apply the do/undo technique. Alternatively, if applicable actions can be determined quickly but constructing the resulting states is expensive, the (usual) approach of lazy state construction can be used. In order to achieve this, let actions(Object) return actions, without constructing any states. Then states(Object,Object) performs lazy construction of resulting states on every call. However, this technique is not that powerful as do/undo, and it is less useful if the calculation of costs depends on the specific resulting states anyway. Nevertheless, it is much more simple to implement.

Specified by:
actions in interface TransitionModel
state - the state s∈S whose applicable actions to determine.
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:


java.util.Iterator states(java.lang.Object action,
                          java.lang.Object state)
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 TransitionModel
action - the action a∈A(s) that must be applicable in state s∈S.
state - the state s∈S.
a list of states sʹ∈S that could be reached when performing the action a in the state s.
super ∧ ¬(RES.hasNext() after RES.next())


TransitionModel.Transition transition(java.lang.Object action,
                                      java.lang.Object state,
                                      java.lang.Object statep)
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

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 TransitionModel
action - the action a∈A(s) that must be applicable in state s∈S.
state - the source state s∈S prior to the transition.
statep - the resulting state sʹ∈S after the transition took place.
τ(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:
RES.getProbability()∈{0,1} ∧ RES instanceof GeneralSearchProblem.Transition

Orbital library
1.3.0: 11 Apr 2009

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