CMSC 671: Introduction to Artificial Intelligence
Fall 2010

Extensions and late homework penalty

• Extensions may be granted for the whole group if requested as a group on any class previous to the due date.
• Extensions of up to one week may be granted on an individual basis, if requested in advance.
• Repeated requests for extensions, or requests for extensions at the last minute, will be denied other than in extraordinary circumstances.

• 0 to 24 hours late: 25% penalty
• 24 to 48 hours late: 50% penalty
• 48 to 72 hours late: 75% penalty
• More than 72 hours late: no credit will be given

You may use written reference materials. You may not work on or discuss the pretest with anyone else. This pretest will be graded for your information (and mine), but will not count towards your final course grade, nor will it make any difference on how you are evaluated on your tests and assignments. The primary intent is for you to identify prerequisite material that you are expected to know for CMSC 671. If you have trouble with this pretest, you may want to put in some time now reviewing basic concepts.

Problem 1, 20 points

Problem 2, 20 points

Problem 3, 60 points: 15 points for (a); 15 points for (c); 30 points for (b)

Problem 4, 10 points

OPTION 1
Check the Introduction and Section 1 (Turing (1950) and the Imitation Game) of Turing Test.
Write a 200-400 word discussion reflecting your opinion about the points discussed in section 5: The Turing Test is Too Hard; The Turing Test is Too Narrow; The Turing Test is Too Easy; Should the Turing Test be Considered Harmful?

• Pat Hayes and Ken Ford, Turing test considered harmful, Proceedings of IJCAI-95, pages 972-977, 1995.
• Hutchens, Jason L. 1996. How to pass the Turing test by cheating, University of Western Australia Technical Report TR97-05, 1997.
• Stuart Shieber. Lessons from a restricted Turing test. Communications of the Association for Computing Machinery, volume 37, number 6, pages 70-78, 1994.
• Saygin, A.P., Cicekli, I. and Akman, V. (2000), Turing test: 50 years later, Minds and Machines 10(4): 463-518.
• John R. Searle, Is the brain a digital computer?, Proceedings and Addresses of the American Philosophical Association volume 64, pages 21-37, November 1990.

The homework is due on Sat, Sep. 18. Submit by email (cmsc671@gmail.com) or bring it printed to the class.

Note: You have to submit the homework by the deadline to cmsc671@gmail.com. Additionally, you have to bring me a printed copy of your report (and the extra credit problem if submitting) to class on Tue, Oct. 19.

In this assignment, we'll explore the search space of the game Sudoku. I've provided some Lisp infrastructure (data structures, basic variables, and some helpful macros and functions). You do not have to use the code I have provided, as long as you provide working Lisp code with the specified functionality.

VERY IMPORTANT: You need to pace yourself with this assignment. You have three weeks, in order to give you some flexibility in managing your time and designing your software. I strongly suggest that you use this time wisely. For example, you may want to allocate the first week to implementing the basic form of the search algorithnm, which should be able to apply BFS and DFS to at least *test1* and ideally *test2*, and should be able to do repeated state checking. Use the second week to finish your implementation (record the appropriate data, implement queue/time limits, and implement queue ordering), testing on the larger problem. Use the third week to analyze your data and write your summary report. Be sure you do leave enough time to write the report, since it is worth 25% of the assignment.

1. Implementation (75 points)

Implement a generic uninformed search function, along the lines of the algorithm from the course slides. Write a wrapper function that invoke this generic search function to perform breadth-first, depth-first, and best-first search in the Sudoku search space. Your best-first search should sort the queue of nodes using a "maximally constrained" heuristic. That is, actions that fill empty cells where there is only one legal choice remaining should be tried first; next, try actions that fill empty cells for which there are two legal choices; and so on.

Include mechanisms to limit the length of the queue and/or computation time and to test for repeated states. (You will probably need to do a bit of experimentation to find reasonable values for the queue and time limits. Don't make them too low or you won't be able to solve many of the problems.) Test your code thoroughly, and make sure it's sufficiently well documented for us to read it and understand what it's doing.

Very important: Some of the search spaces will grow quite large, and I don't necessarily expect your implementation to be able to solve all of the problems.

2. Results and Discussion (25 points)

Run breadth-first, depth-first, and best-first search, with and without repeated-state checking, on the test cases *test1* through *test9* (given in the sudoku-basics.lisp file).  (In total, you should have 3 searches * 2 options * 9 test cases = 54 runs.)  Submit a well-organized report that summarizes your findings, and that discusses the questions below.  (Note that the tests have different array sizes.  The only function for which this should matter is the BLOCK-GROUPS function, which I've provided.  However, you'll need to reset XBLOCKS and YBLOCKS appropriately before invoking your solver.)

At a minimum, you should show, for each of the 54 runs, the number of nodes generated, number of nodes expanded, and CPU time consumed. You may present this data in a graph, chart, or table -- whichever you think will be most understandable and most effectively support your conclusions. (You will probably want to write a "wrapper" function to run all of the experiments and gather the statistics together.)

Your report should answer the following questions (though it does not need to be organized in this order, and you are certainly welcome to include additional observations, experiments, or ideas):

1. Did the algorithms find a solution in all cases?  If not, why not?
   
2. How did the various measures of run time (nodes generated/expanded and CPU time) compare for breadth-first search and depth-first search?
3. How did checking repeated states affect the various measures of run time?  Was this effect different for the different algorithms (BFS vs. DFS)?  Why or why not?
   
4. In this domain, what does it mean for a search to be optimal?  What does it mean for a search to be efficient?
5. How did you find a reasonable queue limit and/or time limit?  How would the algorithms behave if you increased or removed these limits?
6. How did queue ordering affect the various measures of run time? Was this effect different for the different algorithms?  Why or why not?
   
7. I didn't mention the possibility of using a depth limit, or iterative deepening search.  Would either of these be helpful?  Why or why not?

Additional background, description of the problem, and design guidance can be found here.

Extra credit problem (10 points)

The homework is due on Tue, Oct. 16, midnight. Submit your modified owl file and answers by email (cmsc671@gmail.com). Bring printed copy to next class (Do not print your modified owl file. Submit printed copy only for the answers to the questions below).

Problem 1, 40 Points: 20 points for (a); 20 points for (b)

1. The initial state on the figure is (1,4), that means A is on 1, B is on 4
2. The winning state for A is (4,3), whose value is +1
3. The first move down from the root of the ree has only one branch (and so does the next move too)
4. Looking at question (c), which is not part of the homework, might help when solving (b)
5. In the minimax algorithm there are no such things as ? values. You need to decide what to do when choosing the value to be backed up to a parent node when one of its children has a ? value

Problem 2, 60 Points: 30 points for (b); 10 points for each option from (c) to (e)

1. The three should have an empty board as the root node and 2 more levels down the root
   
2. Option (b) asks you to take symetry into account in order to reduce the search space, that is, the number of nodes you will expand. As an example, on the first level you only need to expand the first of the following two nodes:
   
3. For the second level, as an example, you only need to expand the first of the following two nodes
   

Problem 3, 10 Points

Russell&Norvig, exercise 6.9 (page 232)
Tips: Thinking of the sudoku (HW2) and the best-first search using a "maximally-constrained" heuristic might be of help. Check also the slides 38-41 for the class of Sep. 16 (Constraint Satisfaction).

In this homework you will do some basic stuff with ontologies. Specifically, you will use Protégé, an existing ontology editor to do a few changes to the ontology that you will be provided, as well as to observe the results of a reasoner.

SOFTWARE AND FILES

Download and install Protégé 4.x. Protégé is a powerful ontology editor with many features. So many features that many users have not found most of them. I will provide you here with a quick walkthrough on how to browse our small Pizza ontology and do some basic changes and reasoning. If you have any problems following the instructions here, or if you are interested in more details, you can run through the much more substantial Protege OWL tutorial. That tutorial is intended to teach you more details about OWL and Protégé. This notes are to show how to use Protégé efficiently for basic functionality.

Download the pizza ontology file that I have provided for this homework. This file is a short version of the original pizza ontology, which is a well-known ontology in the semantic web community. It is developed for educational purposes by the University of Manchester, which is a leading university in the development of semantic technologies.

Just as a reference, the original pizza ontology (bigger than the one I have supplied) can be found at http://www.co-ode.org/ontologies/pizza/2007/02/12/

YOUR HOMEWORK

1. Open the pizzaCMSC671.owl file with Protégé. The Active Ontology tab that shows up initially give you a summary of the information contained in the ontology (number of classes, relations, properties, axioms, etc.)
2. Go to the Classes tab and take a look at the "Asserted Class Hierarchy" (in the tab with that name). This is the hierarchy that has been asserted by us as users or ontology engineers (as opposed to infered by a reasoner).
   As you select a class (clicking on it) you can see its properties, restrictions, etc. on the right side ("Usage" pane)

PROBLEM 1. Ontology graph

Draw a graph of the ontology that contains the classes Food, Pizza, PizzaBase, and PizzaTopping, and the relations among them. Here are the guidelines to do it:
• The nodes in the graph are the classes and the edges are the relations. You can see the relations in the ObjectProperties tab (relations are called ObjectPorperties in OWL), as well as the Domain and Range for each (which tell you the classes that they link).
• There are basically 6 relations, namely, hasIngredient and isIngredientOf (both from Food to Food), and the two subproperties of each (e.g. hasBase which goes from Pizza to PizzaBase).
• Include also, a couple of subclasses of Pizza, PizzaBase, and/or PizzaTopping. For example, if you choose to include CheeseyPizza, you will have a node for it and draw an edge from it to Pizza with the label "subclass".
• For an example of how your graph should look like, you can look at this file, which contains a part of the graph you will be submitting.
3. You will now perform reasoning on the ontology. Before you do that, check again the "Asserted Class Hierarchy" and notice we have some Pizzas defined as subclasses of the NamedPizza class. This are particular examples of pizzas. I have explicitly decided to put them here as opposed as instances (or individuals). Also, notice that all the other sublcasses of Pizza (CheeseyPizza, InterestingPizza, etc) do not have subclasses.
4. Make sure you have a reasoner installed with Protégé. Select the "Reasoner" option on the main menu and you should have some reasoner there (Pellet, Fact++, Hermit, or other). I have particularly tried Pellet for this exercise, but you can use any other.
   If you do not see any Reasoner under that option, you need to install one. You can find instructions to install Pellet directly from Protégé here (look for the Installation section).

   PROBLEM 2. Inference results

   Run the reasoner and go to the "Inferred Class Hierarchy" tab (right next to "Asserted Class Hierarchy").
   • What inconsistencies were found? (Inconsistencies found by the reasoner are highlighted with RED color)
   • What subsumption inferences were made? (subclasses). Check on the pizzas that did not have subclasses on the asserted class hierarchy. Specifically check if any of the named pizzas (subclasses of NamedPizza) were classified also as subclasses of any other pizza (CheesyPizza, InterestingPizza, MeatyPizza, ThinAndCrispyPizza).
5. Can you figure out why TomatoTopping is inconsistent? Regardless, delete it (go back to the "Asserted Class Hierarchy" tab, select it and click on the X button) and run the Reasoner again.

   PROBLEM 3. Inference results iteration 2

   Go back to the results ("Inferred Class Hierarchy") and tell what was different this time.
6. CheeseyVegetableTopping is still inconsistent, can you figure out why? Lets get rid of it too ... Delete it the same way you deleted TomatoTopping.
7. Finally, come up with a couple of pizzas of your own creation ...

   PROBLEM 4. Define your favorite pizzas (at least two)

   Back in the "Asserted Class Hierarchy", create a subclass of NamedPizza.
   • Select NamedPizza and then click on the "add subclass button" (first button with a plus sign).
   • Name your class.
   • Put some toppings. Check how other NamedPizzas have been defined having some specific toppings. You can see that on the "Description" pane. If it is not visible, go to the main menu and select "View", "Class views", "Description". Specifically, to add a topping we create a restriction on the class. We add a superclass (on the Descripion pane) for our named pizza class using the "Object Restriction Creator".

The homework is due on Tue, Nov.9, 2:15pm. Submit by email (cmsc671@gmail.com) and bring printed copy to class.

Problem 1, 40 Points: 20 points for (a); 20 points for (b)

Russell&Norvig, exercise 14.4 (page 559)

For option a, answer the question (if no evidence is observed, are Burglary and Earthquake independent?) from what you see in the network (Fig. 14.2), that is, the topology of the network or topological semantics. Then compute the probability P(Burglary, Earthquake).

For option b, we want to show whether P(B,E|A) and P(B|A)P(E|A) are equal. Use Bayes Theorem to solve for them. That is:

• P(B,E|A) = P(A|B,E)P(B,E) / P(A)
• P(B|A) = P(A|B)P(B) / P(A)
• P(E|A) = P(A|E)P(E) / P(A)

Problem 2, 40 Points

Problem 3, 30 Points

1. [15 points] Draw the bayesian belief network that represents the conditional independence assumptions of the Naive Bayes classifier for the PlayTennis problem discussed in class. Slides 17-19 from Nov. 18 class and slides 59-62 from Nov. 16 class.
2. [15 points] Give the conditional probability table associated with the node Wind

Hint: The following general bayesian network represents the Naive Bayes (conditional independence) assumptions.

The homework is due on Tue, Nov. 30, midnight. Submit by email (cmsc671@gmail.com) and bring printed copy to next class (Thu, Dec. 2nd).