ai.search.informed
Class MAStarSearcherForIntCostFn<S extends SearchStateForIntCostFn>

java.lang.Object
  ai.search.SearchEngine
      ai.search.SearchEngineForIntCostFn<S>
          ai.search.informed.BestFirstSearcherForIntCostFn<S>
              ai.search.informed.MAStarSearcherForIntCostFn<S>

public class MAStarSearcherForIntCostFn<S extends SearchStateForIntCostFn>
extends BestFirstSearcherForIntCostFn<S>

This class represents a search engine that generates a search space from a given initial state and guided by a heuristic function. The initial state and the heuristic function must be given to this search engine at construction time.

Now the search can be started using the function doSearch(). Successors of the initial state will then be explored in the order determined by the heuristic function. The essential strategy is to expand those nodes first for which the current path cost plus the estimated distance to the closest goal state is smallest, i.e. nodes which appear to be on a shortest path to a goal state. The search will halt when a goal state has been expanded. The goal state and the path to it can then be inspected using the appropriate functions described in the SearchEngineForIntCostFn class.

Thus, a typical invocation would look something like this:

     SearchEngineForIntCostFn s = new MAStarSearcherForIntCostFn(
             initialState, heuristic, Long.MAX_VALUE, GRAPH, 100);
     s.doSearch();
     if (s.foundGoalState()) { ... }
 

To continue the search call doSearch() again and the search will be continued as far as possible. If the test for repeated states is switched on, continuing the search will not result in the discovery of alternative paths to an already discovered goal state, but in the discovery of alternative goal states, if any. Furthermore, paths through a goal state will never be considered.

An important feature of this SearchEngine is that it uses the available memory, but starts to delete search nodes from memory when it gets close to using all available memory. The memory limit is given by two parameters. Firstly, there is the heap given to the JVM using the -Xmx option. Secondly, there is a the percentage of this space that will be used, which can be set using setMemoryUsageLimit(float). This will take into account all memory used by all classes though, which means it may not work as expected if there are other threads in the same JVM filling up the heap.

Author:

Gerhard Wickler

Nested Class Summary

protected class	MAStarSearcherForIntCostFn.MbSearchNode
protected class	MAStarSearcherForIntCostFn.MbSearchQueue

Nested classes/interfaces inherited from class ai.search.SearchEngineForIntCostFn

SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>

Nested classes/interfaces inherited from class ai.search.SearchEngine

SearchEngine.GraphType

Field Summary

protected int	maxF the highest f-value that may appear in the queue
protected MAStarSearcherForIntCostFn.MbSearchQueue	open the search queue for unexplored (open) nodes (outer by fValue, inner by depth)

Fields inherited from class ai.search.informed.BestFirstSearcherForIntCostFn

dfTendency, h, hweight

Fields inherited from class ai.search.SearchEngineForIntCostFn

foundGoalNode, initialState

Fields inherited from class ai.search.SearchEngine

doInterrupt, doRepeatTest, searchLimit, searchStarted, traceStream, yieldFrequency

Constructor Summary

MAStarSearcherForIntCostFn(S state, IntCostHeuristic<S> heuristic, long limit, SearchEngine.GraphType structure, int maxF)
This constructor creates a new MAStarSearcherForIntCostFn for the given initial state, heuristic, search limit, type of search space, and f-value limit.

Method Summary

boolean	continuable() This function tests whether the search may be continued.
void	doSearch() This function must be called to start or continue the search.
int	getNodeLimit() This function returns the memory limit in as the number of nodes this search engine is allowed to keep in memory.
long	getNrOfExploredStates() This function returns the number of states that have been explored during this search.
long	getNrOfGeneratedStates() This function returns the number of states that have been generated during this search.
void	setMemoryAssessmentFrequency(int frq) This function sets the frequency with which the memory limit is adjusted.
void	setMemoryUsageLimit(float limit) This function sets the current memory limit.

Methods inherited from class ai.search.informed.BestFirstSearcherForIntCostFn

setBreadthFirstTendency, setDepthFirstTendency, setHeuristicWeight

Methods inherited from class ai.search.SearchEngineForIntCostFn

foundGoalState, getGoalState, getInitialState, getSolutionDepth, getSolutionPath, getSolutionPathCost

Methods inherited from class ai.search.SearchEngine

clone, equals, getSearchLimit, hashCode, interrupt, printTrace, setSearchLimit, setTraceStream, setYieldFrequency, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

maxF

protected int maxF

the highest f-value that may appear in the queue

open

protected MAStarSearcherForIntCostFn.MbSearchQueue open

the search queue for unexplored (open) nodes (outer by fValue, inner by depth)

Constructor Detail

MAStarSearcherForIntCostFn

public MAStarSearcherForIntCostFn(S state,
                                  IntCostHeuristic<S> heuristic,
                                  long limit,
                                  SearchEngine.GraphType structure,
                                  int maxF)

This constructor creates a new MAStarSearcherForIntCostFn for the given initial state, heuristic, search limit, type of search space, and f-value limit. The search does not start immediately but waits for the function doSearch() to be called.

Parameters:

state - the initial state from which the search space is generated

heuristic - the heuristic function that guides the search

limit - the initial value for the search limit

structure - TREE or GRAPH, depending on what is to be be searched

maxF - the highest expected f-value

Method Detail

doSearch

public void doSearch()

This function must be called to start or continue the search. It will only return when one of the following conditions becomes true:

• a goal state has been found: in this case SearchEngineForIntCostFn.foundGoalState() will return true, the search will be continuable (continuable() usually will return true), and SearchEngineForIntCostFn.getGoalState() will return a goal state, not null
• the search limit has been reached: in this case SearchEngineForIntCostFn.foundGoalState() will return false, the search will not be continuable (continuable() will return false), and SearchEngineForIntCostFn.getGoalState() will return null; to make the search continuable the search limit has to be increased using SearchEngine.setSearchLimit(long)
• the search space has been exhausted: in this case SearchEngineForIntCostFn.foundGoalState() will return false, the search will not be continuable (continuable() will return false), and SearchEngineForIntCostFn.getGoalState() will return null

Specified by:

doSearch in class SearchEngine

continuable

public boolean continuable()

This function tests whether the search may be continued. Usually this is the case if there are more search states to be explored and the search limit has not yet been exceeded.

Specified by:

continuable in class SearchEngine

Returns:

true if and only if there are more search states that can be explored

getNrOfExploredStates

public long getNrOfExploredStates()

This function returns the number of states that have been explored during this search. A state counts as explored when the goal test has been performed on the state and its successors have been generated.

Specified by:

getNrOfExploredStates in class SearchEngine

Returns:

the number of nodes that have been closed during this search

getNrOfGeneratedStates

public long getNrOfGeneratedStates()

This function returns the number of states that have been generated during this search. Note that these states may not all be different.

Specified by:

getNrOfGeneratedStates in class SearchEngine

Returns:

the number of states that have been generated during this search

getNodeLimit

public int getNodeLimit()

This function returns the memory limit in as the number of nodes this search engine is allowed to keep in memory. Note that this limit may change while the search is performed. Also, this number may be exceeded.

Returns:

the largest number of nodes that should be in memory

setMemoryUsageLimit

public void setMemoryUsageLimit(float limit)
                         throws java.lang.IllegalArgumentException

This function sets the current memory limit. This is given as a percentage of the heap size available to the JVM, i.e. it must be a value between 0.0f and 1.0f. The default value is currently 0.7f. Note that this limit applies to all memory used, not just the search engine.

Parameters:

limit - the percentage of total heap space that may be used

Throws:

java.lang.IllegalArgumentException - if (limit <= 0.0f) || (limit >= 1.0f)

setMemoryAssessmentFrequency

public void setMemoryAssessmentFrequency(int frq)

This function sets the frequency with which the memory limit is adjusted. By default this will happen every 256 generated nodes.

Parameters:

frq - the number of nodes generated before the next adjustment of the memory limit