AIMA3e Search Framework

About the design of the search framework

The following UML class diagram gives an overview about the most important classes and interfaces of of the AIMA3e search implementation:

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. 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 comparator, which orders nodes with respect to their path costs. The findActions implementation is the same for all PrioritySearch algorithms. It creates a 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 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 (though the paths will seldom be optimal). Additionally, the common node expander interface unifies progress tracing for all search algorithms (just add a node listener to get notifications about expanded nodes).