CMPU-365, Spring 2013 Asmt. 2 Due: Wed., Feb. 13 @ 11:59 p.m. NOTE: For this assignment, you are encouraged to work in pairs. Each pair need only turn in one solution. However, each file submitted must clearly indicate the names of the people in the pair. NOTE: No collaboration across *different* groups is allowed. ====================================================================== For this assignment, you will: (1) implement the general tree search algorithm; (2) implement the missionaries-and-cannibals domain discussed in class; and (3) use the general search algorithm to compare the performance of breadth-first and depth-first search on the missionaries and cannibals domain. To help you, you are provided with an implementation of the vacuum-world domain discussed in the text (and in class briefly). You should begin by creating a directory for this assignment. CD into that directory and set up an emacs/lisp session as described elsewhere. (Let me know if you have any trouble with any of this set-up stuff.) Download the following files into your working directory: gen-search-starter.lisp vw.lisp test-vw.lisp ===> Before doing any compilation, be sure to evaluate the following two expressions in your Lisp session: (setq compiler:tail-call-self-merge-switch t) (setq compiler:tail-call-non-self-merge-switch t) This will ensure that tail-recursive function calls are handled appropriately/efficiently by the compiler. You only need to do this once at the beginning of your lisp session. Okay, *now*, compile-and-load each of the files in turn, as follows: (compile-file "gen-search-starter") (load "gen-search-starter") (compile-file "vw") (load "vw") (compile-file "test-vw") (load "test-vw") Don't worry about the warning messages when you compile "gen-search-starter". They will go away when you fill in the needed function definitions. Open up "vw.lisp". It contains an implementation of the vacuum-world domain. It uses a global constant to hold the size of the vacuum-world. Currently, it is 4x4. It defines a VW-STATE data structure that records the robot's location and the locations of all the dirty squares. (This data structure can be defined in many many different ways, some more efficient/convenient than others.) Notice that the PRINT-VW-STATE function is automatically linked as the printing function for instances of the VW-STATE data structure. You can test this as follows: (format t "Here's a state: ~A. Pretty cool, eh?!~%" (make-vw-state :dirt-locations '((1 2) (2 2)))) The VW-STATE-EQUAL? function determines whether two given VW-STATE structs have the same contents. VW-GOAL-TEST returns T if the given STATE has no dirty locations. The actions in this domain are: NORTH, SOUTH, EAST, WEST and VACUUM. The first four are defined using a helper function, DO-MOVE. DO-MOVE uses a helper function VALID-XY, which determines whether the given move would be legal. VACUUM is defined separately. Feel free to create some sample states and apply various functions to them to see what happens. Also, look at the code to see how they are implemented using Lisp. Next, open up the "gen-search-starter.lisp" file. It defines the following: A global variable, called *NODE-COUNT* The SEARCH-PROBLEM and NODE data structures -- notice how the PRINT-NODE function is automatically linked to the NODE data structure. The functions: BUILD-PATH -- traces path from current node back to root node, returns the accumulated list of nodes ==> Notice the use of LABELS (Lisp's version of LETREC) PRINT-RESULTS -- displays information about a given search result CYCLE? -- Used to determine whether a given state already appears in the path of nodes from the given node back to the root node. MAKE-ROOT-NODE -- Create the root node for a new search tree EXPAND -- Given a node and a list of actions, apply generate a list of child nodes. Each new child node has a state that is obtained by applying one of the actions to the current state (i.e., the state associated with the given node). However, does not create nodes for repeat states. It uses CYCLE? to check for repeats. GEN-SEARCH -- This is a wrapper function for the recursive helper function, GEN-SEARCH-GUTS. The wrapper function initializes the node-count variable to 0, records the starting time, calls the helper function (which does the search), determines whether the search was successful or not, and then prints some statistics. GEN-SEARCH-GUTS -- This is the function that does the actual tree search algorithm. It takes a search problem and a queuing function as inputs. The queuing function determines what kind of search to do (in this assignment, either breadth-first or depth-first search). It should use the EXPAND function as a helper. FRONT-ENQUEUE!, END-ENQUEUE! -- Queuing functions that put newly generated child nodes at the front or end of the search queue. These functions are DESTRUCTIVE for reasons of efficiency. ==> All of the code you write should be NON-DESTRUCTIVE!! BREADTH-FIRST-SEARCH, DEPTH-FIRST-SEARCH -- Wrapper functions that call GEN-SEARCH with appropriate inputs. -------------------------- YOUR JOBS -------------------------- Flesh out the definitions of the CYCLE?, MAKE-ROOT-NODE, EXPAND and GEN-SEARCH-GUTS functions. Each of these is described in the text and has been discussed in class. These should all be NON-DESTRUCTIVE. NOTE: If GEN-SEARCH-GUTS is given a destructive queuing function, like front-enqueue! or end-enqueue!, then the search queue will be destructively modified when these queuing functions are used. But if given non-destructive queuing functions, then GEN-SEARCH-GUTS should be non-destructive. See the note about replacing NCONC with APPEND just above the definition of front-enqueue! The rest of the functions have already been defined for you. It is strongly recommended that you define your functions in the following order: MAKE-ROOT-NODE -- see "test-vw.lisp" for a sample problem to give it CYCLE? -- test this thoroughly on sample inputs before moving on. you can create a chain of search nodes manually to facilitate testing. be sure each case works properly. EXPAND -- you can begin by writing this without worrying about repeated states. expanding the root node for the vacuum world problem in "test-vw.lisp" should generate a list of several nodes. try it out. then expand one of those child nodes. make sure you don't allow moves out of the world! GEN-SEARCH-GUTS -- Once EXPAND is working, you're ready for this one. If the search queue is empty, then you're done; return NIL. If the first node in the search queue is a goal node, then you're done; return that node. Otherwise, you need recursion. The recursive case involves expanding the first node in the queue, inserting the newly generated nodes into the REST of the search queue (i.e., not including the first node), and then making the recursive call. When you've got all these functions working, then you can begin testing *simple* examples in the vacuum world. *** Make sure you have compiled and loaded all changed code before testing! You may wish to write a helper function that does the compiling and loading of all needed files. Try doing depth-first search on the sample problem in "test-vw.lisp". (Look at the testing functions defined in "test-vw.lisp".) Feel free to enlarge the size of the room or increase the number of dirty rooms so that your searches take more than a few seconds. Of course, you don't want to wait around for too long.... ------------- Now, you are ready to implement the missionaries-and-cannibals domain discussed in class. (Actually, this part can be done in parallel; that's the beauty of problem decomposition: different people can work on different independent parts.) The miss-and-cann domain will not stress your search algorithms unless you increase the numbers (e.g., the numbers of missionaries, cannibals, and move operators), but only try doing that if you have extra time. You should create a new file, mc.lisp, that contains structures and functions needed to implement the missionaries-and-cannibals domain. Feel free to mimic some of the functions provided in "vw.lisp"; however, you can probably come up with custom structures or representations for the miss-and-cann domain that will be much more efficient than if you try to making things too close to what's in vw.lisp. Remember that your representation should be concise and efficient. Also, you shouldn't generate illegal states (e.g., states where missionaries get eaten). When you have completed the mc.lisp code, run breadth-first and depth-first search on it. Because your GEN-SEARCH-GUTS function weeds out repeated states, your searches should run *really* fast! -- TESTING -- After all your code has been written and debugged, you should start a fresh Emacs/Lisp session, compile and load all files and then do your test cases. You should save the results of your test cases in a plain text file. (Use C-x C-w to save the contents of the Lisp buffer. That will, unfortunately, also kill the Lisp session.) ==================== GRADING ==================== Approximately 40% on GEN-SEARCH-STARTER functions Approximately 30% on missionaries and cannibals domain. Approximately 20% on testing (in both domains) Approximately 10% on clarity of code, layout, comments, etc. ================================== SUBMISSION INSTRUCTIONS ================================== You should not modify "vw.lisp" or "test-vw.lisp". You should only modify "gen-search-starter.lisp". And, of course, you should generate "mc.lisp" and the results of your testing (saved as plain text). Thus, you only need to PRINT OUT the following three files: "gen-search-starter.lisp", as modified by you "mc.lisp" your saved interactions To save paper, use the enscript command, as illustrated below: enscript -P Asprey -2jr mc.lisp Also, don't print out *too* many pages of interactions! The directory you SUBMIT ELECTRONICALLY, using submit365, should contain all lisp files, and your interactions. --> Be sure to remove any temporary files (i.e., those whose names end with a ~) before submitting electronically. ------------------------------ ONE SUBMISSION PER PAIR! ------------------------------ DUE: Wed., Feb. 13 @ 11:59 p.m.