CMPU-365, Spring 2013 Asmt. 3 ---------------------------------------- ===> Due: Friday, Feb. 22 @ 5:00 p.m. ---------------------------------------- ===> NOTE: Solutions to assignment 2 will be posted on the course web site by Feb. 16th (i.e., approx. two days after asmt 2 is due). You may use solutions to asmt 2 for the General Search functions needed for this assignment. For this assignment you will implement both the Iterative Deepening Search (IDS) and A-star search algorithms. In addition, you will implement the Eights Tile Puzzle domain as your testing domain. You will implement both the Num-Tiles-Out-Of-Place and Manhattan-Distance heuristics. Your testing will compare the performance of IDS and A-star (testing both heuristics). *********************************************************** For this assignment, you are encouraged to work in PAIRS. Each PAIR need only submit one set of printouts/files. Be sure to clearly indicate the students in the pair!!! *********************************************************** NOTE: To ensure that the compiler correctly deals with tail-recursive functions calls, be sure to evaluate the following expressions at the beginning of any Lisp session: (setq compiler:tail-call-self-merge-switch t) (setq compiler:tail-call-non-self-merge-switch t) NOTE: For efficiency, you definitely want to COMPILE your files before you load them!! ----------------- NOTE: There are four parts to this assignment. You should put your definitions into three separate files, as follows: Part One: myname-ids.lisp Part Two: myname-a-star.lisp Part Three: myname-tiles.lisp Part Four: myname-tests.lisp ----------------- PART ONE: Implementing Iterative Deepening Search (IDS). A. First, you need to implement Depth-Limited Search (DLS). DLS takes a problem struct and a numerical limit as its inputs. (The queuing function can be hardwired to depth-first; so you don't need to pass it as an input.) It should return one of the following: a goal node, if one was found (at depth <= limit); NIL, if search queue exhausted without reaching the cutoff depth; CUTOFF, if search queue exhausted but cutoff depth *was* hit. It is important to understand the difference between returning NIL and returning CUTOFF. If NIL, then further search with a higher depth limit would be pointless; if CUTOFF, then further search may yield a goal node. Okay, define a function, DLS, that does depth-limited search for a particular limit, L. Now, you can't just use GEN-SEARCH for this because GEN-SEARCH-GUTS doesn't consider depth limits. However, you can start by cutting-and-pasting these function definitions into similar functions named DLS and DLS-GUTS. The changes to DLS-GUTS are not very big. In particular, you need to include an extra input parameter, CUTOFF-REACHED?, that is T if the depth-limit L has already been reached; NIL otherwise. Then, before expanding a node, you simply check its depth. If its depth is less than L, you expand it as usual; however, if its depth equals L, then you *don't* expand it (because its child nodes would be at depth L+1). ==> You can leave EXPAND, CYCLE? and MAKE-ROOT-NODE unchanged from Asmt 2 solutions. ==> Also, keep GEN-SEARCH and GEN-SEARCH-GUTS around because you can use them for A-STAR search. When making your recursive function call to DLS-GUTS, be careful how you deal with CUTOFF-REACHED? Also, be careful how you deal with the case of an empty search queue. By the way, you can test DLS on vacuum-world or missionaries and cannibals. Using small depth limits makes things easy to check. If you remove some of the actions, you can ensure that no solution will be found; that way you can check whether your NIL vs. CUTOFF answers are being correctly generated. B. Once you have DLS working, you can implement IDS as a function that takes a problem as its only input. It should be a wrapper for a recursive helper function, IDS-HELPER. IDS-HELPER should take a depth limit as an extra input. It should run DLS on the current depth limit. If a goal node is found, great! If NIL is returned, we're doomed! If CUTOFF is returned, try again (recursively) with the depth limit increased by 1. By the way, each time DLS is called, it resets the global variable, NODE-COUNT. So... you need to do something for IDS to keep track of the SUM of all the node-counts for all the iterations of DLS. You could create a new global variable, MASTER-NODE-COUNT, that is incremented each time DLS finishes a search; or you could be more responsible and have master-node-count be an accumulator input to IDS-HELPER that is updated on each recursive call to include the nodes created by the most recent call to DLS. Also, somewhere you'll want to print-out the path from root node to goal node, as well as the number of nodes created during the all iterations of DLS. PART TWO Implementing A-STAR search. Define a function called A-STAR that takes a PROBLEM and a HEURISTIC function as its two inputs. It should simply call GEN-SEARCH, but needs to provide an appropriate queuing function. Okay, so define a helper function called MAKE-F-QUEUING-FUNC. It should take a HEURISTIC function as its only input. It should return as its output a queuing function that maintains a search queue in order of F values, where the F values depend on the given heuristic. It's not as bad as it seems! NOTE: Recall that f(n) = g(n) + h(n). For this problem, g(n) = depth of n in the search tree. Use LABELS or FLET to create a helper function called F that takes one input N (a node) and computes the F value for that node. Recall that g(N) is found in the NODE struct and H(N) is obtained by using the supplied HEURISTIC function (courtesy of FUNCALL). Okay, now MAKE-F-QUEUING-FUNC doesn't return F ... instead it returns a QUEUING function *based* on F. So, use a LAMBDA special form to create a queuing function. Recall that queuing functions take two inputs (old-nodes and new-nodes). They sort the new nodes and then merge them with the old nodes. Fortunately, there are built-in Lisp functions called MERGE and SORT to take care of these tasks. Consider the following examples: CL-USER(2): (sort '(1 2 3 1 2 3) #'<=) (1 1 2 2 3 3) CL-USER(3): (sort '(1 2 3 1 2 3) #'<) (1 1 2 2 3 3) CL-USER(4): (sort '(-1 2 -3 -4 3 8 2) #'<) (-4 -3 -1 2 2 3 8) CL-USER(5): (sort '(-1 2 -3 -4 3 8 2) #'>) (8 3 2 2 -1 -3 -4) So, SORT takes a list and a comparison function and returns a sorted list. However, it can do more. For example, it can take an optional KEYWORD input (confusingly) called :KEY that allows you to PRE-PROCESS the objects being sorted. For example, if you want to sort the same numbers according to the values of their SQUARES... CL-USER(5): (sort '(-1 2 -3 -4 3 8 2) #'< :key (lambda (x) (* x x))) (-1 2 2 -3 3 -4 8) Or, if you want to sort a list of pairs by the values of their first entries: CL-USER(6): (sort '((1 hi) (2 bye) (0 you) (4 me)) #'<= :key #'first) ((0 YOU) (1 HI) (2 BYE) (4 ME)) MERGE is similar, except you have to TELL it what kind of output you want. We'll always ask it to generate a LIST as output. (I know, I know.) So, you can merge two already sorted lists according to some comparison function... CL-USER(7): (merge 'list '(1 3 5) '(2 4 6) #'<=) (1 2 3 4 5 6) And you can also give it a :KEY argument, for example, to merge two sorted lists of pairs according to the values of their FIRST entries. CL-USER(8): (merge 'list '((1 hi) (3 rope) (5 nope)) '((2 bye) (4 me)) #'<= :key #'first) ((1 HI) (2 BYE) (3 ROPE) (4 ME) (5 NOPE)) In our case, the F function is applied to each NODE to determine the sorting order. And we are interested in having the nodes sorted into increasing (or non-decreasing) order. PART THREE Implement the Eights-Tile-Puzzle domain. So, like vacuum-world or missionaries and cannibals, you'll need to define a STRUCT that holds desired state information. You can use either a vector or an array to hold the contents of the puzzle. You may also want to keep track of where the blank is. The goal state of the puzzle should look like this: 1 2 3 8 _ 4 7 6 5 Of course, that's what it looks like when printed out; you can represent it any way you like internally. You'll need a state-equality function. Please call it EIGHTS-EQUAL? You'll need a goal-test function. Please call it EIGHTS-GOAL? You'll need a function for each of the actions. Please call them BLANK-NORTH, BLANK-EAST, BLANK-WEST, BLANK-SOUTH. Of course, you are encouraged to define an abstract DO-BLANK-MOVE function that does all the dirty work for these action operators. Define heuristic functions, NUM-TILES-OUT and MANHATTAN-DISTANCE. If you want to use vectors or arrays, be sure to consult Graham's book for info. Some illustrations are given below, but they are not complete. ==> The use of SETF to destructively modify contents of arrays or vectors is fine within COPY-VECK or COPY-ARRAY. The other uses of SETF effectively create global variables for illustrative purposes only. As usual, you are strongly encouraged to AVOID destructive programming whenever possible. ------------------- VECTOR EXAMPLES -- notice use of LENGTH, MAKE-ARRAY, SVREF, SETF, DOTIMES ------------------- CL-USER(48): (defun copy-veck (veck) (let* ((len (length veck)) (new-veck (make-array len))) (dotimes (i len) (setf (svref new-veck i) (svref veck i))) new-veck)) COPY-VECK CL-USER(49): (setf vicki (vector 10 20 30 40 50)) #(10 20 30 40 50) CL-USER(50): (svref vicki 3) 40 CL-USER(51): (setf (svref vicki 3) 9999) 9999 CL-USER(52): vicki #(10 20 30 9999 50) CL-USER(53): (setf (svref mickey 0) 8) 8 CL-USER(54): mickey #(8 20 30 9999 50) CL-USER(55): vicki #(10 20 30 9999 50) ------------------- ARRAY EXAMPLES -- notice use of MAKE-ARRAY, ARRAY-DIMENSIONS, ARRAY-DIMENSION, AREF, SETF, DOTIMES ------------------- CL-USER(22): (defun copy-array (arrie) (let ((new-array (make-array (array-dimensions arrie)))) (dotimes (row (array-dimension arrie 0)) (dotimes (col (array-dimension arrie 1)) (setf (aref new-array row col) (aref arrie row col)))) new-array)) COPY-ARRAY CL-USER(23): (setf harry (make-array '(2 3) :initial-contents '((1 2 3) (10 20 30)))) #2A((1 2 3) (10 20 30)) CL-USER(24): (setf barry (copy-array harry)) #2A((1 2 3) (10 20 30)) CL-USER(25): (setf (aref harry 1 2) 999) 999 CL-USER(26): harry #2A((1 2 3) (10 20 999)) CL-USER(27): barry #2A((1 2 3) (10 20 30)) =============================== PART FOUR: Testing! Your test file will compile and load the relevant files and evaluate various test expressions. You may wish to define a helper function that compiles and loads the relevant files... Use your IDS and A-STAR search algorithms (with two different heuristics) on the eights tile puzzle domain. Begin with simple examples that can be solved in just a few moves to make sure your functions are working properly. Be careful when generating other examples: some configurations cannot be solved! If you find that your algorithms are running quite a long time, try swapping two of the tiles in the initial state. That often turns an unsolvable state into a solvable state. (Of course, you could define a helper function that starts with a solved state and applies, say, 15 randomly selected actions to generate a "scrambled" state. There's a built-in RANDOM function. See Graham's book for details.) You should run all three algorithms (IDS, A-STAR with Heuristic 1, A-STAR with Heuristic 2) on the same puzzle. Do this a few times for puzzles that take IDS quite a while to solve, but that A-STAR can solve more quickly. Confirm that the expected heuristic is better! SUMBISSION INSTRUCTIONS Please submit PRINTOUT of your four LISP files. DO NOT PRINT OUT *MY* definitions files!! ===> You need not print out your interactions file. (We want to conserve paper.) Submit all files electronically (in a single directory, as usual). submit365 asmt3 mysubmitdir ===> If working in pairs (which is recommended), please be sure to clearly indicate who worked on this assignment. For example, at the top of each LISP file, you could include comments such as: ;;; =================================== ;;; CMPU-365, Spring 2013, Asmt. 2 ;;; Barack Obama & Hillary Clinton ;;; =================================== And, for example, the submission directory could be called something like: obama-clinton-asmt2