AIMA3e Search Framework
Search is about finding paths from an initial state to a goal state. The state space is defined by some problem formulation. In this framework, concrete problems can be described by implementing the general interface Problem or by providing implementations of the required functional interfaces to the constructor of class GeneralProblem (e.g. BidirectionalEightPuzzleProblem).
The following UML class diagram gives an overview of the AIMA3e search algorithm implementations:
All classes and interfaces are generic. They use type parameters for the types to represent states
S and actions A. 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 QueueBasedSearch. They
delegate the work of controlling the actual search to some QueueSearch implementation.
Abstract class QueueSearch relies on the template method design pattern. The template method
findNode is shared by most subclasses. It calls primitive operations for accessing
the frontier. Those primitive operations are provided by the concrete QueueSearch implementations,
especially by TreeSearch, GraphSearch, and BidirectionalSearch.
The following sequence diagram shows that the only special responsibility of UniformCostSearch
is to create a priority queue with a comparator, which sorts nodes with respect to their path costs.
The findActions implementation is the same for all QueueBasedSearch algorithms. It clears the queue,
delegated the seach to some QueueSearch implementation and translates the resulting node into a
sequence of actions.
In this framework, all search strategies explore the search space by expanding nodes. A central NodeExpander class is used for his 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 moving direction changes). The node structure is needed when searching for sequences of actions. The reverse sequence is obtained by following parent links to the root 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 (though the resulting paths will seldom be optimal). Additionally, the common node expander component unifies progress tracking for all search algorithms. It informs all registered node listener about expanded nodes.