; CSW 4701- Artificial Intelligence ; MORE Search Programs in LISP ;The UNIFORM COST SEARCH seen today in class searches for the MINIMAL COST ;PATH from the initial node to the goal node(s). ;It does so by maintaining total path costs in each node and choosing paths ;for expansion that have been found to be of minimal cost so far. ;That is nothing more than the total cost of each transition to that node ;starting at the initial node. 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. ;Thus, we update our node representation to be: ; (State Operator-name G-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 Parent (node) (fourth 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. Since we are searching for the minimum cost solution path ;over all possible solution paths, someone (like Charlie) has to provide ;us with the COST function as part of the problem definition. We saw ;the traveling salesman problem today that is a good example of problems ;with inherent costs defined by reality! ;Here is the uniform cost search algorithm in LISP (defun uniform-cost-search (s0 sg sons) (let ( ( open (list (list s0 nil 0 nil) ) ) ;note the inner list is a node ;g-hat set to 0 ( closed nil ) ( n nil ) ( daughters nil )) ;ok, here we go: (loop (if (null open) (return 'fail)) ;failure, oh well.... (setf n (pop open)) ;Ok, remove the first node ;and update open and (push n closed) ;update closed with n since we expand it next ; Recall that we maintain open and closed lists so that we ; do not "loop" forever through the search space by visiting ; states we've previously explored. Here now we have to also ; concern ourselves with MAINTAINING THE MINIMAL COST PATHS WE FIND ; TO ANY STATE IN THE STATE SPACE. (if (**equal** (state n) sg) ;have we found our goal state? ;remember (state n) = (first n) ;and **equal** has to be general (let () ;OK...for free, I fixed this bug for you (print "Great. I found a solution. Here it is:") (return (trace-solution n)))) ;AND ITS THE MINIMAL COST SOLUTION ;GUARANTEED!!! TAKE IT TO THE BANK (setf daughters (apply sons n)) ;here we generate new derived states (setf daughters (DIFF daughters closed)) ;Remove duplicate states ;previously explored and residing on closed. REMEMBER, THE ;NEW PATH TO THIS STATE THAT WE HAVE PREVIOUSLY EXPANDED MUST ;BE MORE EXPENSIVE SO WE JUST ELIMINATE IT FORM OUR CURRENT ;LIST OF DAUGHTER NODES. ;BUT NOW WE HAVE TO KEEP THE CHEAPEST DAUGHTER NODES ON OPEN (setf open (UPDATE daughters open)) ; now watch this function in action below (setf open ;LOOK HERE...WE'RE SORTING THE OPEN LIST FROM MIN G-HAT TO MAX (sort open '(lambda(node1 node2) (< (g-hat node1) (g-hat node2))))) ;ends setf ;By taking the fist node off of OPEN, above in the loop, then ;we are assured of expanding the next cheapest path ) ;closes loop ) ;closes let ) ;closes defun ;Here is the update function that maintains the cheapest path to a state ;by keeping the node on open with minimum g-hat value (defun UPDATE (daughters open) (let ( ( m nil ) (found-old-m nil) ) (loop ;another one of those simple loops over the list of nodes (if (null daughters) (return open)) ;if we processed them all, we're done.. (setf m (pop daughters)) ;let's work on the first chid node (setf found-old-m (MEMBER-STATE (state m) open)) ; did we find it on open? ;MEMBER-STATE is defined below... ;if so, found-old-m will be the sublist of open starting at ;the place where we found it (if found-old-m ;if we found an old m on the open list (let ((old-m (first found-old-m))) ;extract the node with the same state (if (< (g-hat m) (g-hat old-m)) ;if the new child's ghat value is ;CHEAPER ;than the old child previously generated ;we certainly want to keep the new one (setf (first found-old-m m))) ) ;so simply make the old child garbage and ;replace it with the new child, m!!! ;Please notice that this makes a ;destructive change to OPEN.... (push m open)) ;otherwise we didn't find an old node with the same state ;so simply add m to open This expression is the else ;part of the if statement above. ) ;ends loop, try the next daughter node ) ;ends let ) ;end defun ;This next function simply returns the sublist where a node has been found ;to contain a state that is **equal** to the first argument "state": (Defun MEMBER-STATE (state list-of-nodes) (if (null list-of-nodes) ;if exhausted then nil ;return nil (if (**equal** state (first list-of-nodes)) ;else if we find one list-of-nodes ;return where we found it (MEMBER-STATE (rest list-of-nodes))))) ;else keep looking recursively ;Here is how you must update your successor generator: (defun successor-function (node) (let ( (son-nodes nil) (son-states nil) (state (first node)) ) (setf son-states (operator-ONE state)) ;apply problem dependent operator 1 ;NOW LOOK HERE: SEE HOW THE GHAT VALUE OF THE NEW SON STATE IS UPDATED ;BY THE SUM OF THE GHAT OF THE PARENT NODE, PLUS THE COST OF GETTING TO ;THE SON STATE FROM THE PARENT STATE. THIS COST FUNCTION IS PROBLEM DEPENDENT ;AND IS PROVIDED SEPARATELY AS PART OF THE PROBLEM FORMULATION (setf son-nodes (mapcar son-states '(lambda(son-state) (list son-state 'ONE (+ (g-hat node) (COST (state node) son-state)) node)))) ;here we create ;a list of nodes! (setf son-states (operator-TWO state)) ;and we repeat for each operator ;please note this function is incomplete...you have to fill out the ;rest of the operator applications as appropriate.... (return son-nodes))) ;and that's it. Son-nodes is returned by the function ;THE REST OF THE MACHINERY PROVIDED EARLIER IS STILL USED HERE. THE OTHER ;FUNCTIONS NEED NOT CHANGE. ;NOW, HERE'S ANOTHER \$64K QUESTION (ANOTHER CHANCE FOR ONE OF THOSE A'S): ;IF COST(SI, SJ) = 1 ALWAYS, WHAT IS THIS SEARCH FUNCTION ACTUALLY DOING? ;WHAT IS G-HAT IN THIS CASE? ;THE ANSWER IS: ;--------------------------------------- (WRITE THE ANSWER ON THIS LINE, ;EXCISE IT FROM THIS MSG AND MAIL IT BACK TO SAL@CS.COLUMBIA.EDU ;5.......4.......3........2........1.........AHHHHHHHHH....TOO LATE..... ;but send it in anyway to let me know that you got my message.....