Assignment 3 information

• Unfortunately, the web grader is not up now and won't be in time for this assignment. So, you will still need to submit your code electronically but in the same manner as for Assignment 2 (see instructions below).

  IMPORTANT: Your code must load and run correctly! There is now no excuse for it not to: you have a test function which will load your file and at least check that you have defined the proper procedures. A handful of students had some problems last time; these problem were things such as unbalanced parentheses, having things other than your code in the file. There will be a 10% penalty if we have to edit your file to make it work with our tester.

  Also note the limit on heap memory as described towards the bottom of this page.

  Your scheme code file should look something like this:

  ; Your Name
  (load "a3code")
  (load "a3tests")
  
  (define (ep-children s)
    ...)
  
  (define (ep-manhattan state goal)
    ...)
  
  (define (ep-heuristic state goal)
    ...)
  

• Problems 1, 2, and 4c (the written problems) are to be turned in on paper in class on Tuesday.

• Electronic turn-in instructions (basically the same as last time):
  • Your scheme code for all functions that are to be turned in electronically (including any helper functions they need to run, of course) should be in a single file. Name this file using your RCS username and the extension ".scm". For example, if President Shirley Jackson were taking this class and her RCS email address is jackss@rpi.edu, then she would name her file jackss.scm

  • On RCS, copy or ftp your file to the directory /dept/cs/ai/submit3 You will only have permission to copy a file into this directory and to list the files in this directory. You cannot read, modify, or delete files in this directory.

    You cannot do this from the newer CS machines because they do not have AFS. You can however, do it from the older machines such as dishwasher. You will have to klog -cell rpi.edu and then copy your file to /afs/rpi.edu/dept/cs/ai/submit3.

  • On RCS windows systems, you can click on the desktop RCS icon and connect to the public areas. You'll have to type your RCS username and password. Then open the "dept", "cs", and "ai" folders.

  • If for some reason you need to resumbit your assignment, add an extension ".1" when you sumbit your revised solutions. For example, if Dr. Jackson had to resumbit her assignment, she would name the new file jackss.scm.1 If for some reason you need to sumbit the assignment again, increment the number of the final extension (e.g. jackss.scm.2, etc.)

  • We will only grade the most recent sumbission.

• Note on Problem 1a: I have been convinced that there is more than one good answer to this problem. Even using the simplest interpretation of the text's scheme (so to speak) of generating children, their suggested answer is too high. In the course of thinking about this problem, you will probably think of a better way to generate the children.

  Your answer should definitely be smaller than the text's suggested answer, and you should try to devise a way to avoid identical expression trees from appearing at multiple nodes in the search tree.

• Note on problem 4b and 4c: Your heuristic need not be monotonic or admissible; however, we expect an explanation in 4c. Regarding the performance evaluation, if your heuristic is not admissible (and therefore may return a suboptimal solution), then it should be better in terms of computation time and the number of nodes evaluated.

  The performance evaluation will be measured in terms of cpu time, number of nodes evaluated, and whether the solution returned is optimal. It should be fairly easy to get at least half of the points for this part of the problem. (The breakdown is as follows: 8 points for part (a), 16 points for part (b), and 6 points for part (c).) It should take more work to get almost all the points, and I'd expect only a few students to have heuristics that garner all 16 points for this problem.

  I've put a few suggestions for heuristics on this page if you're looking for suggestions on something to implement.

• For this assignment, I am providing both the A* code and a simple testing procedure that will allow you to test do some rudimentary tests on your scheme code before uploading it. There are two files that you need for this assignment:
  • A* and testing code This is compiled scheme code.
  • Information and testing aids This contains some useful procedures and instructions for using the A* code and the testing procedure.

  The compiled code only runs on x86 Intel hardware for MIT Scheme versions 7.5. I'm working on a compiled version for SunOS with MIT Scheme 7.3. (Mon. 9/25 update: still no luck yet; i'll try some more but at this point can't guarantee that it will be availible for Sun hardware.)

• You may need to start Scheme with more memory. You can do this by giving it a command line switche. Windows users can create/copy/edit the shortcuts on your start menu.

    scheme -large
  

  will start scheme with more memory than usual (about 3-4 times, i think). You can also specify a size for the heap directly:

    scheme -heap 4000
  

  This sets the heap to 4000K words. This should be more than large enough for any decent heuristic. This is what the web tester will use, so your program must execute in this size heap.

  The -large flag is equivalent to setting the heap to around 1200. You can get memory information with the Scheme command (print-gc-statistics).