CS472, 2008 Project 2a ------------------------------------------------------------------- What to submit: A zip file called proj2a_XX.zip where "XX" is your project number. That zip file will contain at least: proj2a/XX/make.lisp ; what i load to start your system proj2a/XX/src/ ; your code proj2a/XX/doc/task1.txt ; sample output from task 1 proj2a/XX/doc/task2.txt ; sample output from task 2 proj2a/XX/doc/task3.txt ; sample output from task 3 proj2a/XX/doc/task4.txt ; sample output from task 4 proj2a/XX/doc/task5.txt ; sample output from task 5 proj2a/XX/doc/task6.txt ; sample output from task 6 proj2a/XX/doc/task7.txt ; sample output from task 7 proj2a/XX/doc/task8.txt ; sample output from task 8 proj2a/XX/doc/task9.txt ; sample output from task 9 (optional) These tasks are listed below. Including another a task 10 that is a walk-through the code with me. Be warned- these tasks will not take equal time: - Tasks 1,2,3,4,5,6 will implement the interpreter and this will be a relatively fast task. - But tasks 7,8 will take _much_ more time. - And if you are brave enough to try task 9, then that will take quite some time. ------------------------------------------------------------------- Background Welcome to knowledge programming. In AI, we often use some declarative structure called a knowledge base to store domain details. Then we build an interpreter that can draw conclusions from that knowledge base. In effect, we have built a new language and a new interpreter for that language. This means that the same interpreter can be used for different knowledge bases. In project2a you will implement an new knowledge base language called RITUAL. When you demonstrate this code you will show it working on two different knowledge bases modeling the rituals seen in two different kinds of ethnic weddings (see the list at http://menzies.us/csx72/?137). RITUAL stores its knowledge in a modification of Novrig's grammar from chapter2. RITUAL fixes at least eight drawbacks to Norvig's rule system: 1) There is no SELECTION CONTROL how many times a phrase gets picked; e.g. never more than once, never more than 20 times. 2) There are no PROCEDURAL ACTIONS (e.g. a print statement thanking your for selecting a noun from the great list of nouns and Words Inc; or a pick M of N constructs) 3) There is no LOCAL ASSESSMENT that increments cost/benefit counters seen from selecting a particular phrase. 4) There is no GLOBAL ASSESSMENT that increments cost/benefit feedback seen from selecting combinations of phrases within the entire sentence. 5) There are no user definable PREFERENCES for biasing what gets picked out of M of N 6) There is no DEBUGGING information that helps you trace the firing of the rules. 7) There is no LOOP DETECTION for rules that recurse around to fire themselves again and again and again and... 8) Inert here your favorite complaint about Norvig's rules. I've fixed three of these and you have to fix the rest. Your tasks are to fix the remaining problems, then apply the refined system to the task of modeling the rituals around two ethnic weddings. ------------------------------------------------------------------- Task 0: set up Download and understand http://unbox.org/wisp/var/timm/08/ai/src/week5/harder.lisp. There you'll find a variant of Norvig's stuff that has three new features: 1) A working memory called *wme*. This is a bag of information that you can carry around between picking phrases. This code carries around three pieces of information: a) A list of used phrases. b) The benefits of using a phrase. Currently, this is not used. c) The cost of using a phrase. Right now, this is a pretty silly cost- just a count of the number of vowels used in each phrase. You need to do something better than that, (You may or may not want to use a,b,c- that will depend on your application.) 2) Procedural actions. The function "actionp" stores a list of defined "actions". If a rule contains a list whose first system in one of the "actions" then that "action" is used as a funcall (see "case 1" of "generate1"). For example, in the example grammar in harder.lisp there (Noun -> the (!pick 2 aa bb cc dd ee) man ball woman table) where "!pick2" is the action implemented in the "parser" function "!pick" (which parses out some information from the list) then "do-!pick" which does the work of pulling 2 items from the list (aa bb cc dd ee). 3) Local assessment. The function "local-assessment is called when some new phrase has not been "used-before". ------------------------------------------------------------------- Task 1: understand my code Fix harder.lisp's generate-tree code. It is the old code from Norvig and does not support procedural actions or local assessment. Write a function "(demo-task1)" that calls 5 "eg"-s that show off parts of the above code and your fixed "generate-tree". ------------------------------------------------------------------- Task 2: implement global assessment. Write a function that calls "generate-tree" and queries the returned contents for any insanities. E.g. poor grammar. Implement a set of insanity checks return numbers 0 to 10. Write a function "(demo-task2)" that shows off you can sum the total number of insanities. ------------------------------------------------------------------- Task 3: implement preferences Add a procedural action that selects things from a list, weighted towards the left hand side. For example (!any 1 a b c d) returns any one of "(a b c d)" with equal likelihood while (!any 0.8 a b c d) skews the selection. For example, with 0.8, these generates probabilities with sum 0.8^1 (for "a") and 0.8^2 (for "b") and 0.8^3 (for "c") and 0.8^4 (for "d'). This totals to 2.3616 which means these symbols are picked at probabilities a = 0.8^1 / 2.3616 = 34 % and b = 0.8^2 / 2.3616 = 27 % and c = 0.8^3 / 2.3616 = 22 % and d = 0.8^4 / 2.3616 = 17 % Write a function "(demo-task3)" that shows off you can control the preference of selection. ------------------------------------------------------------------- Task 4: add debugging information Write a function "(demo-task4)" that shows off you can trace the applications of the rules as well as calling the actions. Make the trace output indent according to the depth of the rules being called. ------------------------------------------------------------------- Task 5: add loop detection Write a function "(demo-task5)" that processes a grammar containing a loop. Show off that you can detect such loops and abort the recursive application of the rules. ------------------------------------------------------------------- Task 6: be clever List the things that most irritate you about Norvig's grammar and then write a function "(demo-task6)" that shows off your cleverness. ------------------------------------------------------------------- Task 7: code up one RITUAL Write a function "(demo-task7)" that, for one of your wedding rituals listing the total costs, benefits, and insanities seen in 100 randomly generated wedding plans. ------------------------------------------------------------------- Task 8: code up another RITUAL Write a function "(demo-task8)" that, for another of your wedding rituals listing the total costs, benefits, and insanities seen in 100 randomly generated wedding plans. ------------------------------------------------------------------- Task 9: (optional) difficult- only for extra credit Implement a search that controls how the rituals are created to bias the wedding plans towards those with higher benefits, lower costs, and fewer insanities. ------------------------------------------------------------------- Task 10: code walk through With your group, come to my office and I'll question your group about your code.