;                       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.....