The AISEARCH library contains a number of search algorithms that may be used to solve a wide variety of problems. The purpose of the library is to enable the programmer to concentrate on the representation of the problem, not the implementation of a particular search algorithm. As a side benefit, the library encourages standardization by declaring a number of functions virtual, thus forcing the programmer to actively attend to their implementation.

As a sample problem, consider the 8-puzzle. The 8-puzzle consists of eight numbered, movable tiles set in a 3 X 3 frame. One of the cells of the frame is always empty, which makes it possible to move the tiles.

A sample 8-puzzle is shown in the figure below. Consider the problem of transforming the first configuration into the second one, the goal.

The 8-puzzle

2 1 6     1 2 3
4 0 8 --> 8 0 4
7 5 3     7 6 5

An operator transforms one configuration into another. In the case of the 8-puzzle it is most natural to think of four such operators, each corresponding to moving the empty tile: move empty tile left, move empty tile right, move empty tile up, move empty tile down.

The preceding description defines the problem-solving process in terms of a state space search. In a state space search the object is to reach a certain goal state (configuration), having started in an initial state, As it moves from an initial state to the goal, a problem such as the 8-puzzle can be in a finite number of possible configurations. All of these configurations together, i.e., all possible configurations, make up the state space. Defining the state space explicitly by enumerating all states is usually impossible; fortunately, in most cases providing rules specifying how each state can be derived from another will define the state space implicitly. For most problems the state space is so large that it would be impossible to explore the entire space, but often this is not needed, because finding one solution to a problem will be enough — i.e., one path leading from the start state to the goal state. Finding this one path usually entails not an exhaustive search, but can be accomplished by searching only a portion of the state space. The problem of course is, which portion?

In addition to selecting a portion of state space to search, the would-be problem solver must also specify a search direction. A search may proceed in two directions: if it moves forward from the start state, it is called forward reasoning. If the search begins with the goal as the start state and moves backward (often just as viable a strategy), it is called backward reasoning. These two techniques can be combined, resulting in a bidirectional search: it proceeds forward from the start and backward from the goal simultaneously, until the two paths meet somewhere in between. Choosing the right technique can make a big difference in the efficiency of the search.

Another search technique is the uniform-cost search, which is used to find the optimum solution to a problem. This technique is required when, for instance, finding the shortest route between two cities. In this case it is not sufficient just to find any route — only the shortest (the optimum solution) will do. To guarantee that the optimum solution (also called the cheapest path) will be found the algorithm associates a cost with every node in the search tree. These costs enable the algorithm to select the cheapest nodes so far for expansion. Instead of expanding paths of equal length (like the breadth-first method), the uniform-cost search technique expands paths of equal cost. The cost associated with a node consists of the cost associated with its parent plus the cost of getting from the parent to the node. The function used to compute this cost is usually called g(n).

The preceding discussion demonstrated that problems can be solved using standard techniques, such as the state-space representation and search. AISEARCH enables the programmer to easily incorporate these standard techniques into an application when designing problem-solving software. AISEARCH offers these standard techniques in the form of foundation classes. Each class implements a particular search algorithm while leaving open the exact nature of the problem to be solved. Using these classes the programmers can concentrate on the representation of the problem at hand without having to worry about how the problem has to be solved. This sort of freedom is also offered by declarative languages, such as Prolog; but unlike Prolog, AISEARCH does not restrict the programmer to a fixed search method. (Prolog implements depth-first seach only.)

• Depth-first search, both tree search and graph search
• Breadth-first search, idem.
• Uniform-cost search, idem.
• Best-first search
• Bi-directional depth-first search, idem.
• Bi-directional breadth-first search, idem.
• AND/OR depth-first search, tree search only
• AND/OR breadth-first search, tree search only

class PUZZLE_: public DEPTH_GRAPH
// select depth first
{
   ...
};

Determining the search algorithm is only one part of the problem-solving process. What's left is developing the problem representation. The programmer puts together this representation by using class NODE_ or one of its derivatives. Class NODE_ specifies a general structure that is to be processed by different search classes. (Note that some search classes must be used in combination with a derivative of class NODE_ rather than with NODE_ itself, see manual.) The programmer turns the problem representation into a class that is derived from class NODE_ (or from one of its derivatives, depending on the search class that is used), like this:

class PNODE_: public NODE_{ ..... };

PUZZLE_::PUZZLE_(PNODE_ *start, PNODE_ *goal )
   :DEPTH_GRAPH_(start, goal, 4)
{  // pass start node, goal node and number of
}  // operators to DEPTH_GRAPH_'s constructor

Class NODE_ also has a number of virtual functions that must be instantiated by the programmer. One of the most important is do_operator, used for expanding a node. do_operator's definition appears as follows:

NODE_ *do_operator(int) const
// apply operator n and
// return new node or NULL

Some problems, however, do not have a fixed number of operators at each node. For example, in the route-finding problem, there generally will be a variable number of roads leading from one city to other cities. In this case it would be easier to apply all the operators (if they can be called that) at once and return the resulting new nodes together. Such is the operation of function expand, which returns a linked list of all node successors:

NODE_ *expand(int) const
// expand node and return all of
// its successors in a linked list

Barr, A., Feigenbaum, E.A. The Handbook of Artificial Intelligence. Los Altos: Kaufmann, 1983.

Nilsson, N.J. Problem Solving Methods in Artificial Intelligence. New York: McGraw-Hill, 1971.

Nilsson, N.J. Principles of Artificial Intelligence. Los Altos: Kaufmann, 1986.

Knuth, D.E. The Art of Computer Programming, (2nd ed.). London: Addison-Wesley, 1979.

Pearl, J. Heuristics: Intelligent Strategies for Computer Problem Solving. London: Addison-Wesley, 1984.

Rich, E. Artificial Intelligence, New York: McGraw-Hill, 1983.