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 all subclasses. It calls primitive operations for accessing the frontier. By overriding the primitive methods TreeSearch can be turned into different kinds 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, delegates the search 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).

The SimpleProblemSolvingAgent is a concept for agent design which is based on search. Agents of this kind select a goal, reason about sequences of actions leading to a goal state, make a plan, and then execute it. An example of such an agent is the SimpleMapAgent 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. Map environments are especially suited for search concept evaluation because the state space can be visualized in 2D easily. Several graphical applications support experiments with maps of different size. Applications of the aima-gui project concentrate on the Romania scenario of the textbook (e.g. RouteFindingAgentApp). More realistic scenarios can be analyzed with applications in the aimax-osm project (e.g. ExtendedRouteFindingAgentOsmApp).

The concept of the SimpleProblemSolvingAgent is limited to scenarios, for which all relevant information is available in advance as the plan is blindly executed. Package aima.core.search.agent contains concepts for online scenarios as well. The ProblemSolvingAgent is a generalized version which can react to unforeseen events during plan execution by clearing the plan and then creating a new one. Alternatively, an agent can prepare for different possible scenarios during planning by generating a contingency plan. The NondeterministicSearchAgent uses AndOrSearch for this purpose. Consult NondeterministicVacuumEnvironmentDemo to see the agent in action.