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