orbital.algorithm.template
Class HeuristicAlgorithm.PatternDatabaseHeuristic

java.lang.Object
  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.