Orbital library

orbital.algorithm.template
Class GaussSeidelDynamicProgramming

java.lang.Object
  extended by orbital.algorithm.template.MarkovDecisionProcess
      extended by orbital.algorithm.template.MarkovDecisionProcess.DynamicProgramming
          extended by 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 Uk.

Uk+1(s) := mina∈A(s) QU(s,a)
where
U(t) := Uk+1(t) ⇐ t<s
U(t) := Uk(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)

Orbital library
1.3.0: 11 Apr 2009

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