5.1 The A* algorithm in Prolog

Section 2.16 introduced an outline for a simple Prolog search program. This section discusses heuristic search using the A* algorithm, due to Nilsson (1980).

Heuristic search uses a heuristic function to help guide the search. When a node is expanded, each of its children is evaluated using a search function. Each child is placed into a list of nodes -- the so-called open list -- in order determined by the search function evaluation (smaller values first). The heuristic function estimates how much work must be done to reach a goal from the node in question. Typically, the search function f is expressed as

Fig. 5.1

Here is some simple pseudocode from which the Prolog program will be developed.

1. Start with the start node, place it in the (previously empty) list open.
2. Let n be the first node on open. Remove n from open. Fail if open is empty.
3. If n is the goal, then a solution has been found. (One could stop here.)
   
4. Expand n, obtaining all of its children, and evaluate f(-) for each of them. Insert each of these children into open, maintaining order where the smallest f(-) values come first.
5. Repeat from step 2.

When a goal has been reached, one would certainly like to be able to return the solution path from the start to the goal. The pseudocode ignored this feature, but it will be included as the Prolog prototype program is developed.

A common cost function g(-) is path length. The cost of getting from the start node to a current node is the length of relevant path. This can be computed incrementally, as will be seen.

It is important to realize that this kind of search can follow a contiguous path for a while, until some previously unchosen node n has the current smallest f(-) value, in which case this node n is expanded, and its children considered.

Now for the Prolog program for the A* search.

Let us assume that State refers to some description of the state of a search. For example State might be a description of the 8-puzzle tile for a specific configuration, as developed in the next section. A Node in the search space (or graph) needs to record the State, the Depth (or path length from the start), the value of f(-) for the node F, and a list of the ancestors A of this node. We will use the Prolog term structure

• The state of each child will be computed as a move from State
• each of these children will have depth Depth + 1,
• the f(-) value of each child will be calculated, and
• the ancestor list of a child will be the Prolog list term [Node|A].

In general, if the Depth is replace by some other cost, the node representation would be similar; just replace Depth by a cost, and compute it appropriately. Also, we will see in the next section (8-puzzle) that the ancestor list might be more conveniently saved as a list of symbolic actions (used to achieve successive states), rather that as a list of the actual full nodes themselves. Other modifications of the prototypical A* algorithm presented in this section might be made, depending on the application.

The main predicate for the program is

solve(Start,Soln) :- f_function(Start,0,F),
                     search([Start#0#F#[]],S),
                     reverse(S,Soln).

f_function(State,D,F) :- h_function(State,H),
                         F is D + H.

search([State#_#_#Soln | _], Soln) :- goal(State).
search([B|R],S) :- expand(B, Children),
                   insert_all(Children, R, NewOpen),
                   search(NewOpen,S).

expand(State#D#_#A, All_My_Children) :-
         bagof(Child#D1#F#[Move|A],
               ( D1 is D + 1,
                 move(State,Child,Move),
                 f_function(Child,D1,F) ) ,
               All_My_Children).  

The (application dependent) 'move' predicate should generate the 'Child' states, in such a way as to obtain them all by backtracking. (See the 8-puzzle example in the next section.) As previously stated, the 'Move' can either be the the whole parent node itself or some appropriate substitute. (Actually, one should rewrite the 'expand' clause if one is going to use the whole node, rather some symbolic representation, as we do in the next section.)

Here is the code for insert_all. It is a familiar kind of insertion-sort algorithm ...

insert_all([F|R],Open1,Open3) :- insert(F,Open1,Open2),
                                 insert_all(R,Open2,Open3).
insert_all([],Open,Open).

insert(B,Open,Open) :- repeat_node(B,Open), ! .
insert(B,[C|R],[B,C|R]) :- cheaper(B,C), ! .
insert(B,[B1|R],[B1|S]) :- insert(B,R,S), !.
insert(B,[],[B]).

repeat_node(P#_#_#_, [P#_#_#_|_]).

cheaper( _#_#H1#_ , _#_#H2#_ ) :- H1 <  H2.

The following exercises ask the reader to formulate A* solutions to various problems or puzzles. See the next section, 5.2 on the 8-puzzle, as an example of how to extend the general A* program of this section to a specific solution of the 8-puzzle.

Exercise 5.1.1 Formulate an A* algorithm for the N queens puzzle. (See section 2.11 for a simple, but inefficient, approach.)

Exercise 5.1.2 Formulate an A* approach to maze solving.