CSC244 / CSC444 - Assignment #3 DUE: 5:00PM November 14, 2006 TURNIN: Please email the following to ardis@cs.rochester.edu : + 1 LISP file (a3.lisp) containing all function and structure definitions used to solve the assignment problems. + 1 text file (a3_usage.txt) containing a text log of using your defined functions/structures to solve the assignment problems. Please include all code usage which you believe helps show the correct behavior of your provided LISP code. + 1 text file (a3_readme.txt) containing a brief description of all defined functions/structures including their intended purpose, input/output, etc. Please indicate here if your code has any problems/incapatabilities/failures, as well as any improvements for efficiency or robustness, for purposes of partial credit and/or extra credit. Your email should have the subject line "CSC244 Assignment 3" if you are in CSC244 and "CSC444 Assignment 3" if you are in CSC444. Multiple submissions are allowed, but only the most recent submission (prior to the deadline) will be graded. Please put your name at the top of your submission email. Late submissions will be accepted for 2 days with a 10% penalty per day. All submissions after November 16th will not be graded. PROBLEM: *** Graph Planning *** For this assignment, you will be asked to produce a set of functions (in an orderly progression) which will each make use of the previous functions for the purposes of graph planning. - STEP 1 - Create a function named "parse" which takes input of the following format: ( (name (and (pre1) (NOT pre2) (pre3)) (and (eff1) (eff2))) (name2 (pre4) (eff4)) That is, it takes as input a single list, each of whose elements is a list of the following format: (name (prelist) (efflist)) This corresponds to an action definition as seen on p.5 of Daniel Weld's paper. The precondition list and effect list have the following format: If zero entries: () If only one entry: (entry) Otherwise: (and (entry1) (NOT entry2)) That is, each entry is either a literal name or a negated name (corresponding to propositions in the world), and the list is built up from these as if they were evaluated logical truth values. You can assume that entries will only be done with propositional logic (not FOL). Your function should take this input and return a basic list which contains an "action" object for each specified action, where this object is a custom structure of your own devising. Sample input: ((jump () (inair)) (run (NOT inair) (fast)) (dive (and (inair) (fast)) (and (wet) (splash)))) ((waddle () ())) ((buy (money) (and (NOT rich) (skateboard))) (practice (time) (and (busy) (skillz))) (wipeout (and (skateboard) (NOT skillz)) (sukz)) (shred (and (skateboard) (skillz)) (rockz))) - Step 2 - Create a function named "mutex" which takes input identical to your previous function and returns a list of action name pairs when those two actions are mutually exclusive. Sample input: ((walk (NOT car) (there)) (drive (car) (there)) (dance (and (there) (NOT car)) (fun)) (cruise (and (there) (car)) (fun))) Sample output: ((walk drive) (dance cruise) (walk cruise) (drive dance)) Note that this function should make use of your "parse" function, then check for mutual exclusion using your "action" structures. Be sure to handle the mutex cases which Weld describes. - Step 3 - Create a function named "level" which takes as input a list containing two elements, the first of which is an input list as handled for the previous two functions (containing all of the actions) and the second of which is a list of entries of the same form as a precondition/effect list. The first element corresponds to all feasible actions, while the second corresponds to all possibly true propositions at this level of planning. Sample input (relating to dancing at parties): (((disco (and (fun) (NOT fancy)) (morefun)) (waltz (fancy) (morefun)) (tango (and (fun) (fancy)) (morefun))) ((fun) (clothes))) Your function should then determine the set of possible actions from this level (using your previous functions) and compute the next set of possible propositions. The output should be a list containing two elements: 1.) A list of possible actions, like: ((swim) (ski) (soccer)) 2.) A list of possible propositions, like: ((fun) (weird)) Be careful to handle mutually exclusive situations correctly. NOTE: If you wish, you may return this instead as a single custom structure which contains these lists. This may be useful for the following step. - Step 4 - Create a function named "graphplan" which performs full graph planning to attempt to solve a problem. Input will be a list containing four elements, the first two of which will be the two input elements to the previous function, the third of which will be a list of goal propositions, such as: ((fun) (morefun)) The fourth element will be a single integer value to indicate the number of steps to plan. Output should be a list of inputs from the previous function, meaning either a list of custom structures (each corresponding to a level) or a list of lists of the specified format. NOTE: I will NOT be testing each of these components (up through this step) with a script, so exact correlation of your output to this document is not necessary - the idea is to make each piece work in a regular manner so that it is easy to use the resulting information in the next function. - Step 5 - Create a function named "answer" which performs graph planning (using your above function), then does a backward search to find an answer (if one exists). "answer" should process iteratively, starting with an answer of length 1 (if one exists), and checking for a longer plan if it cannot find a solution of the current length (by telling graphplan to go another level). Input will be of the format specified in Step 4, but without the integer, meaning that it will consist of a list of actions, a list of known facts (initial state), and a list of goals. Output should be a list of actions (in the order in which they are performed) which solves all of the goals, if possible. If no solution exists at any length, return the following: (fail) You may use whatever criteria you wish for determing when to give up on finding a solution, but you must list in your readme file what this criteria is. Example 1: INPUT: (((buy (money) (food)) (eat (food) (happy))) ((money) (silly) (fun)) ((happy) (fun))) OUTPUT: (buy eat) Example 2: INPUT: (((walk () (tired))) ((tired) (sad)) ((NOT tired))) OUTPUT: (fail) - Step 6 - (CSC444 only, or CSC244 for up to 10% extra credit) Implement at least one optimization which speeds up your "answer" function on one or more provided test cases (separate from this document). Describe in your readme file the manner in which you implemented this optimization. This project is quite long, so PLEASE START EARLY. You will receive partial credit based on which steps you have correctly and fully implemented, so testing at each step is crucial. A series of test cases will be published throughout the span of this assignment. It is recommended that you test your code on as many as possible, as some of these will be used during grading. Good luck!