Package aima.core.search.framework

This package (together with its subpackages) contains base classes for search algorithm implementations.

See: Description

Interface Summary

Interface	Description
NodeExpander.NodeListener	Interface for progress Tracers
PerceptToStateFunction	This interface is to define how to Map a Percept to a State representation for a problem solver within a specific environment.
SearchForActions	Interface for all AIMA3e search algorithms which store at least a part of the exploration history as search tree and return a list of actions leading from the initial state to a goal state.
SearchForStates	Interface for all AIMA3e search algorithms which forget the exploration history and return just a single state which is hopefully a goal state.
SolutionChecker	A specialization of the GoalTest interface so that it is possible to check the solution once a goal has been identified to determine if it is acceptable.

Class Summary

Class	Description
Metrics	Stores key-value pairs for efficiency analysis.
Node	Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.10, page 79. Figure 3.10 Nodes are the data structures from which the search tree is constructed.
NodeExpander	Instances of this class are responsible for node creation and expansion.
PrioritySearch	Performs search by creating a priority queue based on a given Comparator and feeding it to a given QueueSearch implementation which finally controls the simulated search space exploration.
ProblemSolvingAgent	Modified copy of class aima.search.framework.SimpleProblemSolvingAgent which can be used for online search, too.
QueueFactory	Factory class for queues.
SearchAgent
SearchUtils	Provides several useful static methods for implementing search.
SimpleProblemSolvingAgent	Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.1, page 67.

Package aima.core.search.framework Description

This package (together with its subpackages) contains base classes for search algorithm implementations. Common interfaces are defined by SearchForActions and SearchForStates. Most of the concrete algorithms implement both of them. Many search algorithms are basically queue-based algorithms. They construct a tree of nodes which represents the possible sequences of actions and the corresponding resulting states. A queue is used to manage and prioritize the current end points of already analyzed sequences.
Specializations are possible in two ways: There are different ways to define a queue (A), and to use the queue to explore the search space (B). (A) is about prioritizing nodes, which can be done by time (e.g. first come first serve), by comparator, or by evaluation function. (B) is about controlling the simulated exploration of the search space based on a given queue data structure. This includes strategies for filtering nodes to avoid getting stuck in loops.
To support arbitrary combinations of different strategies for (A) and (B), the bridge pattern is used here. Different abstractions of search (so called search strategies) are provided as specializations of PrioritySearch. They delegate the work of controlling the actual search to some QueueSearch implementation. The most important concrete implementations are TreeSearch, GraphSearch, and BidirectionalSearch.
Here, all search strategies explore the search space by expanding nodes. A central NodeExpander class is used for this purpose. The default implementation should work for most purposes, but it is possible to equip search algorithms with specialized versions (e.g. which modify path cost computation - extra costs for move direction changes). The node structure is needed when searching for sequences of actions (just follow parent links after a goal state node was found). Defining search for states (e.g. in a local search strategy) based on nodes makes sense, too. Nodes do not necessary increase space complexity as long as parent links can be switched off. However, by switching on parent links, those algorithms can be turned into search for actions algorithms. Additionally, the common node expander interface unifies progress tracing for all search algorithms (just add a node listener to get notifications about expanded nodes).

Author:

Ruediger Lunde