orbital.algorithm.template
Class GaussSeidelDynamicProgramming

java.lang.Object
  orbital.algorithm.template.MarkovDecisionProcess
      orbital.algorithm.template.MarkovDecisionProcess.DynamicProgramming
          orbital.algorithm.template.GaussSeidelDynamicProgramming

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm, HeuristicAlgorithm

public class GaussSeidelDynamicProgramming
extends MarkovDecisionProcess.DynamicProgramming
implements HeuristicAlgorithm

Gauß-Seidel dynamic programming.

Gauß-Seidel dynamic programming is a variant of synchronous dynamic programming performing value iteration in a sequential "sweep" of all the states after each state backup. Due to this fact, it can even be seen half-way as asynchronous dynamic programming. For the same reason, Gauß-Seidel dynamic programming usually converges faster than sychronous dynamic programming.

Gauß-Seidel dynamic programming permanently uses a dynamic programming variant of value iteration for the sequence of utility functions U_k.

U_k+1(s) := min_a∈A(s) Q_U(s,a) where U(t) := U_k+1(t) ⇐ t<s U(t) := U_k(t) ⇐ t≥s

Author:

André Platzer

See Also:

DynamicProgrammingProblem, "A. Barto, S. Bradtke, and S. Singh. Learning to act using real-time dynamic programming. Artificial Intelligence, 72:81-138, 1995.", Serialized Form

Invariants:

getDiscount()∈[0,1]

Nested Class Summary

Nested classes/interfaces inherited from class orbital.algorithm.template.MarkovDecisionProcess

MarkovDecisionProcess.DynamicProgramming

Nested classes/interfaces inherited from interface orbital.algorithm.template.HeuristicAlgorithm

HeuristicAlgorithm.Configuration, HeuristicAlgorithm.PatternDatabaseHeuristic

Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm

EvaluativeAlgorithm.EvaluationComparator

Constructor Summary

GaussSeidelDynamicProgramming(Function heuristic, java.util.Collection states, double tolerance)

Method Summary

Function	complexity() Measure for the asymptotic time complexity of the central solution operation in O-notation.
protected Function	plan() Run the planning.
Function	spaceComplexity() Measure for the asymptotic space complexity of the central solution operation in O-notation.

Methods inherited from class orbital.algorithm.template.MarkovDecisionProcess.DynamicProgramming

createMap, getActionValue, getDiscount, getEvaluation, getGreedyPolicy, getHeuristic, maximumExpectedUtility, setDiscount, setHeuristic

Methods inherited from class orbital.algorithm.template.MarkovDecisionProcess

getProblem, solve

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface orbital.algorithm.template.HeuristicAlgorithm

getEvaluation, getHeuristic, setHeuristic

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

solve

Constructor Detail

GaussSeidelDynamicProgramming

public GaussSeidelDynamicProgramming(Function heuristic,
                                     java.util.Collection states,
                                     double tolerance)

Parameters:

states - the full set S of all states of the problem.

tolerance - the tolerance value below which the evaluation function is considered to have converged.

Method Detail

plan

protected Function plan()

Description copied from class: MarkovDecisionProcess

Run the planning.

Specified by:

plan in class MarkovDecisionProcess

Returns:

the solution policy function S→A found, or null if no solution could be found.

complexity

public Function complexity()

Description copied from interface: AlgorithmicTemplate

Measure for the asymptotic time complexity of the central solution operation in O-notation.

Specified by:

complexity in interface AlgorithmicTemplate

Returns:

the function f for which the solve() method of this algorithm runs in O(f(n)) assuming the algorithmic problem hook to run in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

spaceComplexity

public Function spaceComplexity()

Description copied from interface: AlgorithmicTemplate

Measure for the asymptotic space complexity of the central solution operation in O-notation.

Specified by:

spaceComplexity in interface AlgorithmicTemplate

Returns:

the function f for which the solve() method of this algorithm consumes memory with an amount in O(f(n)) assuming the algorithmic problem hook uses space in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)