AIMA3e Search Framework

About the design of the 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, by providing implementations of the required functional interfaces to the constructor of class GeneralProblem (e.g. in NQueensFunctions), or by subclassing 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 repeated work or 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 (a search execution strategy). The most important implementations are TreeSearch, GraphSearch4e, and BidirectionalSearch.

Class TreeSearch relies on the template method design pattern. The template method findNode is shared by most subclasses. It calls primitive operations for accessing the frontier. By overriding the primitive methods TreeSearch can be turned into differend kindes of GraphSearch.

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 NodeFactory class provides base functionality for node creation and successor computation. 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 parent links on, those algorithms can be turned into search for actions algorithms (though the resulting paths will seldom be optimal). Additionally, the common node factory component unifies progress tracking for all search algorithms. It informs all registered node listener about expanded nodes. This common infrastructure makes it easy to compare the performance of different algorithms based on the same example problem (see e.g. NQueensDemo).

A SimpleProblemSolvingAgent is an agent which is based on search. It reasons about sequences of actions leading to a goal state, makes a plan, and then executes it. The ProblemSolvingAgent is a generalized version which can react to unforseen events during plan execution. An example of such an agent is the MapAgent which tries to find the shortest path from the current location to a goal location based on map information (see e.g. MapAgentDemo how to use it).