Orbital library

orbital.algorithm.template
Class HeuristicAlgorithm.PatternDatabaseHeuristic

java.lang.Object
  extended by orbital.algorithm.template.HeuristicAlgorithm.PatternDatabaseHeuristic
All Implemented Interfaces:
java.io.Serializable, Function, Functor
Enclosing interface:
HeuristicAlgorithm

public static class HeuristicAlgorithm.PatternDatabaseHeuristic
extends java.lang.Object
implements Function, java.io.Serializable

An heuristic function that uses a pattern database.

This heuristic function uses a pattern database for better values or speedup. For states that are not yet known in the pattern database a backing traditional heuristic function is required. The patterns can either be build from the full or from a projected state space.

Within the pattern database this heuristic is optimal (i.e. h|P = h*|P for the part P of the state space that is handled by the pattern database) and for the full state space it is admissible. Still a good backing heuristic function is required for maximum performance.

Dynamically building or increasing a pattern database can be a worthwhile refinement of the pre-processing approach to pattern database creation, as it better adapts to the current problem's need. Either way, the basic idea of using a pattern database, especially in the presence of memoisation (dynamically improving the database during the search) is dynamic programming. Observe the close connection of pattern database heuristics and bidirectional search.

To massively reduce memory usage the pattern database could store hash codes instead of whole state objects. Then the state objects are assumed to have an appropriate Object.hashCode() implementation. Although this dramatically reduces memory usage then the heuristic relies on disjunct hash codes or may lose admissibility.

Author:
André Platzer
See Also:
"Memory-Based Heuristics: Pattern Databases. Culbersion & Schaeffer. 1995.", "Stefan Edelkamp. Symbolic pattern databases in heuristic search planning. In Ghallab, M. and Hertzberg, J. and Traverso, P., editors. Proceedings of the 7th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-02), Toulouse, France, April, 2002, AAAI Press, Menlo Park. pages 274-283", Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from interface orbital.logic.functor.Function
Function.Composite
 
Nested classes/interfaces inherited from interface orbital.logic.functor.Functor
Functor.Specification
 
Field Summary
 
Fields inherited from interface orbital.logic.functor.Function
callTypeDeclaration
 
Constructor Summary
HeuristicAlgorithm.PatternDatabaseHeuristic(Function backingHeuristic)
           
HeuristicAlgorithm.PatternDatabaseHeuristic(Function backingHeuristic, java.util.Map patternDatabase)
           
HeuristicAlgorithm.PatternDatabaseHeuristic(Function backingHeuristic, java.util.Map patternDatabase, boolean autoUpdatePatternDatabase)
          Create a new heuristic function supported by a pattern database.
 
Method Summary
 java.lang.Object apply(java.lang.Object o)
          Called to apply the Function.
 Function getHeuristic()
          Get the backing heuristic.
 java.util.Map getPatternDatabase()
          Get the pattern database.
 void setPatternDatabase(java.util.Map patterns)
          Set the pattern database.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface orbital.logic.functor.Functor
equals, hashCode, toString
 

Constructor Detail

HeuristicAlgorithm.PatternDatabaseHeuristic

public HeuristicAlgorithm.PatternDatabaseHeuristic(Function backingHeuristic,
                                                   java.util.Map patternDatabase,
                                                   boolean autoUpdatePatternDatabase)
Create a new heuristic function supported by a pattern database.

Parameters:
backingHeuristic - the heuristic function used for states not contained in the pattern database.
patternDatabase - the pattern database to use for looking up cost.
autoUpdatePatternDatabase - whether to enter heuristic estimate cost into the pattern database for states not yet contained. This is almost only useful for very expensive backing heuristic functions.

HeuristicAlgorithm.PatternDatabaseHeuristic

public HeuristicAlgorithm.PatternDatabaseHeuristic(Function backingHeuristic,
                                                   java.util.Map patternDatabase)

HeuristicAlgorithm.PatternDatabaseHeuristic

public HeuristicAlgorithm.PatternDatabaseHeuristic(Function backingHeuristic)
Method Detail

getHeuristic

public Function getHeuristic()
Get the backing heuristic.

Returns:
the heuristic function used for states not contained in the pattern database.

getPatternDatabase

public java.util.Map getPatternDatabase()
Get the pattern database.

Returns:
the pattern database used for looking up cost. It is a Map from states to cost.

setPatternDatabase

public void setPatternDatabase(java.util.Map patterns)
Set the pattern database.

Parameters:
patterns - the pattern database to use for looking up cost. It is a Map from states to cost.

apply

public java.lang.Object apply(java.lang.Object o)
Description copied from interface: Function
Called to apply the Function. Evaluates to f(a).

Specified by:
apply in interface Function
Parameters:
o - generic Object as argument
Returns:
returns a generic Object.

Orbital library
1.3.0: 11 Apr 2009

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