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