CSW 4701- Artificial Intelligence
                             A* Search ALGORITHM


The A* (Ordered-) SEARCH seen today in class searches for the MINIMAL COST
PATH from the initial node to the goal node(s) using BOTH the ghat value
and the hhat value.  Recall that f = g + h and we seek the solution path
with minimal f value.  

A* maintains the total path costs in each node as well as their heuristically
estimated path cost to a goal state,  and chooses paths
for expansion that have been found to be of minimal fhat cost so far.

Once again: 
 The minimal cost path from the initial node to any arbitrary node in the 
 state space is called the G-HAT value of the node, while 
 The estimated minimal cost path from the node to a goal node is called
 the H-HAT value.


(FOR LISP:

YOU MUST update your node representation to be:

   (State Operator-name G-hat H-hat Parent-Node)

and include a new accessor function:


(Defun State (node) (first node))
(Defun Operator (node) (second node))
(Defun G-hat (node) (third node))
(Defun H-hat (node) (fourth node))
(Defun Parent (node) (fifth node))

Remember, that the successor-generator function now has to be updated
to include the COST function that is now part of the problem-solving
formulation as well as the HEURISITC EVALUATION function. Since we are 
searching for  the minimum cost solution path ;over all possible solution 
paths, someone  has to provide us with the COST function 
as part of the problem definition. SOMEONE LIKE YOU HAS TO PROVIDE THE
HEURISITC EVALUATION FUNCTION. 

Here is the A* search algorithm. YOU CAN UPDATE THE UNIFORM-COST SEARCH CODE 
TO INCORPORATE THE NEW PROVISIONS OF THIS ALGORITHM:


1. PUT INITIAL STATE S0 ON OPEN 
                 WITH GHAT(S0) = 0, AND 
                      HHAT(S0) = HEURISITIC VALUE CALCULATED BY YOUR FUNCTION

2. IF OPEN IS EMPTY, EXIT WITH FAILURE (NO SOLUTION)

3. REMOVE FROM OPEN THE NODE WITH THE MINIMAL FHAT VALUE, (I.E. GHAT + HHAT)
     -CALL IT N
     -IF N CONTAINS A GOAL STATE, EXIT WITH SUCCESS
     -ADD N TO CLOSED

4. FOR ALL M IN SUCCESSORS(N) DO THE FOLLOWING:

   4.1 IF STATE(M) IS NOT ON OPEN OR CLOSED THEN
         -ADD M TO OPEN
         -SET GHAT(M) = GHAT(N) + COST(M,N)
         -SET HHAT(M) = COMPUTE ITS HEURISTIC VALUE

   4.2 IF STATE(M) IS ON OPEN THEN
         -IF GHAT(M ON OPEN) > GHAT(N)+COST(N,M) THEN RESET 
                                    GHAT(M ON OPEN) TO NEW GHAT(N)+COST(N,M)
                                AND REDIRECT THE PARENT(M ON OPEN) TO N
   4.3 IF M IS ON CLOSED THEN
         -IF GHAT(M ON CLOSED) > GHAT(N)+COST(N,M) THEN RESET 
                                    GHAT(M ON CLOSED) TO NEW GHAT(N)+COST(N,M)
                                AND REDIRECT THE PARENT(M ON OPEN) TO N
                       *********AND MOVE M ON CLOSED BACK TO OPEN!!!!*********
5. GO TO 2






Now, one final word.  Look at 4.2 and 4.3.  Remember that we needed
4.2 in the uniform cost search algorithm in the case we find a better
way to get to a node that has not yet been expanded. But in the uniform
cost search we didn't need to worry about finding a cheaper path to a
node on the closed list. Once it was closed, there cannot be any other
cheaper paths to it.

But in A* this is NOT the case. Since we are choosing on the basis of fhat
values, the hhat value can be a terribly wrong estimate of the true
h value, and hence a node that has been closed already may have a better
cheaper path to it. 

FOR EXAMPLE: IMAGINE A NODE (N1) WITH STATE X AND GHAT OF 100 AND HHAT OF 2
             node N1 looks something like (X OP 100 2 P1)

NOW LET'S SAY NODE N1 WAS EXPANDED BECAUSE ITS FHAT VALUE (OF 102) WAS 
CHEAPEST.  ITS GENERATED CHILDREN ARE THEN PLACED ON OPEN.

NEXT WE CHOOSE ANOTHER NODE FROM OPEN AND EXPAND IT, LET'S SAY THIS NODE N2
HAS STATE Y WITH GHAT 90 AND HHAT 15 (FHAT IS THEREFORE 105)
             node N2 looks something like (Y OP 90 15 P2)

NEXT WE EXPAND NODE N2 AND ONE SINGLE CHILD NODE CALLED M CONTAINS STATE X. 
THIS NEW CHILD NODE M HAS STATE X GGHAT 91 AND HHAT 2.
             node M looks something like (X OP 90 2 N2)

WHAT WENT WRONG?  HHAT SCREWED UP ON N1. IT GROSSLY OVERESTIMATED HHAT WITH
15 MAKING N1 CHOSEN FOR EXPANSION WHEN CLEARLY M IS PREFERED.

TO REPAIR THIS CASE, WE HAVE TO UPDATE N1 TO THE CHEAPEST PARENT (N2), AND
WE MUST UPDATE THE CHILDREN THAT N1 GENERATED.

BOTTOM LINE: WE CAN NO LONGER GUARANTEE THAT NODES ARE EXPANDED IN OPTIMAL
GHAT VALUE ORDER SINCE HHAT MAY OVERESTIMATE. HOWEVER, AS LONG AS HHAT IS
BOUNDED ABOVE BY H THIS WILL NOT OCCUR.

With that in mind, 4.3 is added to the algorithm to handle the case of
bad hhat evaluations:

But remember we said that since N1 was closed, then we expanded it
before, and thus its children are also incorrectly evaluated? Their ghats
must be wrong and need to be updated. NOTE THE CLEVERNESS IN STEP 4.3.
By putting the node back on the OPEN list with an updated ghat value and
redirected parent pointer, then later we may reexpand that node, regenerate 
its children, search for them on open and closed, and hence update them 
too correctly later as needed.

Isn't that cool?


As for the code for this problem, I sent it already: Uniform Cost
Search code in LISP is all that you need to get started. You simply
have to change that code to choose by MINIMUM Fhat, and handle the
case that the successor node is on the CLOSED list (and put it back
on OPEN accordingly when necessary).



regards

sal