orbital.algorithm.template
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

• a finite and discrete state space S.
• a finite set of actions A.
• sets of actions A(s)⊆A applicable in each state s∈S.
• a transition function t:S×A(s)→S; (s,a)↦t(s,a) mapping current states and chosen action to the next state. The deterministic transition function is wrapped in a transition model with a transition relation.
• action costs c:S×A(s)→R;(s,a)↦c(s,a)>0 for taking the action a∈A(s) in the state s∈S. Also note that there is no strict requirement for c(s,a)>0. Instead there are some criterions that ensure convergence even for c(s,a)∈[0,∞).
• an initial state s₀∈S.
• a set G⊆S of goal states. In fact, the explicit goal states are usually hidden in a mere "blackbox" predicate goal query G⊆℘(S).

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

• K(s,t) := min {∑ⁿ_i=0c(s_i,a_i) ¦ n∈N, s₀=s, s_i+1:=t(s_i,a_i),s_n=t,a_i∈A(s_i)} is the minimum accumulated cost for going from s∈S to t∈S.
• h^*(s) := min K(s,G) is the effective cost function for the best path from s.
• g^*(s) := K(s₀,s) is the minimum cost needed to reach s.
• f^*(s) := g^*(s) + h^*(s) is the minimum cost for paths going through s.

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.

Author:

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

MarkovDecisionProblem.DefaultTransition

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

isSolution

Method Detail

getInitialState

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.

Returns:

s₀ ∈ S.

Postconditions:

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

getAccumulatedCostFunction

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.

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.

Postconditions:

RES == OLD(RES)

Attributes:

secret storage of accumulated cost values of states

actions

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

• conservatively provide an iterator over a list that has been explicitly constructed.
• explicitly implement and provide a problem-specific iterator that constructs the actions leading to successor states on demand.
• or use the StreamMethod connector to provide an implicit yet constructive iterator in a very simple way.

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

Parameters:

state - 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

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

Parameters:

action - the action a∈A(s) that must be applicable in state s∈S.

state - the state s∈S.

Returns:

a list of states sʹ∈S that could be reached when performing the action a in the state s.

Postconditions:

super ∧ ¬(RES.hasNext() after RES.next())

transition

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

τ: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 TransitionModel

Parameters:

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.

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

Postconditions:

RES.getProbability()∈{0,1} ∧ RES instanceof GeneralSearchProblem.Transition